[Java] Doubly Linked List

✔️ 이중연결리스트(Doubly Linked List)

• 단일연결리스트는 삽입/삭제 시 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아내야 하고 역방향으로 노드 탐색이 불가함이중연결리스트는 이러한 단점을 보완
• 각 노드마다 한 개의 레퍼런스를 추가로 저장해야 한다는 단점이 있음

💡 이중연결리스트의 노드 구조
각 노드가 두 개의 레퍼런스로 각각 이전 노드와 다음 노드를 가리킴

1. 기본적인 이중연결리스트 클래스
💡 header와 trailer 초기화하는 이유
두 노드는 실제로 데이터 저장하지 않는 Dummy 노드, 빈 노드들을 의도적으로 남겨두어 리스트가 비어있는 경우가 발생하지 않게 함

public class DoublyLinkedList<E> {
    private static class Node<E> {
        private E element;
        private Node<E> prev; // 연결리스트의 이전 노드
        private Node<E> next; // 연결리스트의 다음 노드
        public Node(E e, Node<E> p, Node<E> n) {
            element = e;
            prev = p;
            next = n;
        }
        public E getElement() { return element; }
        public Node<E> getPrev() { return prev; }
        public Node<E> getNext() { return next; }
        public void setPrev(Node<E> p) { prev = p; }
        public void setNext(Node<E> n) { next = n; }
        private Node<E> header;
        private Node<E> trailer;
        private int size = 0;
        public void DoublyLinkedList() {
            header = new Node<E> (null, null, null);
            trailer = new Node<E> (null, header, null);
            header.setNext(trailer);
        }
        public int size() { return size; }
        public boolean isEmpty() { return size == 0;}
        // 첫번째 노드 값 리턴
        public E first() {
            if(isEmpty()) return null;
            return header.getNext().getElement();
        }
        // 마지막 노드 값 리턴
        public E last() {
            if(isEmpty()) return null;
            return trailer.getNext().getElement();
        }
    }
}

맨 앞에 노드 삽입

public void addFirst(E e) {
            addBetween(e, header, header.getNext());
}

맨 뒤에 노드 삽입

public void addLast(E e) {
            addBetween(e, trailer.getPrev(), trailer);
}

첫 번째 노드 삭제

public E deleteFirst() {
            if(isEmpty()) return null;
            return remove(header.getNext());
}

마지막 노드 삭제

public E deleteLast() {
            if(isEmpty()) return null;
            return remove(trailer.getPrev());
}

💡 addBetween/remove 메소드를 reuse하여 제일 앞과 뒤의 노드 추가 및 삭제 구현

💡 addBetween은 실제로는 앞 노드만 인자로 가지는 addNext로 remove는 removeNext로 바꾸는 것을 권장

두 노드 사이에 값 추가

private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
            Node<E> newest = new Node(e, predecessor, successor);
            predecessor.setNext(newest);
            successor.setPrev(newest);
            size++;
}

특정 노드 뒤의 노드 삭제

private E remove(Node<E> node) {
            Node<E> predecessor = node.getPrev();
            Node<E> successor = node.getNext();
            predecessor.setNext(successor);
            successor.setPrev(predecessor);
            size--;
            return node.getElement();
}