Double Linked List

• 더블 링크드리스트의 경우

앞의 노드를 가리키는 prev 부분이 추가되엇다

 

insert와 remove 연산의 달라진 부분을 위주로 기억해두자

public class MyDoubleLinkedList<E> {
    private int size = 0;
    private Node<E> firstNode = null;
    private Node<E> lastNode = null;

    //노드 생성자에 앞의 노드를 가르키는 prev가 추가되었다
    public static class Node<E> {
        E item;
        Node<E> prev;
        Node<E> next;
        Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.item = element;
            this.next = next;
        }
    }

    //맨 앞에 넣을때는 prev가 null
    private void addFirst(E element) {
        Node<E> newNode = new Node<>(null, element, firstNode);
        if (size == 0) lastNode = newNode;
        else firstNode.prev = newNode;
        firstNode = newNode;
        size++;
    }

    //맨 뒤에 넣을때는 기존과 거의 비슷하다
    public void add(E element) {
        Node<E> newNode = new Node<>(lastNode, element, null);
        if (size == 0) firstNode = newNode;
        else lastNode.next = newNode;
        lastNode = newNode;
        size++;
    }


    //get과 set은 next 노드를 타고 동작하기에 싱글링크드리스트와 동일
    public Node<E> getNode(int idx) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        Node<E> currentNode = firstNode;
        for (int i = 0; i < idx; i++)
            currentNode = currentNode.next;
        return currentNode;
    }

    public E get(int idx) {
        return getNode(idx).item;
    }

    public void set(int idx, E element) {
        Node<E> targetNode = getNode(idx);
        targetNode.item = element;
    }

    // newNode의 앞 뒤 노드를 연결하고(생성자 부분)
    // 연결된 후에 prev와 next가 newNode를 가르키게 바꿔줘야한다

    public void insert(Node<E> prevNode, E element) {
        Node<E> newNode = new Node(prevNode, element, prevNode.next);
        if (newNode.next != null) newNode.next.prev = newNode;
        prevNode.next = newNode;
        if (newNode.next == null)
            lastNode = newNode;
        size++;
    }

    //맨앞 맨뒤, prev노드를 찾은 후에 insert하는 경우 3가지

    public void insert(int idx, E element) {
        if (idx < 0 || idx > size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        if (idx == 0) addFirst(element);
        else if (idx == size) add(element);
        else insert(getNode(idx - 1), element);
    }

    public void remove(Node<E> targetNode) {
        if (targetNode.prev != null)
            targetNode.prev.next = targetNode.next;
        
        //맨 앞 노드가 타겟노드인 경우
        else firstNode = targetNode.next;

        if (targetNode.next != null)
            targetNode.next.prev = targetNode.prev;
        
        //맨 뒤 노드가 타겟노드인 경우
        else lastNode = targetNode.prev;

        //타겟 노드의 데이터와 앞뒤 가리키는 노드들을 초기화
        targetNode.item = null;
        targetNode.prev = targetNode.next = null;
        size--;
    }

    public void remove(int idx) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        remove(getNode(idx));
    }

    public Node<E> getFirstNode() {
        return firstNode;
    }

    public Node<E> getLastNode() {
        return lastNode;
    }

    public int size() {
        return size;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<E> currentNode = firstNode;
        sb.append('[');
        for(int i = 0; i < size; i++) {
            if (i > 0) sb.append(", ");
            sb.append(currentNode.item.toString());
            currentNode = currentNode.next;
        }
        sb.append(']');
        return sb.toString();
    }

    public static void main (String[] args) {
        MyDoubleLinkedList<Integer> list = new MyDoubleLinkedList<>();

        // LinkedList의 add: O(1)
        list.add(1);            // [1]
        list.add(2);            // [1, 2]
        list.add(3);            // [1, 2, 3]

        // LinkedList의 특정 위치값에 대한 add: O(N)
        list.insert(0, 4);      // [4, 1, 2, 3]
        list.insert(3, 5);      // [4, 1, 2, 5, 3]

        // LinkedList의 특정 위치값에 대한 set: O(N)
        list.set(2, -1);        // [4, 1, -1, 5, 3]
        System.out.println(list);

        // LinkedList.java는 ListIterator를 사용해 순차 탐색을 지원하지만
        // 이 클래스는 Node 접근자를 제공하여 직접 조작하는 형태로 사용합니다.
        // ListIterator와는 달리 실제 Node를 가리킵니다.
        Node<Integer> currentNode = list.getFirstNode();

        // 3칸 뒤 Node로 이동 후 현재 노드 정보를 출력하는 예제입니다.
        int currentIndex = 0;   // index: 0, value: 4
        for (int i = 0; i < 3; i++) {
            currentNode = currentNode.next;
            currentIndex++;
        }
        // index: 3, value: 5
        System.out.printf("index: %d, value: %d\n", currentIndex, currentNode.item);

        // 계속 같은 변수를 사용해 2칸 앞 원소로 이동 후 현재 노드 정보를 출력하는 예제입니다.
        for (int i = 0; i < 2; i++) {
            currentNode = currentNode.prev;
            currentIndex--;
        }
        // index: 1, value: 1
        System.out.printf("index: %d, value: %d\n", currentIndex, currentNode.item);

        // LinkedList의 특정 위치값에 대한 get: O(N)
        System.out.printf("index: %d, value: %d\n", 2, list.get(2));

        // LinkedList의 순차 접근 중 특정 노드에 대한 remove: O(1)
        list.remove(currentNode);
        System.out.println(list);   // [4, -1, 5, 3]

        // LinkedList의 특정 위치값에 대한 remove: O(N)
        list.remove(3);             // [4, -1, 5];
        int size = list.size();     // 3
        System.out.printf("Size: %d, %s", size, list);
    }
}