Linked List

데이터의 추가나 삭제 시 일어나는 많은 데이터 이동은 배열의 단점이다. 또한 배열은 미리 메모리 공간을 고정적으로 확보해 놓아야 하는 단점이 있었다. 이러한 단점을 동적인 메모리 공간 점유 아이디어로 해결한 것이 ArrayList였다.

반면, LinkedList는 노드 간의 연결이라는 개념을 통해, 동적 메모리 점유 외에도 다른 장점을 제시한다. 물론, 이 방식에도 파생되는 단점이 존재한다.

노드 간의 연결을 사용하면 낭비되는 메모리 없이 필요한 만큼만 메모리를 확보해 사용할 수 있다. 또한, 앞이나 중간에 데이터를 추가하거나 삭제할 때 더 효율적이다. 하지만, 이러한 방식은 직접 접근이 필요할 때 성능이 떨어질 수 있다는 단점이 있다.

// Node Class
public class Node {
    Object item;
    Node next;

    public Node(Object item) {
        this.item = item;
    }

간단하게 구현된 위의 노드는 item에 배열처럼 데이터가 들어가며, next는 다음 인덱스에 해당하는 노드를 가리킨다. 만약 다음 인덱스가 존재하지 않으면, 해당 next는 null로 초기화된다. 즉, null인 노드는 해당 LinkedList에서 가장 마지막 부분을 나타낸다.

장점

LinkedList의 장점은 "조회"를 제외한 추가나 삭제의 용이함에 있다. 이 말을 이해하려면 이전의 배열이나 배열리스트에서 데이터를 추가하거나 삭제할 때의 과정을 떠올려보자. 배열에서 예를 들어, index=k에 데이터를 추가하려면, 우선 그 자리를 확보하기 위해 k부터 n까지의 데이터들이 한 칸씩 옮겨져야 한다.

이 과정을 아파트 1~10단지로 비유할 수 있다. 예를 들어, 5단지에 새로운 단지를 추가하려면, 5단지는 6단지로, 6단지는 7단지로... 10단지는 11단지로 이동해야 한다. (실제로 상상해보면 말도 안 되는 일이다. 심지어 11단지는 새로운 단지를 건설해야 한다.)

버스 노선은 LinkedList처럼 작동한다.. 각 버스 정류장은 노드에 해당하고, 버스가 각 정류장을 지나가면서 다음 정류장을 가리키는 포인터가 있다. 만약 한 정류장을 추가하거나 제거하고 싶다면, 버스 노선의 중간에 해당하는 포인터만 수정하면 되므로, 버스의 이동 경로를 수정하는 데 다른 버스 정류장을 이동시키는 수고가 필요 없다는 장점이 있다..

단점

장점 부분에서 설명했던 "조회"를 제외한 추가나 삭제에서 조회 부분이 문제가 있다. LinkedList에서, 전체 단지가 10단지인 아파트 단지군이 있을 때 10단지를 가기 위해서는 1,2,3....9단지까지 포탈을 타고 이동해야 한다. 즉 ArrayList에서 배열과 동일하게 가졌던 장점인 빠른 index조회가 불가능해졌다. 이는 사실 우주였던 컨셉은 착각이었고, 마치 지하의 사일로 구조로 만들어진 것 처럼 느껴진다.
10에 해당하는 주소를 가기 위해서는 1부터 2,3,4...를 거쳐서 10까지 가야한다. 아마도 10에 해당하는 부동산이 가장 가치가 낮을 것이다...

실제로 LinkedList의 추가나 삭제는 결국 O(N)의 시간복잡도를 가진다. 이는 최악의 경우때문이다.(11단지를 만들기 위해서는 1,2,3...단지를 거쳐 10단지까지 가야 10단지의 포탈도착주소를 추가해줄 수 있기 때문이다.)

LinkedList vs ArrayList

만약 조회가 대부분이고 데이터의 변화가 거의 없다면 ArrayList가 유리할 경우가 많으며, 데이터의 변화가 많다면 LinkedList가 유리할 것이다.

Java 구현

자바의 Collection은 기존의 LinkedList를 더 개선한 양방향 연결리스트를 제공하지만, 실제로 linkedlist를 구현해본 코드는 아래와 같다.

package collection.link;

public class MyLinkedListV3 <E> {
    private Node<E> first;
    private int size = 0;

    public void add(E e) {
        Node<E> newNode = new Node(e);
        if (first == null) {
            first = newNode;
        } else {
            Node<E> lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

    public void add(E e, int index) {
        Node<E> newNode = new Node(e);
        if (index == 0) {
            newNode.next = first;
            first = newNode;
        } else {
            Node<E> prevNode = getPrevNode(index);
            Node<E> getNode = getNode(index);
            prevNode.next = newNode;
            newNode.next = getNode;
        }
        size++;
    }

    public E remove(int index) {
        Node<E> removeNode = getNode(index);
        E removedItem = removeNode.item;
        if (index == 0) {
            first = removeNode.next;
        } else {
            Node<E> prev = getNode(index - 1);
            prev.next = removeNode.next;
        }
        removeNode.item = null;
        removeNode.next = null;
        size--;
        return removedItem;
    }

    private Node getPrevNode(int index) {
        Node<E> x = first;
        for (int i=0; i < index - 1; i++) {
            x = x.next;
        }
        return x;
    }

    private Node getLastNode() {
        Node<E> x = first;
        while (x.next != null) {
            x = x.next;
        }
        return x;
    }

    public E set(int index, E element) {
        Node<E> x = getNode(index);
        E oldValue = x.item;
        x.item = element;
        return oldValue;
    }

    public E get(int index) {
        Node<E> node = getNode(index);
        return node.item;
    }

    private Node getNode(int index) {
        Node<E> x = first;
        for (int i=0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    public int indexOf(E o) {
        int index = 0;
        for (Node<E> x= first; x != null; x=x.next) {
            if (o.equals(x.item)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyLinkedListV3{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }

    private static class Node<E> {
        E item;
        Node<E> next;

        public Node(E item) {
            this.item = item;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            Node<E> x = this; // x01
            sb.append("[");
            while (x != null) {
                sb.append(x.item);
                if (x.next != null) {
                    sb.append("->");
                }
                x = x.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

이전 배열리스트 구현보다 나아진 점은 Object 타입을 코드에 넣지 않았다는 것이다. 연결된 모든 Node의 Item을 제네릭을 통해 통일성을 줄 수 있었다.