자료구조 - Doubly Linked List

Doubly Linked List

---

• 단일 연결 리스트는 하나의 노드에 데이터와 다음 노드를 가리키는 노드만을 가지고 있었다면 이중 연결 리스트는 여기서 하나더 추가되어 이전 노드를 가리키는 노드도 추가되어 있습니다.
• 이중 연결 리스트가 단일 연결 리스트에 비해 좋은 점은 검색 능력입니다. 단일 연결 리스트의 경우 N 번째에 있는 노드를 검색하기 위해서는 이전 노드를 아는 경우는 O(1)의 성능을 가지지만 이전 노드를 모르는 보통의 경우에는 N만큼을 순회해야 하기 때문에 O(n)이 소요됩니다. 하지만 이중 연결 리스트의 경우 이전 노드를 참조하는 변수를 가지고 있기 때문에 단일 연결 리스트에 비해 효율적인 탐색이 가능합니다.

 

Doubly Linked List 구현

---

💡 구현하고자 하는 메서드

• 아래 메서드는 기본적으로 구현하고자 하는 메서드입니다.

public interface List<E> {

    /**
     *  리스트의 마지막에 데이터를 추가합니다.
     */
    void add(E value);

    /**
     * 특정 인덱스에 데이터를 추가합니다.
     */
    void add(int index, E value);

    /**
     * 특정 인덱스의 위치에 있는 데이터를 삭제합니다.
     */
    void remove(int index);

    /**
     * 특정 요소를 삭제합니다.
     * 만약 동일한 데이터가 있는 경우 첫번째로 발견한 데이터를 삭제합니다.
     */
    void remove(E value);

    /**
     * 특정 인덱스에 있는 데이터를 반환합니다.
     */
    E get(int index);

    /**
     * 특정 위치에 특정 데이터로 대체합니다.
     */
    void set(int index, E value);

    /**
     * 특정 데이터가 있는지 확인합니다.
     */
    boolean contains(E value);

    /**
     * 특정 데이터가 몇번째에 위치하여 있는지 반환합니다.
     * 일치하는 요소가 없다면 -1을 반환합니다.
     */
    int indexOf(E value);

    /**
     * 리스트의 데이터 개수를 반환합니다.
     */
    int size();

    /**
     * 리스트가 비어있는지 확인합니다.
     */
    boolean isEmpty();

    /**
     * 리스트의 모든 데이터를 삭제합니다.
     */
    void clear();
}

 

💡 Node 클래스

• Node 클래스는 기본적으로 데이터를 담을 변수 E와 다음 노드의 주소를 가리키는 next, 이전 노드를 가리키는 prev 변수를 가지고 있습니다.

public class Node<E> {

    E data;
    Node<E> next; // 다음 노드를 가리키는 변수
    Node<E> prev; // 이전 노드를 가리키는 변수

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

 

💡 LinkedList  클래스 add 함수

• 하나씩 파악하면서 천천히 구현을 하겠습니다. 우선적으로 구현해볼것은 추가 행위를 할 수 있는 메서드입니다.

public class LinkedList<E> implements List<E> {

    private Node<E> head;
    private Node<E> tail;
    private int size;

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

        if (head != null) {
            head.prev = newNode;
        }
        if (tail == null) {
            tail = newNode;
        }
        head = newNode;
        size++;
    }

    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++;
    }

    @Override
    public void add(E value) {
        addLast(value);
    }

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

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

        if (index == size) {
            addLast(value);
            return;
        }

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

        prevNode.next = newNode;
        newNode.next = nextNode;
        nextNode.prev = newNode;
        size++;
    }

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

        // 뒤에서부터 시작
        if (index > (size / 2)) {
            Node<E> n = tail;
            for (int i = size -1; i > index; i--) {
                n = n.prev;
            }
            return n;
        } else {
            Node<E> n = head;
            for (int i = 0; i < index; i++) {
                n = n.next;
            }
            return n;
        }
    }

    public void print() {
        Node<E> next = head;

        while (next != null && next.next != null) {
            System.out.print(next.data + " -> ");
            next = next.next;
        }
        if (next != null) {
            System.out.println(next.data);
        }
    }
}

 

addFirst 메서드

• 노드를 가장 앞단에 추가하는 메서드입니다.
• 기존에 이미 head가 있다면 head의 이전(prev)에 새로 추가된 노드를 연결시켜줍니다. 
• tail이 없다면 현재 추가되는 새로운 노드가 tail이 될 수 있도록 연결시켜줍니다.
• 새로 추가된 노드 뒤에 기존 노드를 연결시켜줄 수 있도록 연결시켜줍니다. 또한 새로 추가된 노드가 head가 되도록 설정합니다.

addLast 메서드

• 새로운 노드가 가장 마지막에 추가될 수 있도록 해주는 메서드입니다.
• 현재 추가된 노드가 없다면 즉 size가 0이라면 가장 처음에 추가될 수 있도록 설정합니다.
• 기존에 노드가 존재한다면 tail의 다음 노드가 신규로 추가되는 노드로 연결될 수 있도록 합니다.
• 신규로 추가되는 노드의 이전 노드값을 기존 tail로 설정합니다. 그리고 새로추가된 신규 노드가 마지막이 될 수 있도록 tail을 수정합니다.

add 메서드

• add 메서드는 특정 위치에 데이터를 추가하는 메서드입니다.
• 추가하고자 하는 위치가 첫번째 위치라면 addFirst 메서드를 호출하여 가장 앞단에 추가될 수 있도록 합니다.
• 추가하고자 하는 위치가 가장 마지막 위치라면 addLast 메서드를 호출하여 가장 마지막단에 추가될 수 있도록 합니다.
• 그것이 아닌 중간의 위치에 추가하고자한다면 search 메서드를 통해 이전 노드를 탐색하고 치환을 사용하여 자리를 교체합니다.

 

search 메서드

• 특정 노드를 찾기 위해서는 O(n)만큼의 시간이 소요되리라 생각해서 단순히 for문을 사용하여 처음부터 특정 인덱스까지 순회하면서 노드를 찾아야겠구나 생각을 했지만 다른 블로그의 글을 보니 index의 값이 tail에 가까운지 head에 가까운지 파악하여 길이(size)를 나누어 탐색을 하셨는데 이러한 방법도 있구나 싶었습니다. 이러한 방법을 사용하면 더 효율적일거 같습니다.

// 내가 생각한 특정 인덱스의 노드 찾기
private Node<E> search(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    Node<E> node = this.head;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

// 다른 분이 생각한 특정 인덱스의 노드 찾기
private Node<E> search(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    // 뒤에서부터 시작
    if (index > (size / 2)) {
        Node<E> n = tail;
        for (int i = size -1; i > index; i--) {
            n = n.prev;
        }
        return n;
    } else {
        // 앞에서부터 시작
        Node<E> n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n;
    }
}

 

💡 LinkedList  클래스 remove 함수

public class LinkedList<E> implements List<E> {

    private Node<E> head;
    private Node<E> tail;
    private int size;

    public void removeFirst() {
        Node<E> headNode = this.head;

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

        Node<E> next = headNode.next;
        headNode.data = null;
        headNode.next = null;

        if (next != null) {
            next.prev = null;
        }
        head = next;
        size--;
    }

    @Override
    public void remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }

        if (index == 0) {
            removeFirst();
            return;
        }

        Node<E> prevNode = search(index -1); // 삭제할 노드의 이전 노드
        Node<E> removeNode = prevNode.next;  // 삭제할 노드
        Node<E> nextNode = removeNode.next;  // 삭제할 노드의 다음 노드

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

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

    @Override
    public void remove(E value) {
        Node<E> headNode = this.head;
        Node<E> removeNode = null;
        while (headNode != null) {
            if (headNode.data.equals(value)) {
                removeNode = headNode;
                break;
            }
            headNode = headNode.next;
        }
        Node<E> prevNode = removeNode.prev; // 삭제할 노드의 이전 노드
        Node<E> nextNode = removeNode.next; // 삭제할 노드의 다음 노드

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

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

 

removeFirst 메서드 

• removeFirst 메서드는 가장 앞단에 있는 데이터를 제거하는 메서드입니다. 즉 가장 앞단의 데이터를 삭제하고 앞단의 다음 노드를 head로 지정해줍니다.

 

remove(int index) 메서드 

• 특정 인덱스에 위치한 데이터를 삭제하는 메서드입니다. index가 0이라면 가장 앞단에 있는 head를 삭제하는 일이기 때문에 removeFirst 메서드를 호출합니다. indexr가 0이 아니라면 search 메서드를 사용하여 삭제할 이전 노드를 찾습니다. 
  그리고 치환을 사용하여 삭제할 노드의 이전 노드와 다음 노드를 연결시켜 줍니다. 이때 만약 삭제할 노드의 다음 노드가 없다면 삭제할 노드의 이전 노드가 마지막 노드가 될 수 있도록 tail을 설정해줍니다.

 

remove(E value) 메서드 

• 삭제할 데이터를 찾기 위해서는 모든 노드를 순회해야합니다. 이때 O(n)만큼을 순회해야 합니다. 
• 삭제할 노드를 찾았다면 삭제할 노드의 이전 노드와 다음 노드를 찾아서 치환을 시켜줍니다.
• 이때 이전 노드가 null이라면 다음 노드가 head가 될 수 있도록 설정합니다. 또한 다음 노드가 null이라면 tail이 될 수 있도록 설정해줍니다.

 

💡 LinkedList  클래스 get(int index) 함수

• 특정 인덱스의 데이터를 반환하는 get 메서드는 내부적으로 search 메서드를 사용하여 데이터를 반환합니다.

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

 

💡 LinkedList  클래스 set(int index, E value) 함수

• set 메서드는 특정 인덱스에 위치한 데이터를 새로운 데이터로 교체하는 작업입니다. 

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

 

💡 LinkedList  클래스 indexOf, lastIndexOf 함수

• indexOf의 경우 정방향으로 탐색을 하니 for 반복문을 사용하여 처음부터 순회를 시작합니다. 
• lastIndexOf의 경우 역방향으로 탐색을 하니 for 반복문을 사용하여 끝에서부터 순회를 할 수 있도록 합니다.

@Override
public int indexOf(E value) {
    int index = 0;
    Node<E> node = this.head;
    for (int i = 0; i < size; i++) {
        if (node.data.equals(value)) {
            return index;
        }
        index++;
        node = node.next;
    }
    return -1;
}

public int lastIndexOf(E value) {
    int index = 0;
    Node<E> node = this.head;
    for (int i = size; i > 0; i--) {
        if (node.data.equals(value)) {
            return index;
        }
        index++;
        node = node.next;
    }
    return -1;
}

 

💡 LinkedList  클래스 contains, size, isEmpty, clear 함수

• 아래와 같은 함수들은 기존에 만들어져 있는 함수 또는 변수를 사용하여 적용합니다.
• clear 함수의 경우 while문을 순회하면서 GC가 수거할 수 있도록 명시적으로 null 처리를 해줍니다.

@Override
public boolean contains(E value) {
    return indexOf(value) >= 0;
}
@Override
public int size() {
    return this.size;
}

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

@Override
public void clear() {
    Node<E> next = this.head;
    while (next.next != null) {
        Node<E> removeNode = next.next;
        removeNode.prev = null;
        removeNode.next = null;
        removeNode.data = null;
        next = next.next;
    }
    this.head = null;
    this.tail = null;
    this.size = 0;
}

 

 

전체적인 소스는 깃허브에 있습니다.

https://github.com/kdg0209/datastructure-study/tree/master/src/main/java/com/datastructure/study/linked_list/doubly_linked_list

 

 

참고자료)

https://st-lab.tistory.com/169