Doubly linkedList (이중 연결리스트) Java 구현

일단 LinkedList의 ADT부터 정의해보자.

https://www.baeldung.com/java-arraylist-linkedlist

연결된 노드들이 서로의 메모리 위치를 가리키면서 요소를 저장하고 검색해야한다. 배열이나 리스트처럼 연속된 주소에 저장되어있지 않고 노드주소들이 떨어져있기 때문에 인덱스값을 통해서 조회할 수 없어, 특정 값이나 인덱스를 조회 시에 O(N) 시간복잡도가 소요된다.

각 노드들은 두 개의 포인터(prev, next)와 데이터를 가지고, DoublyLinkedList는 맨 처음과 맨 마지막을 가리키는 포인터(head, tail)이 있다.
이 것들을 이용해서 노드를 추가 - O(1), 조회 - O(N), 삭제 - O(1) 하는 연산이 있어야 한다.

C++의 경우에는 STL의 list container가 이미 doubly-linkedlist로 작성되어 있어서 양방향 iterator로 탐색을 할 수 있다.
하지만 Java의 경우에는 컬렉션 프레임워크의 LinkedList가 single-linkedlist로 작성되어 있기 때문에 종종 직접 구현해야하는 경우가 생길 수 있다.

1. 일단 Doubly-LinkedList와 Node에 필요한 필드값을 정의해주자

public class DoublyLinkedList {
    private Node head;
    private Node tail;
    private int size = 0;

    private class Node {
        private Object data;
        private Node prev;
        private Node next;

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

2. 노드 조회, 추가 연산을 정의해보자

- 링크드리스트에 노드를 추가해야하는데, 리스트 길이와 추가하는 위치에 따라 head와 tail 주소값이 바뀔 수 있고, 노드 간 가리키는 prev, next 주소값이 바뀌어야 한다.
그래서 add(index, data), addLast(data), addFirst(data)를 정의 해주었고, 특정 인덱스까지 조회하여 주소값을 반환하는 node(index) 메서드를 정의해서 add연산 시에 이용하였다.
node1, node2가 순서대로 연결되어 있을 때 node3을 중간에 삽입한다면

-> node3.prev = node1, node3.next = node2
-> node1.next = node2, node2.prev = node3
이 되는 것이다.

Node node(int idx) {
    if(idx < size / 2) {
        Node cur = head;
        for(int i = 0; i < idx; ++i) {
            cur = cur.next;
        }
    } else {
        Node cur = tail;
        for(int i = size - 1; i > index; --i) {
            cur = cur.prev;
        }
        return cur;
    }
}

public void addFirst(Object input) {
    Node newNode = new Node(input);
    newNode.next = head;
    if(head != null) {
        head.prev = newNode;
    }
    head = newNode;
    ++size;
    if(head.next == null) {
        tail = head;
    }
}

public void addLast(Object input) {
    Node newNode = new Node(input);
    if(size == 0) {
        addFirst(input);
    } else {
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
        ++size;
    }
}

public void add(int idx, Object input) {
    if(idx == 0) addFirst(input);
    else {
        Node tmp1 = node(idx - 1);
        Node tmp2 = tmp1.next;
        Node newNode = new Node(input);

        tmp1.next = newNode;
        newNode.next = tmp2;
        if(tmp2 != null) {
            tmp2.prev = newNode;
        }
        newNode.prev = tmp1;
        ++size;
        if(newNode.next == null) {
            tail = newNode;
        }
    }
}

3. 삭제 연산을 정의해보자.

- 삭제 연산 역시 노드의 위치에 따라 head, tail 주소값을 수정해줄 수 있고, 노드 간 가리키는 주소값을 수정해줘야 한다.
3개의 노드 중에 가운데 노드가 빠진다면 첫번째와 세번째 노드가 서로를 가리키도록 수정해야한다.
따라서 node1, node2, node3이 순서대로 있을 때 node2를 삭제한다면

-> node1.next = node3, node3.prev = node1
이 되는 것이다.

public Object removeFirst() {
    Node tmp = head;
    head = tmp.next;
    Object returnData = tmp.data;
    tmp = null;
    if(head != null) {
        head.prev = null;
    }
    --size;
    return returnData;
}

public Object removeLast() {
    return remove(size - 1);
}

public Object remove(int idx) {
    if(idx == 0) return removeFirst();
    Node tmp = node(k - 1);
    Node todoDeleted = tmp.next;
    tmp.next = tmp.next.next;
    if(tmp.next != null) {
        tmp.next.prev = tmp;
    }

    Object returnData = todoDeleted.data;
    if(todoDeleted == tail) {
        tail = tmp;
    }
    todoDeleted = null;
    --size;
    return returnData;
}

4. 양방향 iterator를 이용한 조회 연산도 정의해보자.

// 합본
public class DoublyLinkedList {
    private Node head;
    private Node tail;
    private int size = 0;

    private class Node {
        private Object data;
        private Node next;
        private Node prev;

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

        public String toString() {
            return String.valueOf(this.data);
        }
    }

    public void addFirst(Object input) {
        Node newNode = new Node(input);
        newNode.next = head;
        if (head != null) {
            head.prev = newNode;
        }
        head = newNode;
        ++size;
        if (head.next == null) {
            tail = head;
        }
    }

    public void addLast(Object input) {
        Node newNode = new Node(input);
        if (size == 0) {
            addFirst(input);
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
            ++size;
        }
    }

    Node node(int index) {
        if (index < size / 2) {
            Node x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node x = tail;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    public void add(int k, Object input) {
        if (k == 0) {
            addFirst(input);
        } else {
            Node temp1 = node(k - 1);
            Node temp2 = temp1.next;
            Node newNode = new Node(input);

            temp1.next = newNode;
            newNode.next = temp2;
            if (temp2 != null) {
                temp2.prev = newNode;
            }
            newNode.prev = temp1;
            ++size;
            if (newNode.next == null) {
                tail = newNode;
            }
        }
    }

    public String toString() {
        if (head == null) {
            return "[]";
        }
        Node temp = head;
        StringBuilder sb = new StringBuilder("[");
        while (temp.next != null) {
            sb.append(temp.data).append(",");
            temp = temp.next;
        }
        sb.append(temp.data).append("]");
        return sb.toString();

    }

    public Object removeFirst() {
        Node temp = head;
        head = temp.next;
        Object returnData = temp.data;
        temp = null;
        if (head != null)
            head.prev = null;
        --size;
        return returnData;
    }

    public Object remove(int k) {
        if (k == 0) {
            return removeFirst();
        }
        Node temp = node(k - 1);
        Node todoDeleted = temp.next;
        temp.next = temp.next.next;
        if (temp.next != null) {
            temp.next.prev = temp;
        }
        Object returnData = todoDeleted.data;
        if (todoDeleted == tail) {
            tail = temp;
        }
        todoDeleted = null;
        --size;
        return returnData;
    }

    public Object removeLast() {
        return remove(size - 1);
    }

    public int size() {
        return size;
    }

    public Object get(int k) {
        Node temp = node(k);
        return temp.data;
    }

    public int indexOf(Object data) {
        Node temp = head;
        int index = 0;
        while (temp.data != data) {
            temp = temp.next;
            ++index;
            if (temp == null) {
                return -1;
            }
        }
        return index;
    }

    public ListIterator listIterator() {
        return new ListIterator();
    }

    public class ListIterator {
        private Node lastReturned;
        private Node next;
        private int nextIndex;

        ListIterator() {
            next = head;
            nextIndex = 0;
        }

        public Object next() {
            lastReturned = next;
            next = next.next;
            ++nextIndex;
            return lastReturned.data;
        }

        public boolean hasNext() {
            return nextIndex < size();
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        public Object previous() {
            if (next == null) {
                lastReturned = next = tail;
            } else {
                lastReturned = next = next.prev;
            }
            --nextIndex;
            return lastReturned.data;
        }

        public void add(Object input) {
            Node newNode = new Node(input);
            if (lastReturned == null) {
                head = newNode;
                newNode.next = next;
            } else {
                lastReturned.next = newNode;
                newNode.prev = lastReturned;
                if (next != null) {
                    newNode.next = next;
                    next.prev = newNode;
                } else {
                    tail = newNode;
                }
            }
            lastReturned = newNode;
            nextIndex++;
            size++;
        }

        public void remove() {
            if (nextIndex == 0) {
                throw new IllegalStateException();
            }
            Node n = lastReturned.next;
            Node p = lastReturned.prev;

            if (p == null) {
                head = n;
                head.prev = null;
                lastReturned = null;
            } else {
                p.next = next;
                lastReturned.prev = null;
            }

            if (n == null) {
                tail = p;
                tail.next = null;
            } else {
                n.prev = p;
            }

            if (next == null) {
                lastReturned = tail;
            } else {
                lastReturned = next.prev;
            }

            --size;
            --nextIndex;
        }
    }
}

 

- 이 개념을 이용해서 풀 수 있는 2021년 카카오 인턴쉽 코딩테스트 문제가 있어 정리해 본다. (https://ellerymoon.tistory.com/106)​