개요

자바에서 재공하는 List 중 하나인 LinkedList를 직접 구현하며 작동 원리를 살펴보고, ArrayList와 LinkedList의 장단점을 비교하여 각 리스트의 특성에 대해 알아보자.

ArrayList의 단점과 Node

ArrayList의 단점

공간낭비

ArrayList는 배열을 사용하여 데이터를 저장함으로 배열을 미리 확보해야만 한다. 만약 데이터가 배열의 크기만큼 사용되지 않는다면 나머지 공간은 낭비가 된다.

배열 중간에 데이터 삽입, 삭제

배열 중간에 값을 삽입하거나 삭제하려면 해당 위치 이후의 요소들을 한 칸씩 이동시켜야 한다. 특히 index가 앞쪽일수록 더 많은 데이터를 이동해야 하므로 성능이 좋지 않다.

Node

ArrayList와 달리 LinkedList는 배열을 사용하지 않고, Node라는 객체를 사용하여 데이터들을 관리한다. Node를 사용함으로써 낭비되는 메모리 없이 필요한 만큼의 메모리를 사용할 수 있고 앞이나 중간의 데이터를 삽입, 삭제할때 효율적으로 처리할 수 있다.

public class Node {
    String item;     // 저장할 데이터
    Node next;      // 다음 노드를 가리키는 참조
}

• Node는 저장할 값과 다음으로 연결할 Node의 참조값을 가진다.

Node 데이터 추가 - 마지막 위치에 Node 추가

Node에 값을 추가할 때는 새로운 Node를 생성한 뒤 next에 연결할 노드를 할당하면 된다. 이 과정을 코드로 표현하면 다음과 같다.

public class NodeTest {

    public static void main(String[] args) {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");

        nodeA.next = nodeB;
        nodeB.next = nodeC;

        System.out.println("nodeA = " + nodeA);
    }

    static class Node {
        String node;
        Node next;

        public Node(String node) {
            this.node = node;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            Node x = this;
            while (x != null) {
                sb.append(x.node);
                if (x.next != null) {
                    sb.append(", ");
                }
                x = x.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

// 결과 [A, B, C]

결과를 확인해보면 A -> B -> C 순서로 연결되어있는 것을 확인할 수 있다. 또한 필요한 만큼의 Node(3개)만 생성했기 때문에 메모리의 낭비 또한 일어나지 않는 것을 알 수 있다.

Node 데이터 추가 - 중간 위치에 Node 추가

기존에 A → B → C로 연결되어 있는 구조에서 A와 B 사이에 새로운 Node D를 추가하고 싶다면 연결 순서를 조정해 A → D → B → C 형태로 만들어야 한다. 이를 위해서는 새로 만든 D의 next를 B로 설정하고 A의 next를 D로 변경하면 된다. 이 과정을 코드로 표현하면 다음과 같다.

public class NodeTest {

    public static void main(String[] args) {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");

        nodeA.next = nodeB;
        nodeB.next = nodeC;

        System.out.println(nodeA);

        Node nodeD = new Node("D");
        nodeD.next = nodeB;
        nodeA.next = nodeD;

        System.out.println(nodeA);
    }

    static class Node {
        String node;
        Node next;

        public Node(String node) {
            this.node = node;
        }

       @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            Node x = this;
            while (x != null) {
                sb.append(x.node);
                if (x.next != null) {
                    sb.append(", ");
                }
                x = x.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

// 결과
// [A, B, C]
// [A, D, B, C]

ArrayList의 경우 중간에 값을 삽입하려면 해당 위치 이후의 요소들을 한 칸씩 이동시켜야 했지만 Node를 사용하여 값을 삽입하는 경우 next의 참조값만 바꿔주면 되는 것을 확인할 수 있다. 삭제도 마찬가지로 next의 참조값만 변경해 주면 될 것이다.

Node 데이터 삭제 - 중간 위치의 Node 제거

public class NodeTest {

    public static void main(String[] args) {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");

        nodeA.next = nodeB;
        nodeB.next = nodeC;

        System.out.println(nodeA);
        nodeA.next = nodeC;
        System.out.println(nodeA);
    }

    static class Node {
        String node;
        Node next;

        public Node(String node) {
            this.node = node;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            Node x = this;
            while (x != null) {
                sb.append(x.node);
                if (x.next != null) {
                    sb.append(", ");
                }
                x = x.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

중간 Node값을 제거하는 방법도 추가와 마찬가지로 간단하다. node의 next를 기존 nodeB에서 nodeC로 변경만 하면 된다. 해당 코드는 중간 위치의 Node만 제거했는데 마지막 위치의 Node 제거도 위와 같은 방법으로 제거하면 된다.

MyLinkedList 구현

앞서 살펴본 코드에서 Node는 데이터를 저장하고 다음 노드를 가리키며 서로 연결(Link) 된 구조임을 확인할 수 있었다. 이렇게 각각의 Node를 연결(Link)하여 구성한 자료구조를 LinkedList라고 한다.

그럼 이제 Node의 코드를 확용하여 MyLinkedList를 구현해 보자

1단계 : 기본 구조 정의

public class MyLinkedList<E> {

    private Node<E> first;
    private Node<E> last;

    private int size = 0;

    public void add(E e) {
        Node<E> newNode = new Node<>(e);

        if (size == 0) {
            first = newNode;
            last = newNode;
        } else {
            newNode.prev = last;
            last.next = newNode;
            last = newNode;
        }
        size++;
    }

    public E set(int index, E e) {
        Node<E> node = getNode(index);
        E oldItem = node.item;
        node.item = e;
        return oldItem;
    }

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

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

    public int size() {
        return size;
    }

    private Node<E> getNode(int index) {
        Node<E> x;

        if (index <= size / 2) {
            x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        }
        x = last;
        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        }
        return x;
    }

    @Override
    public String toString() {
        return size == 0 ? "[]" : first.toString();
    }

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

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

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");

            Node<E> x = this;
            while (x != null) {
                sb.append(x.item);
                if (x.next != null) {
                    sb.append(", ");
                }
                x = x.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

• MyLinkedList는 제네릭 타입을 사용하여 다양한 타입의 데이터를 저장할 수 있도록 설계되었다.
• first와 last 필드를 통해 첫 번째와 마지막 노드에 직접 접근할 수 있다.
• 중간 위치의 노드에 접근할 경우 first 노드부터 next를 따라가거나 last 노드부터 prev를 따라가며 탐색할 수 있다.
• size 필드를 통해 현재 리스트의 크기를 확인할 수 있다.

add(E e)

• 마지막에 데이터를 추가한다.
• list의 크기가 0이면 first와 last에 새로운 노드를 연결한다.
• list의 크기가 0이 아니라면 새로운 노드의 prev 필드에 last를 넣고,
• last.next에 새로운 노드를 넣는다.
• 마지막으로 last에 새로운 노드를 넣는다.

set(int index, E e)

• 특정 위치에 있는 데이터를 찾아서 변경하고 기존 값을 반환한다.
• getNode(index) 를 통해 특정 위치에 있는 노드를 찾고, 그 노드에 있는 item 을 변경한다.

indexOf(E e)

• 처음부터 모든 노드를 순회하며 일치하는 값을 찾고 처음으로 일치하는 index를 반환한다.
• 일치하는 하는 값이 없을 경우 -1을 반환한다.

get(int index)

• 특정 위치에 있는 데이터를 반환한다.
• getNode(int index)를 통해 특정 위치의 노드를 찾고, 해당 노드의 item을 반환한다.

size()

• 현재 list의 크기를 반환한다.

getNode(int index)

• 특정 위치에 있는 데이터를 반환한다.
• index가 size / 2 보다 크면 마지막부터 순회하고, 작다면 처음부터 순회하여 노드를 찾는다.

Node 필드를 살펴보면, 기존에는 없던 prev 필드가 새롭게 추가되었다. 기존의 Node는 단방향 연결만 지원했지만, prev 필드를 추가함으로써 양방향 연결이 가능하도록 개선하였다. 이를 통해
getNode(int index) 메서드 실행 시 인덱스에 따라 앞 또는 뒤에서부터 탐색할 수 있어 탐색 성능을 향상시켰다. 위 코드의 흐름을 그림으로 표현하면 아래와 같다.

2단계 : 중간 위치에 데이터 삽입, 삭제

1단계에서 작성한 코드는 index 위치에 데이털를 삽입하거나 삭제하는 메서드가 없다. 특정위치에 데이터를 삽입하거나 삭제하는 메서드를 추가해보자

public void add(int index, E e) {
    Node<E> newNode = new Node<>(e);

    if (index == 0) {
        newNode.next = first;
        if (first != null) {
            first.prev = newNode;
        } else {
            last = newNode;
        }
        first = newNode;
    } else if (index == size) {
        newNode.prev = last;
        last.next = newNode;
        last = newNode;
    } else {
        Node<E> prevNode = getNode(index - 1);
        Node<E> nextNode = prevNode.next;

        prevNode.next = newNode;
        nextNode.prev = newNode;

        newNode.prev = prevNode;
        newNode.next = nextNode;
    }
    size++;
}

public E remove(int index) {
    Node<E> removeNode = getNode(index);
    E removeItem = removeNode.item;

    if (index == 0) {
        first = first.next;
        if (first != null) {
            first.prev = null;
        } else {
            last = null;
        }
    } else if (index + 1 == size) {
        last = last.prev;
        if (last != null) {
            last.next = null;
        } else {
            first = null;
        }
    } else {
        Node<E> prevNode = removeNode.prev;
        Node<E> nextNode = removeNode.next;

        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    size--;

    removeNode.item = null;
    removeNode.prev = null;
    removeNode.next = null;

    return removeItem;
}

add(int index, E e)

• 특정 index에 데이터를 추가한다.
• index가 0이라면 맨 앞에 삽입한다.
  • 기존 노드를 밀어내고 새 노드를 first로 갱신한다.
  • 리스트가 비어있을 경우엔 last도 함께 새 노드로 지정한다.
• index가 size와 같다면 마지막에 삽입한다.
  • 기존 last 노드 뒤에 새 노드를 연결하고 last를 갱신한다.
• index가 중간 위치일 경우
  • index - 1번째 노드(prevNode)와 그 다음 노드(nextNode)를 찾고,
  • 그 사이에 새 노드를 끼워 넣는다.
  • 새 노드가 중간에 끼어들 수 있도록 prev, next 포인터를 조정한다.

remove(int index)

• 특정 index에 데이터를 제거하고 제거된 값을 반환한다.
• getNode(index)를 통해 삭제할 노드를 가져온다.
• index가 0이라면 맨 앞의 노드를 제거한다.
  • first를 한 칸 옮기고, 새 first의 prev를 null로 만든다.
  • 삭제 후 비어 있는 경우엔 last도 함께 null로 설정한다.
• index + 1의 값이 size와 같으면 마지막 노드를 제거한다.
  • last를 한 칸 앞당기고, 새 last의 next를 null로 만든다.
  • 삭제 후 비어 있는 경우엔 first도 함께 null로 설정한다.
• index가 중간 위치일 경우
  • 해당 노드의 앞뒤 노드를 찾아 서로 연결시킨다.
  • 즉 prevNode.next가 nextNode를 가리키고, nextNode.prev가 prevNode를 가리키게 만든다.
• 마지막으로 삭제된 노드는 참조를 모두 끊어 가비지 컬렉터가 수거할 수 있도록 정리한다.

3단계 : 최종 코드

public class MyLinkedList<E> {

    private Node<E> first;
    private Node<E> last;

    private int size = 0;

    public void add(E e) {
        Node<E> newNode = new Node<>(e);

        if (size == 0) {
            first = newNode;
            last = newNode;
        } else {
            newNode.prev = last;
            last.next = newNode;
            last = newNode;
        }
        size++;
    }

    public void add(int index, E e) {
        Node<E> newNode = new Node<>(e);

        if (index == 0) {
            newNode.next = first;
            if (first != null) {
                first.prev = newNode;
            } else {
                last = newNode;
            }
            first = newNode;
        } else if (index == size) {
            newNode.prev = last;
            last.next = newNode;
            last = newNode;
        } else {
            Node<E> prevNode = getNode(index - 1);
            Node<E> nextNode = prevNode.next;

            prevNode.next = newNode;
            nextNode.prev = newNode;

            newNode.prev = prevNode;
            newNode.next = nextNode;
        }
        size++;
    }

    public E remove(int index) {
        Node<E> removeNode = getNode(index);
        E removeItem = removeNode.item;

        if (index == 0) {
            first = first.next;
            if (first != null) {
                first.prev = null;
            } else {
                last = null;
            }
        } else if (index + 1 == size) {
            last = last.prev;
            if (last != null) {
                last.next = null;
            } else {
                first = null;
            }
        } else {
            Node<E> prevNode = removeNode.prev;
            Node<E> nextNode = removeNode.next;

            prevNode.next = nextNode;
            nextNode.prev = prevNode;
        }

        size--;

        removeNode.item = null;
        removeNode.prev = null;
        removeNode.next = null;

        return removeItem;
    }

    public E set(int index, E e) {
        Node<E> node = getNode(index);
        E oldItem = node.item;
        node.item = e;
        return oldItem;
    }

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

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

    public int size() {
        return size;
    }

    private Node<E> getNode(int index) {
        Node<E> x;

        if (index <= size / 2) {
            x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        }
        x = last;
        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        }
        return x;
    }

    @Override
    public String toString() {
        return size == 0 ? "[]" : first.toString();
    }

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

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

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");

            Node<E> x = this;
            while (x != null) {
                sb.append(x.item);
                if (x.next != null) {
                    sb.append(", ");
                }
                x = x.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

• 앞선 1단계와 2단계의 코드를 합치면 위 코드와 같다.
• add(E e)와 add(int index, E e)를 통해 마지막과 특정 위치에 데이터를 추가할 수 있다.
• remove(int index)를 통해 특정 위치의 데이터를 제거할 수 있다.
• get(int index)와 indexOf(E e)를 통해 특정 인덱스의 값과 특정 값의 인덱스를 가져올 수 있다.
• set(int index, E e)를 통해 특정 인덱스의 데이터를 변경할 수 있다.

MyLinkedList를 직접 구현하며 자바의 LinkedList가 어떻게 동작하는지 알아봤다. 이번엔 자바 LinkedList의 특징들을 살펴보자.

LinkedList 특징

수정은 빠르나 접근이 느리다

• 조회: O(n)

  • LinkedList에서 특정 index의 값을 찾기위해서는 처음이나 끝에서부터 차례대로 노드를 따라가야하기 때문에 시간복잡도는 O(n)이다.
  • 만약 데이터가 처음이나 마지막에 위치하는 경우 O(1)의 시간복잡도를 가질 수 있다.

• 수정: O(1)

  • 한번 노드를 찾아내면 해당 노드의 item 값을 바꾸는 것은 단순한 참조 변경이기 때문에 시간 복잡도는 O(1)이다.
  • 하지만 수정을 위해 값을 찾아야 함으로 평균적으로 O(n) 만큼의 시간이 추가된다.

• 삽입, 삭제: O(1)

  • 이전, 다음 노드의 연결만 바꿔주면 되므로 삽입과 삭제는 O(1)로 처리된다.
  • 하지만 삭제도 마찬가지로 값을 찾기 위한 조회가 필요함으로 O(n) 만큼이 시간이 추가된다.

LinkedList는 ArrayList와 달리 값을 삽입하거나 삭제하는 연산 자체는 빠르지만 해당 위치를 찾기 위한 조회 과정에는 더 많은 시간이 소요되는 것을 확인할 수 있다.

ArrayList vs LinkedList

ArrayList와 LinkedList를 구현해보며 각 리스트의 동작방식에 대해 알아봤다. 그럼 궁금한게 있다. 과연 둘중에 어떤 list를 사용해야되는 것일까? 이번에는 ArrayList와 LinkedList의 성능을 비교해보며어떤 list를 선택하는 것이 적절한지 알아보자.

데이터 추가, 삭제

public class ArrayVsLinked {
    public static void main(String[] args) {
        int size = 100_000;

        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();

        System.out.println("=== arrayList ===");
        addFirst(arrayList, size);
        addMid(arrayList, size);
        addLast(arrayList, size);
        System.out.println();

        System.out.println("=== linkedList ===");
        addFirst(linkedList, size);
        addMid(linkedList, size);
        addLast(linkedList, size);
    }

    static void addFirst(List<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(0, i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("앞에 데이터 추가(삭제), 반복 횟수: " + size + ", 경과 시간" + (endTime - startTime) + "ms");
    }

    static void addMid(List<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i / 2);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("중간에 데이터 추가(삭제), 반복 횟수: " + size + ", 경과 시간" + (endTime - startTime) + "ms");
    }

    static void addLast(List<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("마지막에 데이터 추가(삭제), 반복 횟수: " + size + ", 경과 시간" + (endTime - startTime) + "ms");
    }
}

=== arrayList ===
앞에 데이터 추가(삭제), 반복 횟수: 100000, 경과 시간487ms
중간에 데이터 추가(삭제), 반복 횟수: 100000, 경과 시간3ms
마지막에 데이터 추가(삭제), 반복 횟수: 100000, 경과 시간3ms

=== linkedList ===
앞에 데이터 추가(삭제), 반복 횟수: 100000, 경과 시간3ms
중간에 데이터 추가(삭제), 반복 횟수: 100000, 경과 시간2ms
마지막에 데이터 추가(삭제), 반복 횟수: 100000, 경과 시간2ms

추가, 삭제

• 추가와 삭제 유사한 방식으로 동작하므로추가 작업만을 측정하였다.

• ArrayList: 인덱스를 통해 추가나 삭제할 위치를 O(1)로 빠르게 찾지만 추가나 삭제 이후에 데이터를 한칸씩 밀어야 한다. 이 부분에서 O(n)의 시간이 소요된다.

• LinkedList: 인덱스를 통해 추가나 삭제할 위치를 O(n)이 걸리지만 실제 데이터의 추가 및 삭제는 참조만 변경하면 되므로 O(1)의 시간이 소요된다.

앞에 추가/삭제

• ArrayList : 추가, 삭제할 위치를 찾는데 O(1)의 시간이 걸렸고, 데이터를 이동 시키는데 O(n)이 걸렸다. 그래서 최종적으로 O(n)의 시간이 걸렸다.

• LinkedList : 추가, 삭제할 위치를 찾는데 O(1)의 시간이 걸렸고, 데이터를 이동 시키는데 O(1)이 걸린다. 그래서 최종적으로 O(1)의 시간이 걸렸다.

중간에 추가/삭제

• ArrayList : 추가, 삭제할 위치를 찾는데 O(1)의 시간이 걸렸고, 데이터를 이동 시키는데 O(n / 2)이 걸렸다. 그래서 최종적으로 O(n)의 시간이 걸렸다.

• LinkedList : 추가, 삭제할 위치를 찾는데 O(n /2)의 시간이 걸렸고, 데이터를 이동 시키는데 O(1)이 걸렸다. 그래서 최종적으로 O(n)의 시간이 걸렸다.

마지막에 추가/삭제

• ArrayList : 추가, 삭제할 위치를 찾는데 O(1)의 시간이 걸렸고, 데이터를 이동시킬 필요가 없음으로 최종적으로 O(1)의 시간이 걸렸다.

• LinkedList : 추가, 삭제할 위치를 찾는데 O(1)의 시간이 걸렸고, 노드를 변경하는데 O(1)의 시간이 걸렸다. 그래서 최종적으로 O(1)의 시간이 걸렸다.

테스트 결과를 확인해보면 중간과 마지막에 데이터를 추가, 삭제하는 경우 시간이 비슷하지만 앞부분에 데이터를 추가, 삭제하는경우 linekdList가 월등하게 빠른 속도를 내는 것을 확인할 수 있다.

데이터 조회

public class ArrayVsLinked {
    public static void main(String[] args) {
        int size = 100_000;

        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();

        IntStream.range(0, size)
                .forEach(arrayList::add);

        IntStream.range(0, size)
                .forEach(linkedList::add);

        System.out.println("=== arrayList index 조회===");
        searchIndex(arrayList, size, 0);
        searchIndex(arrayList, size, size / 2);
        searchIndex(arrayList, size, size - 1);
        System.out.println();

        System.out.println("=== linkedList index 조회===");
        searchIndex(linkedList, size, 0);
        searchIndex(linkedList, size, size / 2);
        searchIndex(linkedList, size, size - 1);
        System.out.println();

        System.out.println("=== arrayList 검색===");
        search(linkedList, size, 0);
        search(linkedList, size, size / 2);
        search(linkedList, size, size - 1);
        System.out.println();

        System.out.println("=== linkedList 검색===");
        search(LinkedList, size, 0);
        search(LinkedList, size, size / 2);
        search(LinkedList, size, size - 1);
    }

    static void searchIndex(List<Integer> list, int loop, int index) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.get(index);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("index: " + index + ", 반복 : " + loop + ", 경과 시간 : " + (endTime - startTime) + "ms");
    }

    static void search(List<Integer> list, int loop, int findValue) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.indexOf(findValue);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("findValue: " + findValue + ", 반복 : " + loop + ", 경과 시간 : " + (endTime - startTime) + "ms");
    }
}

=== arrayList index 조회===
index: 0, 반복 : 100000, 경과 시간 : 3ms
index: 50000, 반복 : 100000, 경과 시간 : 1ms
index: 99999, 반복 : 100000, 경과 시간 : 2ms

=== LinkedList index 조회===
index: 0, 반복 : 100000, 경과 시간 : 3ms
index: 50000, 반복 : 100000, 경과 시간 : 7963ms
index: 99999, 반복 : 100000, 경과 시간 : 0ms

=== arrayList 검색===
findValue: 0, 반복 : 100000, 경과 시간 : 4ms
findValue: 50000, 반복 : 100000, 경과 시간 : 9162ms
findValue: 99999, 반복 : 100000, 경과 시간 : 19519ms

=== linkedList 검색===
findValue: 0, 반복 : 100000, 경과 시간 : 0ms
findValue: 50000, 반복 : 100000, 경과 시간 : 9111ms
findValue: 99999, 반복 : 100000, 경과 시간 : 19681ms

• index를 통한 조회와 indexOf() 메서드를 사용하여 검색 2가지를 테스트를 진행하였다.
• 각 테스트별로 처음, 중간, 마지막 데이터를 조회하는 시간을 측정하였다.

인덱스 조회

• ArrayList : 인덱스를 사용해서 값을 조회함으로 O(1)의 시간이 소요된다.
• LinkedList : 노드를 인덱스 수 만큼 이동해야함으로 O(n)의 시간이 소요된다.

검색

• ArrayList : 데이터를 찾을때 까지 순회함으로 O(n)의 시간이 소요된다.
• LinkedList : 데이터를 찾을때 까지 순회함으로 O(n)의 시간이 소요된다.

테스트 결과를 확인해보면, 인덱스를 통한 조회에서는 ArrayList가 압도적으로 빠른 성능을 보이는 것을 확인할 수 있다. 반면, 검색의 경우 두 리스트 모두 원하는 데이터를 찾을 때까지 순차적으로 순회하기 때문에 성능 차이가 거의 없다.

결론

그렇다면 ArrayList와 LinkedList 중 어떤 것을 사용해야 할까? 결론적으로 대부분의 경우 ArrayList를 사용하는 것이 더 적합하다. 이유는 다음과 같다.

• ArrayList는 인덱스를 통한 조회 속도가 매우 빠르며, 메모리 구조가 연속적이기 때문에 CPU 캐시 효율도 좋다.

• 삽입과 삭제에서 O(n)이 소요되지만, 실제로는 대부분의 삽입, 삭제가 리스트의 끝에서 일어나므로 성능 차이가 크지 않다.

• 반면 LinkedList는 삽입과 삭제 자체는 빠르지만, 원하는 위치까지 접근하는 데 시간이 오래 걸리기 때문에 조회나 중간 위치 조작이 많은 경우에는 오히려 비효율적이다.

앞쪽에 자주 추가하거나 삭제해야 하는 특수한 상황이 아니라면 ArrayList가 성능과 사용성 측면에서 더 유리하다.

정리

• Node는 저장할 데이터와 다른 Node를 연결하는 구조를 지닌다.
• LinkedList는 각각의 Node를 연결하여 구성한 자료구조이다.
• LinkedList의 경우 삽입, 삭제는 빠르나 해당 위치를 찾는 속도가 느리다.
• List의 앞쪽에 데이터를 추가, 삭제하는 특별한 상황이 아니라면 ArrayList가 성능적인 면에서 LinkedList보다 유리하다.

제가 공부한 내용을 정리한 것이라 틀린 내용이 있을 수 있습니다. 보시고 틀린 내용을 알려주시면 감사하겠습니다 😀

참고자료
김영한의 실전 자바 - 중급 2편