자바[JAVA] 자료구조 구현 4 - 이중 연결 리스트

0. 이중 연결 리스트

 

단일 연결리스트는 다음 노드를 가르키는 포인터 변수를 가지고 있었다면 이중 연결 리스트는 다음 노드 뿐만 아니라 이전 노드를 가르키는 포인터 변수까지 가지고 있는 노드로 이루어져있습니다.

즉 양방향으로 연결 된 리스트를 LinkedList 중에서도 Doubly LinkedList 라고 합니다.

 

 

이렇게 되면 단일 연결 노드보다 검색의 성능이 좋아집니다. 만약 10개의 노드가 있고, 9번째 노드를 검색하고 싶다면 단일 연결 노드에서는 head 노드부터 시작하여 거의 모든 노드를 거쳐서 가야합니다.

하지만 이중 연결 리스트는 10번, 9번 노드 단 두 번만에 검색할 수 있습니다.

 

 

1. Node 클래스

 

이전까지 사용되었던 Node 클래스와 달리 이전 노드를 가르키는 래퍼런스 변수 @param prev 가 생겼습니다.

public class Node<E> {

    E data;
    Node<E> next; // 다음 노드를 가르키는 래퍼런스 변수
    Node<E> prev; // 이전 노드를 가르키는 래퍼런스 변수

    Node(E data){
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

 

2. DlinkedList 클래스

 

import Interfaces.List;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;

@SuppressWarnings("rawtypes")
public class DLinkedList<E> implements List<E>{

    private Node<E> head; // 노드의 첫 부분
    private Node<E> tail; // 노드의 마지막 부분
    private int size; // 요소 개수

    public DLinkedList(){
        this.head = null;
        this.tail = null;
        size = 0;
    }

    public Node<E> search(int index){

        // index range 오류
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException();

        // 헤드 노드부터 탐색 시작
        Node<E> x = head;

        for(int i=0; i<size; i++){
            if(i == index){
                // index 값에 해당하는 노드 반환
                return x;
            }
            // 아니면 다음 노드로 넘어감
            x = x.next;
        }
        return null;
    }

    public Node<E> searchBack(int index){

        // index range 오류
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException();

        // 꼬리 노드부터 탐색 시작
        Node<E> x = tail;

        for(int i = (size - 1); i>0; i--){
            if(i == index)
                return x;
            // 아니면 그 전 노드로 넘어감
            x = x.prev;
        }

        return null;
    }

    // LinkedList 의 기본 add 는 addLast 와 같다
    @Override
    public boolean add(E e) {
        addLast(e);
        return true;
    }

    // 리스트의 가장 마지막에 노드를 넣는다
    public boolean addLast(E e){

        Node<E> newNode = new Node<>(e);

        // 리스트의 요소가 하나도 없을 때는 새로운 노드가 head 이자 tail 이 된다.
        if(size == 0){
            head = tail = newNode;
            newNode.prev = newNode.next = null;

            size++;

            return true;
        }
        // 리스트의 요소가 하나라도 있는 경우
        else{
            Node<E> tailNode = tail;

            tailNode.next = newNode;
            newNode.prev = tailNode;

            tail = newNode;
            newNode.next = null;

            size++;

            return true;
        }
    }

    public boolean addFirst(E e){

        // 요소가 하나도 없는 경우 가장 처음에 노드를 넣는건
        // 가장 마지막에 노드를 넣는것과 다르지 않다.
        if(size == 0){
            addLast(e);
            return true;
        }
        // 요소가 하나라도 있는 경우
        else{
            Node<E> newNode = new Node<E>(e);
            Node<E> headNode = head;

            newNode.next = headNode;
            headNode.prev = newNode;

            head = newNode;
            newNode.prev = null;

            size++;

            return true;
        }
    }

    @Override
    public void add(int index, E e) {

        // index range 오류
        if(index < 0 || index > size)
            throw new IndexOutOfBoundsException();

        // 0 번째 index 로 add 되는건 addFirst 와 다르지 않다.
        if(index == 0){
            addFirst(e);
            return;
        }
        // size 번째 index 로 add 되는건 addLast 와 다르지 않다.
        else if(index == size){
            addLast(e);
            return;
        }
        // 가운데에 삽입되는 경우
        else{
            Node<E> newNode = new Node<>(e);
            Node<E> prevNode = search(index - 1);
            Node<E> nextNode = prevNode.next;

            prevNode.next = newNode;
            newNode.prev = prevNode;

            nextNode.prev = newNode;
            newNode.next = nextNode;

            size++;

            return;
        }
    }

    // LinkedList 의 기본 remove 는 removeFirst 이다.
    public E remove(){
        return remove(0);
    }

    @Override
    public boolean remove(Object o) {

        // 머리 노드부터 순차 탐색
        Node<E> x = head;

        for(int i=0; i<size; i++){
            // 해당 노드를 찾으면 그 노드 index 를 이용하여 remove
            if(x.data.equals(o)){
                remove(i);
            }
            // 못 찾았으면 다음 노드로 넘어감
            x = x.next;
        }

        // 아에 못찾았으면 false 반환
        return false;
    }

    @Override
    public E remove(int index) {

        // index range 오류
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException();

        // 가장 처음 노드를 삭제하는 경우
        if(index == 0){
            Node<E> headNode = head;
            E data = headNode.data;

            Node<E> nextNode = headNode.next;

            headNode.next = headNode.prev = null;

            size--;

            // 원래 요소가 하나밖에 남지 않았던 경우
            // 머리 노드와 꼬리 노드가 모두 null 이 된다.
            if(size == 0){
                head = tail = null;
                return data;
            }
            // 원래 요소가 하나 이상이었던 경우
            // 머리 노드만 바꾸면 된다.
            else{
                head = nextNode;
                nextNode.prev = null;
                return data;
            }
        }
        // 마지막 노드를 삭제하는 경우
        // 요소가 하나여서 머리 노드와 꼬리 노드가 모두 null 이 되는 경우는 위에서 이미 함
        else if(index == (size - 1)){
            Node<E> tailNode = tail;
            E data = tailNode.data;

            Node<E> prevNode = tailNode.prev;

            tailNode.next = tailNode.prev = null;

            tail = prevNode;
            prevNode.next = null;

            size--;
            return data;
        }
        // 가운데에 낀 노드를 삭제하는 경우
        else{
            Node<E> deletedNode = search(index);
            Node<E> prevNode = deletedNode.prev;
            Node<E> nextNode = deletedNode.next;
            E data = deletedNode.data;

            deletedNode.prev = deletedNode.next = null;

            prevNode.next = nextNode;
            nextNode.prev = prevNode;

            size--;
            return data;
        }
    }

    @Override
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public E get(int index) {
        return search(index).data;
    }

    @Override
    public void set(int index, E e) {
        search(index).data = e;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int indexOf(Object o) {

        // 머리 노드부터 순차 탐색
        Node<E> x = head;

        for(int i=0; i<size; i++){
            // 해당 노드를 찾으면 해당 노드의 index 반환
            if(x.data.equals(o)){
                return i;
            }
            // 못 찾았으면 다음 노드로 넘어감
            x = x.next;
        }

        // 아에 못찾았으면 -1 반환
        return -1;
    }

    @Override
    public void clear() {

        Node<E> x = head;

        for(int i=0; i<size; i++){
            Node<E> nextNode = x.next;

            x.next = x.prev = null;
            x.data = null;
        }

        head = null;
        tail = null;
        size = 0;
    }

    @SuppressWarnings("unchecked")
    public DLinkedList<E> clone() throws CloneNotSupportedException {

        DLinkedList<E> clone = (DLinkedList<E>) super.clone();

        clone.head = null;
        clone.tail = null;
        clone.size = 0;

        Node<E> x = head;

        for(int i=0; i<size; i++){
            clone.add(x.data);

            x = x.next;
        }

        return clone;
    }

    public Object[] toArray(){

        Object[] a = new Object[size];

        int i = 0;
        for(Node<E> x = head; x != null; x = x.next, i++){
            a[i] = x.data;
        }

        return a;
    }

    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a){

        if(a.length < size){
            a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
        }

        int i = 0;
        for (Node<E> x = head; x != null; x = x.next) {
            a[i++] = (T) x.data;
        }
        return a;
    }

    public void sort(){
        sort(null);
    }

    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c){

        Object[] sort = this.toArray();

        Arrays.sort(sort, (Comparator) c);

        int idx = 0;
        for(Node<E> x = head; x != null; x = x.next){
            x.data = (E) sort[idx++];
        }
    }
}

 

추가 공부: 제너릭 배열