4. 컬렉션 프레임워크 - LinkedList

노드와 연결

배열 리스트의 단점

배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리한다. 이로 인해 다음과 같은 단점을 가진다.

• 배열의 사용하지 않는 공간 낭비

  • 배열은 초기화 시 사용할 공간을 지정해야 한다.

• 배열의 중간 데이터 추가

  • 배열의 중간에 데이터를 추가할 시 중간 뒤 데이터를 이동시켜야 한다.

  • 이로 인해 성능이 좋지 않다.

노드와 연결

낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때 효율적인 자료구조가 있는데, 바로 노드를 만들고 각 노드를 서로 연결하는 방식이다.

노드 클래스

public class Node {
      Object item;      // 각 노드에 추가할 item
      Node next;        // 다음 노드 레퍼런스 
}

정리

• 노드는 내부에 데이터와 다음 노드에 대한 레퍼런스를 가지고 있다.

• 지금까지 설명한 구조는 각각의 노드가 참조를 통해 연결(Link, 링크) 되어 있다.

• 데이터를 추가할 때 동적으로 필요한 만큼의 노드만 만들어서 연결하면 된다. 따라서 배열과 다르게 메모리를 낭비하지 않는다.

  • 물론 next 필드를 통해 참조값을 보관해야하기 때문에, 배열과 비교해서 추가적인 메모리 낭비도 발생한다.

• 이렇게 각각의 노드를 연결해서 사용하는 자료 구조로 리스트를 만들 수 있는데, 이것을 연결 리스트라고 한다.

직접 구현하는 연결 리스트1 - 시작

연결 리스트는 배열 리스트의 단점인 메모리 낭비, 중간 위치에 데이터 추가에 대한 성능 문제를 어느 정도 극복할 수 있다.

리스트(List) 자료구조

• 순서가 있고,

• 중복을 허용하는 자료구조

우리는 앞서 MyArrayList 시리즈를 만들어보았다. 배열 리스트도, 연결 리스트도 모두 같은 리스트이다. 리스트의 내부에서 배열을 사용하는가 아니면 노드와 연결 구조를 사용하는가의 차이가 있을 뿐이다.

배열 리스트를 사용하든 연결 리스트를 사용하든 둘다 리스트 자료 구조이기 때문에 리스트를 사용하는 개발자 입장에서는 거의 비슷하게 느껴져야 한다.

구현 코드

• MyArrayListV1Main 에 있는 코드를 거의 그대로 사용했다.

• 연결 리스트는 데이터를 추가할 때 마다 동적으로 노드가 늘어나기 때문에 범위를 초과하는 문제는 발생하지 않는다.

package collection.link;

public class MyLinkedListV1 {

    private Node first;
    private int size = 0;

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

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

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

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

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

    public int indexOf(Object o) {
        int index = 0;
        for (Node 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 "MyLinkedListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }
}

package collection.link;

public class MyLinkedListMainV1 {

    public static void main(String[] args) {
        MyLinkedListV1 list = new MyLinkedListV1();
        System.out.println("==데이터 추가==");
        System.out.println(list);
        list.add("a");
        System.out.println(list);
        list.add("b");
        System.out.println(list);
        list.add("c");
        System.out.println(list);

        System.out.println("==기능 사용==");
        System.out.println("list.size() = " + list.size());
        System.out.println("list.get(1) = " + list.get(1));
        System.out.println("list.indexOf(\"c\") = " + list.indexOf("c"));
        System.out.println("list.set(2, \"z\") = " + list.set(2, "z"));
        System.out.println(list);

        System.out.println("==범위 초과==");
        list.add("d");
        System.out.println(list);
        list.add("e");
        System.out.println(list);
        list.add("f");
        System.out.println(list);
    }
}

연결 리스트와 빅오

Object get(int index)

• 특정 위치에 있는 데이터를 반환한다.

• O(n)

  • 배열은 인덱스로 원하는 데이터를 즉시 찾을 수 있다. 따라서 배열을 사용하는 배열 리스트( ArrayList ) 도 인덱스로 조회시 O(1)의 빠른 성능을 보장한다. 하지만 연결 리스트에서 사용하는 노드들은 배열이 아니다. 단지 다음 노드에 대한 참조가 있을 뿐이다. 따라서 인덱스로 원하는 위치의 데이터를 찾으려면 인덱스 숫자 만큼 다음 노드를 반복해서 찾아야 한다. 따라서 인덱스 조회 성능이 나쁘다.

  • 특정 위치의 노드를 찾는데 O(n)이 걸린다.

void add(Object e)

• 마지막에 데이터를 추가한다.

• O(n)

  • 마지막 노드를 찾는데 O(n)이 소요된다. 마지막 노드에 새로운 노드를 추가하는데 O(1)이 걸린다. 따라서 O(n)이다.

Object set(int index, Object element)

• 특정 위치에 있는 데이터를 찾아서 변경한다. 그리고 기존 값을 반환한다.

• O(n)

  • 특정 위치의 노드를 찾는데 O(n)이 걸린다.

int indexOf(Object o)

• 데이터를 검색하고, 검색된 위치를 반환한다.

• O(n)

  • 모든 노드를 순회하면서 equals() 를 사용해서 같은 데이터가 있는지 찾는다.

정리

• 연결 리스트를 통해 데이터를 추가하는 방식은 꼭 필요한 메모리만 사용한다. 따라서 배열 리스트의 단점인 메모리 낭비를 해결할 수 있었다.

  • 물론 연결을 유지하기 위한 추가 메모리가 사용되는 단점도 존재한다.

배열 리스트는 중간에 데이터를 추가하거나 삭제할 때 기존 데이터를 한 칸씩 이동해야 하는 문제가 있었다.

연결 리스트는 이 문제를 어떻게 해결하는지 알아보자.

직접 구현하는 연결 리스트2 - 추가와 삭제1

구현 코드

package collection.link;

public class MyLinkedListV2 {

    private Node first;
    private int size = 0;

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

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

    // 추가 코드
    public void add(int index, Object e) {
        Node newNode = new Node(e);
        if (index == 0) {
            newNode.next = first;
            first = newNode;
        } else {
            Node prev = getNode(index - 1);
            newNode.next = prev.next;
            prev.next = newNode;
        }
        size++;
    }

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

    // 추가 코드
    public Object remove(int index) {
        Node removeNode = getNode(index);
        Object removeItem = removeNode.item;
        if (index == 0) {
            first = removeNode.next;
        } else {
            Node prev = getNode(index - 1);
            prev.next = removeNode.next;
        }
        removeNode.item = null;
        removeNode.next = null;
        size--;
        return removeItem;
    }

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

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

    public int indexOf(Object o) {
        int index = 0;
        for (Node 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 "MyLinkedListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }
}

package collection.link;

public class MyLinkedListMainV2 {

    public static void main(String[] args) {
        MyLinkedListV2 list = new MyLinkedListV2();
        System.out.println("==데이터 추가==");
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);

        // 첫 번째 항목에 추가 삭제
        System.out.println("첫 번째 항목에 추가 삭제");
        list.add(0, "d");
        System.out.println(list);
        list.remove(0);
        System.out.println(list);

        // 중간 항목에 추가, 삭제
        list.add(1, "e");
        System.out.println(list);
        list.remove(1);
        System.out.println(list);
    }
}

정리

직접 만든 배열 리스트와 연결 리스트의 성능 비교표

• 배열 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(1) 로 빠르게 찾지만, 삭제 이후에 데이터를 한 칸씩 밀어야 한다. 이 부분이 O(n)으로 오래 걸린다.

• 하지만 연결 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(n) 로 느리게 찾지만, 찾은 이후에는 일부 노드의 참조값만 변경하면 되므로 이 부분이 O(1) 로 빠르다.

• 앞에 추가하는 경우

  • 배열 리스트: 데이터를 앞쪽에 추가하는 경우 모든 데이터를 오른쪽으로 한 칸씩 밀어야 한다. O(n)

  • 연결 리스트: 데이터를 앞쪽에 추가하는 경우 일부 노드의 참조만 변경하면 된다. O(1)

• 중간에 데이터를 추가하는 경우

  • 배열 리스트 : 중간에 데이터를 추가하는 경우 모든 데이터를 오른쪽으로 한 칸씩 밀어야 한다. O(n)

  • 연결 리스트 :

    • 중간에 데이터를 추가하는 경우 중간 노드를 찾는데 O(n) 의 시간이 걸린다.

    • 데이터를 추가하는 경우 일부 노드의 참조만 변경하면 된다. O(1)

    • 따라서 O(n)의 성능을 제공한다.

• 마지막에 데이터를 추가하는 경우

  • 배열 리스트

    • 인덱스로 마지막 위치를 바로 찾을 수 있다. O(1)

    • 데이터를 마지막에 추가하는 경우 데이터를 이동하지 않아도 된다. O(1)

    • 따라서 O(1)의 성능을 제공한다.

  • 연결 리스트

    • 노드를 마지막까지 순회해야 마지막 노드를 찾을 수 있다. 따라서 마지막 노드를 찾는데 O(n)의 시간이 걸린다.

    • 데이터를 추가하는 경우 일부 노드의 참조만 변경하면 된다. O(1)

    • 따라서 O(n)의 성능을 제공한다.

배열 리스트 vs 연결 리스트 사용 (이론적으로!)

• 데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열 리스트가 보통 더 좋은 성능을 제공한다.

• 앞쪽의 데이터를 추가하거나 삭제할 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공한다.

직접 구현하는 연결 리스트4 - 제네릭 도입

지금까지 만든 연결 리스트에 제네릭을 도입해서 타입 안정성을 높여보자.

추가로 여기서 사용하는 Node 는 외부에서 사용되는 것이 아니라 연결 리스트 내부에서만 사용된다. 따라서 중첩 클래스로 만들자.

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(first);
            lastNode.next = newNode;
        }
        size++;
    }

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

    // 추가 코드
    public void add(int index, E e) {
        Node<E> newNode = new Node<>(e);
        if (index == 0) {
            newNode.next = first;
            first = newNode;
        } else {
            Node<E> prev = getNode(index - 1);
            newNode.next = prev.next;
            prev.next = newNode;
        }
        size++;
    }

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

    // 추가 코드
    public E remove(int index) {
        Node<E> removeNode = getNode(index);
        E removeItem = 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 removeItem;
    }

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

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

    public int indexOf(Object 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 "MyLinkedListV1{" +
                "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;
            sb.append("[");
            while (x != null) {
                sb.append(x.item);
                if (x.next != null) {
                    sb.append("->");
                }
                x = x.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

package collection.link;

public class MyLinkedListMainV3 {

    public static void main(String[] args) {
        MyLinkedListV3<String> list = new MyLinkedListV3<>();
        System.out.println("==데이터 추가==");
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);

        // 첫 번째 항목에 추가 삭제
        System.out.println("첫 번째 항목에 추가 삭제");
        list.add(0, "d");
        System.out.println(list);
        list.remove(0);
        System.out.println(list);

        // 중간 항목에 추가, 삭제
        list.add(1, "e");
        System.out.println(list);
        list.remove(1);
        System.out.println(list);
    }
}