[자료구조] 3. Doubly LinkedList

Doubly LinkedList

 

실제 자바에서 제공하는 util 패키지의 LinkedList는 이번에 구현할 Doubly LinkedList와 같은 형식으로 구현되어 있다. 단일 연결리스트와 차이점은 단일 연결리스트는 노드에 데이터, 다음 노드를 가리킬 변수만을 갖고 있었다면 이중 연결리스트는 이전 노드를 가리키는 변수도 갖고 있다.

 

 

전체적인 구조는 다음과 같다.

 

 

양방향 연결리스트는 단방향 연결리스트보다 검색(색인)능력이 좋아진다. 단방향 연결리스트에서는 head부터 탐색했어야 했다. 하지만 양방향 연결리스트에서는 찾으려는 값이 만약 tail에 더 가깝다면 tail부터 탐색하면 되고 head에 더 가깝다면 head부터 탐색하면 되므로 보다 더 효율적인 탐색이 가능하다.

---

Node 구현

 

public class Node<E> {

    E data;
    Node<E> prev;
    Node<E> next;

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

}

 

Doubly LinkedList 구현

많은 부분이 Singly LinkedList와 비슷하다. Singly LinkedList와 다른 부분에 대해서만 자세히 짚고 넘어가고 그렇지 않은 부분은 이전의 포스트에서 확인하면 좋을듯 하다.

 

<필수 목록>

• 클래스 및 생성자 구성
• search 메소드 구현
• add 메소드 구현
• get, set, indexOf, containsOf 구현
• remove 메소드 구현
• size, isEmpty, clear 메소드 구현 

<부가 목록>

• clone, toArray, sort 메소드 구현

---

Doubly LinkedList 클래스 및 생성자 구성

public class DoublyLinkedList<E> implements List<E> {
    
    private Node<E> head;
    private Node<E> tail;
    private int size;

    public DoublyLinkedList(Node<E> head, Node<E> tail, int size) {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}

 

 

head : 리스트의 가장 첫 노드를 가리키는 변수

tail : 리스트의 가장 마지막 노드를 가리키는 변수

size : 리스트의 요소의 개수 (연결된 노드의 개수)

 

public class DoublyLinkedListTest {
    public static void main(String[] args) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
    }
}

 

메인 클래스에서 객체 생성은 위와 같다.

---

search 메소드 구현

 

이전의 단방향 연결리스트와 마찬가지로 데이터의 삽입, 삭제, 검색을 위해 next 변수를 통해 찾아가야 할 일이 많다.

 

앞으로 구현할 대부분의 자료구조들도 search 메소드를 먼저 구현하면 편리하다.

 

양방향 연결리스트는 검색 과정에서 효율적이도록 index값이 tail에 가까운지 (size값에 가까운지) head에 가까운지 (0에 가까운지)를 구분하여 탐색 시작 위치부터 정하고 찾기 시작한다.

 

private Node<E> search(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    // tail 에서부터 탐색
    if (index + 1 > size / 2) {
        Node<E> x = tail;

        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        }

        return x;

    } else {    // head 에서부터 탐색
        Node<E> x = head;

        for (int i = 0; i < index; i++) {
            x = x.next;
        }

        return x;
    }
}

 

---

add 메소드 구현

 

add 메소드는 단방향 연결리스트와 같이 크게 3가지로 분류된다.

 

• 가장 앞 부분에 추가 - addFirst(E value)
• 가장 마지막 부분에 추가 - addLast(E value)
• 특정 위치에 추가 - add(int index, E value)

 

1. addFirst(E value)

 

 

새로운 노드를 생성하고 새 노드의 next변수가 현재 head 노드를, head노드의 prev 변수가 newNode를 가리키게 하도록 하고 head 노드를 newNode로 업데이트 시킨다.

 

public void addFirst(E value) {
    Node<E> newNode = new Node<>(value);
    newNode.next = head;

    /**
     * head 가 null 이 아닐 경우에만 기존 head 노드의 prev 변수가 새 노드를 가리키도록 한다.
     * 이유는 기존 head 노드가 없는 경우 (null)는 데이터가
     * 아무 것도 없는 상태이므로 head.prev 를 하게 되면 잘못된 참조가 된다.
     */
    if (head != null) {
        head.prev = newNode;
    }

    head = newNode;
    size++;

    /**
     * 다음에 가리킬 노드가 없는 경우 ( 데이터가 새 노드 밖에 없는 경우)
     * 데이터가 한개라는 뜻이므로 새노드는 처음 시작노드이자 끝 노드이다.
     */
    if (head.next == null) {
        tail = head;
    }
}

 

 

2. 기본 삽입 : add(E value) & addLast(E value) 메소드

 

size == 0일 경우 처음 데이터를 삽입하는 것이기 때문에 addFirst를 사용하면 된다.

 

@Override
public boolean add(E value) {
    addLast(value);
    return true;
}

public void addLast(E value) {
    Node<E> newNode = new Node<>(value);

    if (size == 0) {
        addFirst(value);
        return;
    }

    tail.next = newNode;
    newNode.prev = tail;
    tail = newNode;
    size++;
}

 

 

3. add(int index, E value)

 

 

 

먼저 넣으려는 위치의 노드와 이전 노드를 찾아야 한다.

 

넣으려는 위치의 이전노드를 prevNode라 하고, 넣으려는 위치의 기존노드를 nextNode라고 할 때

search 메소드를 사용하여 넣으려는 위치의 - 1 위치의 노드를 찾아내고, nextNode는 그 노드의 next 변수를 통해 찾는다.

 

그리고 이전 노드의 next 변수는 새 노드를, 새노드는 prev와 next를 앞뒤 노드를 가리키도록 하고 nextNode의 prev 변수는 새노드를 기록한다. 또한 index가 잘못된 위치를 참조할 수 있으므로 예외처리는 필수다.

 

@Override
public void add(int index, E value) {
    // 범위 체크
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException();
    }

    // index 가 0이면 가장 맨 앞이므로 addFirst 활용
    if (index == 0) {
        addFirst(value);
        return;
    }

    // index 가 size 와 같다면 마지막이므로 addLast 활용
    if (index == size) {
        addLast(value);
        return;
    }

    Node<E> prevNode = search(index - 1);       // 넣으려는 위치 이전 노드
    Node<E> nextNode = prevNode.next;                 // 넣으려는 위치의 노드
    Node<E> newNode = new Node<>(value);              // 새로운 노드

    // unlinking
    prevNode.next = null;
    newNode.prev = null;

    // linking
    prevNode.next = newNode;        // prev 노드의 next 에 새 노드에 연결

    newNode.prev = prevNode;        // 새 노드의 prev 는 이전 노드에
    newNode.next = nextNode;        // 새 노드의 next 는 다음 노드에 연결

    newNode.prev = newNode;         // next 노드의 prev 에 새노드에 연결

    // size 증가
    size++;
}

 

 

---

 

remove 메소드 구현

remove 메소드도 3가지로 나눌 수 있다.

 

• 가장 앞의 요소 삭제 - remove()
• 특정 index의 요소 삭제 - remove(int index)
• 특정 요소를 삭제 - remove(Object value)

 

1. remove() 메소드

 

 

public E remove() {
    Node<E> headNode = head;

    if (headNode == null) {
        throw new NoSuchElementException();
    }

    E element = headNode.data;

    Node<E> nextNode = head.next;

    head.data = null;
    head.next = null;

    /**
     * head 의 다음 노드가 null 이 아닐 경우만 prev 변수를 업데이트 해야한다.
     * nextNode 가 없는 경우는 데이터가 아무것도 없는 상태이므로 잘못된 참조가 된다.
     */
    if (nextNode != null) {
        nextNode.prev = null;
    }

    head = nextNode;
    size--;

    /**
     * 삭제된 요소가 리스트의 유일한 요소였을 경우
     * 그 요소가 head 이자 tail 이었으므로
     * 삭제되면서 tail 도 가리킬 요소가 없기 때문에
     * size 가 0일 경우 tail 도 null 로 변환
     */
    if (size == 0) {
        tail = null;
    }

    return element;
}

 

 

2. remove(int index) 메소드

 

삭제하려는 노드의 이전 노드의 next 변수를 삭제하려는 노드의 다음 노드를 가리키도록 하면 된다.

 

 

알아야 할 노드는 삭제할 노드 (search로 찾는다)와 삭제할 노드의 이전 노드와 다음 노드이다.

 

@Override
public E remove(int index) {

    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    if (index == 0) {
        E element = head.data;
        remove();
        return element;
    }

    Node<E> prevNode = search(index - 1);
    Node<E> removeNode = prevNode.next;
    Node<E> nextNode = removeNode.next;

    E element = removeNode.data;

    /**
     * index == 0 일 때 조건에서 이미 head 노드 삭제에 대한 분기가 있기 때문에
     * prevNode 는 항상 존재 한다.
     * 
     * 그러나 nextNode 의 경우는 null 일 수 있기 때문에
     * 이전처럼 반드시 검사를 해준 뒤에 nextNode.prev 에 접근해야 한다.
     */

    prevNode.next = null;
    removeNode.data = null;
    removeNode.next = null;
    removeNode.prev = null;

    if (nextNode != null) {
        nextNode.prev = prevNode;
        prevNode.next = nextNode;
    }

    /**
     * nextNode 가 null 이라면 마지막 노드를 삭제했다는 의미임
     * 따라서 prevNode 가 tail 이 된다.
     */
    if (nextNode == null) {
        tail = prevNode;
    }

    size--;

    return element;
}

 

이번에는 고려해야 할 것들이 몇가지 있다. 첫 번째 요소가 삭제되는 경우, 마지막 요소가 삭제되는 경우, 요소가 한 개 남았을 때의 경우이다.

 

 

3. remove(Object value) 메소드

 

 

@Override
public boolean remove(Object value) {

    Node<E> prevNode = head;
    Node<E> x = head;       // removeNode

    // value 와 일치하는 노드를 찾는다;
    for (; x != null; x = x.next) {
        if (value.equals(x.data)) {
            break;
        }
        prevNode = x;
    }

    // 찾으려는 요소가 없을 경우 false 반환
    if (x == null) {
        return false;
    }

    // 삭제하려는 노드가 head 일 경우 remove() 삭제
    if (x.equals(head)) {
        remove();
        return true;
    }

    // remove(int index) 와 같은 매커니즘으로 삭제
    else {
        Node<E> nextNode = x.next;

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

        if (nextNode != null) {
            nextNode.prev = prevNode;
            prevNode.next = nextNode;
        } else {
            tail = prevNode;
        }

        size--;

        return true;
    }
}

 

---

get, set, indexOf, contains 메소드 구현

 

1. get(int index) 메소드 구현

 

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

 

2. set(int index, E value) 메소드 구현

 

@Override
public void set(int index, E value) {
    Node<E> replaceNode = search(index);
    replaceNode.data = value;
}

 

3. indexOf(Object value) 메소드

 

단방향 연결리스트에서는 head부터 탐색했어야 했지만 양방향 연결리스트는 tail 부터도 탐색이 가능하기 때문에 indexOf를 두 개 만든다.

하나는 head 부터 검색하는 메소드, 다른 하나는 tail 부터 검색하는 메소드이다.

 

항상 찾고자 하는 요소를 가장 먼저 마주치는 요소의 인덱스를 반환하게 한다.

 

@Override
public int indexOf(Object value) {
    int index = 0;

    for (Node<E> x = head; x != null; x = x.next) {
        if (value.equals(x.data)) {
            return index;
        }
        index++;
    }

    return -1;
}

public int lastIndexOf(Object value) {
    int index = size;

    for (Node<E> x = tail; x != null; x = x.prev) {
        if (value.equals(x.data)) {
            return index;
        }
        index--;
    }

    return -1;
}

 

 

4. contains(Object value) 메소드

 

 

@Override
public boolean contains(Object value) {
    return indexOf(value) >= 0;
}

 

 

---

 

size, isEmpty, clear 메소드 구현

 

1. size() 메소드

 

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

 

 

2. isEmpty() 메소드

 

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

 

 

3. clear() 메소드 

 

@Override
public void clear() {
    for (Node<E> x = head; x != null; x = x.next) {
        Node<E> nextNode = x.next;

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

        x = nextNode;
    }

    head = tail = null;
    size = 0;
}

---

<부가 목록>

 

clone, toArray, sort 메소드 구현

 

SinglyLinkedList 와 모두 동일하다.

---

정리

 

양방향 연결리스트의 경우 단방향 연결리스트와 비교해서 tail 부터도 검색을 할 수 있다는 점에서 조금이나마 검색(색인) 능력이 향상되었다는 것이 핵심이다. 자바 내부에 구현된 것은 자료 개수에 따라 Tree 혹은 LinkedList 구조로 동적으로 변환하면서 자료를 효율적으로 관리한다.