ArrayList와 LinkedList의 연산 비용

앞 글에서는 목록을 쓰는 코드가 List 인터페이스에만 의존하게 만들어, ArrayList와 LinkedList를 main에서 바꿔 끼울 수 있게 했습니다. 이제 남은 질문은 어느 쪽을 끼울 것인가입니다. 흔히 "조회가 많으면 ArrayList, 삽입과 삭제가 많으면 LinkedList"라고 외우는데, 이 규칙은 절반만 맞습니다. 연결 목록이 원소를 빠르게 끼워 넣는 것은 넣을 위치에 이미 도착해 있을 때의 이야기이고, 그 위치까지 가는 비용이 빠져 있기 때문입니다.

이 글에서는 먼저 원소 하나를 중간에 넣을 때 두 구조가 실제로 하는 일을 세어 봅니다. 그 결과를 바탕으로 표준 ArrayList와 LinkedList의 연산별 비용을 표로 정리하고, 같은 O(n)이라도 실제 무게가 다른 이유를 살펴봅니다. 이어서 비용 표를 실제 작업 부하에 맞춰 읽는 방법과, LinkedList가 정말로 유리한 경우를 정리합니다. Big-O 표기와 분할 상환 O(1)의 뜻은 배열의 조회·삽입·삭제와 시간 복잡도와 용량이 늘어나는 동적 배열 만들기에서 다룬 것을 그대로 씁니다.

인덱스 800에 원소 하나를 넣는 비용

원소가 1000개인 목록의 800번 자리에 새 원소를 넣는다고 해 봅시다. "연결 목록의 삽입은 O(1)"이라는 말만 믿으면 연결 목록 쪽이 당연히 빨라 보입니다. 다음 프로그램은 배열과 단방향 연결 목록에서 이 삽입을 실제로 수행하면서, 원소를 옮긴 횟수와 노드를 따라간 횟수를 셉니다.

public final class InsertCostCount {
    public static void main(String[] args) {
        int size = 1_000;
        int index = 800;
        insertIntoArray(size, index);
        insertIntoLinked(size, index);
    }

    private static void insertIntoArray(int size, int index) {
        int[] elements = new int[size + 1]; // 새 값이 들어갈 빈칸 하나를 남겨 둔다
        for (int i = 0; i < size; i++) {
            elements[i] = i;
        }

        int moves = 0;
        for (int i = size; i > index; i--) { // 뒤에서부터 한 칸씩 민다
            elements[i] = elements[i - 1];
            moves++;
        }
        elements[index] = -1;

        System.out.println("array: moves=" + moves + ", writes=1, around="
                + elements[index - 1] + "," + elements[index] + "," + elements[index + 1]);
    }

    private static void insertIntoLinked(int size, int index) {
        Node head = new Node(0);
        Node last = head;
        for (int i = 1; i < size; i++) {
            last.next = new Node(i);
            last = last.next;
        }

        int steps = 0;
        Node previous = head;
        for (int i = 0; i < index - 1; i++) { // index - 1번 노드까지 걸어간다
            previous = previous.next;
            steps++;
        }
        Node added = new Node(-1);
        added.next = previous.next;
        previous.next = added;

        System.out.println("linked: steps=" + steps + ", writes=2, around="
                + previous.value + "," + added.value + "," + added.next.value);
    }

    private static final class Node {
        private final int value;
        private Node next;

        Node(int value) {
            this.value = value;
        }
    }
}

array: moves=200, writes=1, around=799,-1,800
linked: steps=799, writes=2, around=799,-1,800

배열 쪽부터 보겠습니다. 0번부터 999번 칸까지 원소가 차 있으므로, 800번 칸을 비우려면 800번부터 999번까지의 원소 200개를 한 칸씩 뒤로 밀어야 합니다. 뒤에서부터 미는 이유는 배열의 조회·삽입·삭제와 시간 복잡도에서 본 것처럼, 앞에서부터 밀면 아직 옮기지 않은 값을 덮어쓰기 때문입니다. 그다음 비워 둔 800번 칸에 새 값을 한 번 씁니다. 출력의 around는 799번, 800번, 801번 칸의 값으로, 새 값 -1이 원래의 799와 800 사이에 들어갔음을 보여 줍니다.

연결 목록은 원소를 옮기지 않습니다. 그 대신 새 노드를 이어 붙일 799번 노드, 즉 넣을 자리의 바로 앞 노드를 찾아야 합니다. 노드는 인덱스로 바로 찾을 수 없으므로 head에서 next를 799번 따라갑니다. 도착한 뒤에는 새 노드의 next가 800번 노드를 가리키게 하고, 799번 노드의 next가 새 노드를 가리키게 하는 참조 쓰기 두 번으로 끝납니다. "연결 목록의 삽입은 O(1)"이라는 말은 이 마지막 두 번의 쓰기만 센 것입니다. 위치를 찾는 799번의 이동까지 세면 연결 목록의 중간 삽입도 원소 수에 비례하는 O(n)이고, 이 예에서는 오히려 배열보다 많이 움직였습니다. 두 메서드는 비용을 세는 데 집중하려고 넣을 자리의 앞에 원소가 있는 경우, 즉 index가 1 이상이고 size보다 작은 경우만 다룹니다.

넣는 위치에 따라 결과가 뒤집힌다는 점도 중요합니다. 0번 자리에 넣으면 배열은 1000개를 모두 밀어야 하지만, 연결 목록은 한 걸음도 걷지 않습니다. 새 노드가 원래의 첫 노드를 가리키게 하고 head를 새 노드로 바꾸면 끝입니다. 반대로 끝에 가까울수록 배열이 밀 원소는 줄고 단방향 연결 목록이 걸을 거리는 늘어납니다. 그래서 "삽입이 많은가"보다 "어디에 넣는가, 그 위치를 어떻게 찾는가"를 먼저 물어야 합니다.

표준 LinkedList는 양방향 연결 목록이라 사정이 조금 낫습니다. 인덱스가 앞쪽 절반에 있으면 첫 노드에서 next를 따라가고, 뒤쪽 절반에 있으면 마지막 노드에서 prev를 따라갑니다. 크기 1000인 LinkedList에서 add(800, e)를 호출하면 마지막 노드인 999번에서 출발해 prev를 199번 따라가 800번 노드에 닿고, 그 앞에 새 노드를 끼웁니다. 가장 멀리 걸어야 하는 곳은 가운데로, 약 n/2번을 걷습니다. 걷는 거리가 절반으로 줄었을 뿐 여전히 n에 비례하므로 위치를 찾는 비용은 O(n)입니다. 게다가 양방향이라서 끼울 때 새 노드의 prev와 next, 양옆 노드의 next와 prev까지 참조 4개를 고쳐야 합니다.

표준 List 구현의 연산별 비용

앞에서 본 내용을 표준 클래스의 연산으로 정리하면 다음과 같습니다. n은 목록의 원소 수, i는 인덱스입니다. LinkedList의 이동 횟수는 가까운 끝에서 출발하는 표준 구현의 값입니다.

ArrayList는 인덱스만 알면 칸의 위치를 바로 계산하므로 get과 set이 O(1)입니다. 그 대신 중간에서 넣거나 빼면 그 뒤의 원소를 모두 한 칸씩 옮깁니다. 끝 추가는 대부분 빈칸에 쓰기만 하면 되지만, 배열이 가득 찬 순간에는 더 큰 배열을 만들어 원소 n개를 모두 복사하므로 그 호출 하나만은 O(n)입니다. 이 복사를 전체 추가 횟수로 나누면 한 번에 상수 시간이 되는데, 이것이 용량이 늘어나는 동적 배열 만들기에서 본 분할 상환 O(1)입니다.

LinkedList는 반대입니다. 위치에 도착한 뒤 연결을 고치는 일은 O(1)이지만, 인덱스로 위치를 찾는 데 O(n)이 듭니다. 맨 앞과 맨 끝은 첫 노드와 마지막 노드를 가리키는 first, last 필드로 바로 닿으므로 걷지 않아도 됩니다. 원소를 값으로 찾는 contains와 indexOf는 두 구조 모두 처음부터 하나씩 비교하므로 O(n)입니다. 표의 마지막 줄은 이 글의 뒷부분에서 예제와 함께 따로 봅니다.

메서드 이름이 같다고 비용이 같지는 않다는 점도 기억해 둡니다. Java 21부터는 순서가 있는 컬렉션에 공통 메서드를 둔 SequencedCollection 인터페이스가 생기면서 ArrayList에도 addFirst, removeFirst 같은 메서드가 생겼습니다. LinkedList.addFirst는 O(1)이지만 ArrayList.addFirst(e)는 add(0, e)와 같은 일을 하므로 원소 n개를 옮기는 O(n)입니다.

같은 O(n)이라도 무게가 다르다

중간 삽입은 두 구조 모두 O(n)이지만 한 걸음의 무게가 다릅니다. ArrayList가 원소를 미는 일은 배열의 한 구간을 통째로 옮기는 작업이라, 표준 라이브러리는 이를 System.arraycopy 한 번으로 처리합니다. 연속된 메모리 구간을 통째로 옮기는 일은 JVM과 CPU가 여러 칸을 한꺼번에 처리하도록 최적화되어 있어서, 칸 하나당 비용이 아주 작습니다. 반면 LinkedList가 노드를 따라가는 일은 지금 노드를 읽어야 다음 노드의 주소를 알 수 있어서 한 번에 한 걸음씩만 나아갑니다. 노드가 힙 여기저기에 흩어져 있으면 걸음마다 메모리에서 새로 읽어 와야 할 수도 있습니다. ArrayList의 공식 문서도 선형 시간이 걸리는 연산들에 대해, 상수 계수가 LinkedList 구현보다 작다고 적고 있습니다.

순회도 마찬가지입니다. 두 구조 모두 반복자로 전체를 훑으면 O(n)이지만, ArrayList는 배열에 담긴 참조를 차례로 읽고 LinkedList는 노드에서 노드로 건너뜁니다. 배열에 연속으로 놓인 것은 원소 객체가 아니라 원소를 가리키는 참조이므로, 원소 객체 자체는 두 경우 모두 힙 어딘가에 있습니다. 그래도 다음 원소의 참조를 얻으려고 노드 객체를 하나 더 거쳐야 하느냐가 차이를 만듭니다. CPU는 메모리를 읽을 때 주변의 연속된 데이터를 캐시(cache)라는 작고 빠른 저장소로 함께 가져오므로, 연속된 배열은 한 번 읽을 때 여러 칸이 같이 들어옵니다. 그래서 같은 O(n)이라도 배열 순회가 대개 더 빠릅니다.

메모리 사용량도 다릅니다. ArrayList는 원소마다 배열 칸 하나, 즉 참조 하나를 쓰고, 여기에 여유 용량만큼의 빈칸이 더해질 뿐입니다. LinkedList는 원소마다 원소 참조와 next, prev를 담은 노드 객체를 하나씩 만듭니다. 원소가 100만 개라면 ArrayList는 배열 객체 하나로 충분하지만 LinkedList는 노드 객체 100만 개를 만들고, 가비지 컬렉터는 그 객체를 모두 추적해야 합니다.

더 깊이: 노드 하나는 몇 바이트인가

정확한 크기는 JVM과 설정에 따라 다르지만, 64비트 HotSpot JVM을 기본 설정으로 쓰면 계산해 볼 수 있습니다. 힙이 32GB보다 작으면 JVM은 참조를 4바이트로 압축해 저장하고, 객체마다 12바이트의 헤더를 붙입니다. 그러면 LinkedList의 노드는 헤더 12바이트에 참조 필드 3개(item, next, prev)의 12바이트를 더해 24바이트가 됩니다. ArrayList는 원소마다 배열 칸 4바이트이므로, 원소를 가리키는 데 드는 메모리만 비교하면 LinkedList가 6배를 씁니다.

ArrayList의 배열에는 여유 칸도 있습니다. 공식 명세는 용량을 얼마씩 늘릴지 정하지 않고 끝 추가가 분할 상환 상수 시간이라는 것만 약속하는데, OpenJDK의 구현은 가득 차면 용량을 기존의 약 1.5배로 늘립니다. 그래서 늘린 직후에는 칸의 3분의 1 정도가 비어 있습니다. 그래도 원소 하나에 드는 배열 메모리는 4바이트에 그 절반을 더한 6바이트보다 작아서, 노드 하나의 24바이트에 비하면 훨씬 적습니다. 다만 원소가 몇 개뿐인 목록은 기본 용량 10칸 가운데 대부분이 비어 있어서 원소당 메모리가 더 큽니다. 원소를 지워도 배열이 저절로 줄지는 않으므로, 원소를 다 넣었거나 많이 지운 뒤 남는 칸을 없애고 싶다면 trimToSize()를 호출합니다.

가정한 점수로 두 구현 비교하기

이번에는 조금 다른 상황입니다. 크기 1000인 목록에서 특정 값을 가진 원소를 찾아 그 자리에 새 원소를 넣는데, 찾는 원소가 가운데쯤인 500번째에 있다고 합시다. 위치를 인덱스로 아는 것이 아니라 값으로 찾아야 하므로, 배열이든 연결 목록이든 앞에서부터 원소를 500개쯤 비교해야 합니다. 찾은 뒤에는 배열은 뒤쪽 원소 500개를 밀고, 연결 목록은 참조 2개를 고칩니다. 다음 프로그램은 이 두 단계의 비용을 점수로 정해 두고 합계를 비교합니다.

public final class DeterministicListCostProbe {
    public static void main(String[] args) {
        int size = 1_000;
        int middle = size / 2;
        Cost array = new Cost(middle, size - middle);
        Cost linked = new Cost(middle, 2);
        System.out.println("array-search=" + array.search() + ", writes=" + array.writes());
        System.out.println("linked-search=" + linked.search() + ", writes=" + linked.writes());
        choose(array, linked);
    }

    private static void choose(Cost array, Cost linked) {
        int arrayTotal = array.search() + array.writes();
        int linkedTotal = linked.search() + linked.writes();
        System.out.println("scenario-winner=" + (arrayTotal < linkedTotal ? "array" : "linked"));
    }

    private record Cost(int search, int writes) {
        Cost {
            if (search < 0 || writes < 0) throw new IllegalArgumentException();
        }
    }
}

array-search=500, writes=500
linked-search=500, writes=2
scenario-winner=linked

Cost는 찾는 비용(search)과 고치는 비용(writes)을 담는 레코드이고, 컴팩트 생성자에서 음수 점수를 거부합니다. 배열은 찾기 500점과 밀기 500점(size - middle)을 더해 1000점, 연결 목록은 찾기 500점과 참조 쓰기 2점을 더해 502점입니다. 그래서 choose는 합계가 작은 linked를 고릅니다. 아래 그림이 이 합산을 보여 줍니다.

이 프로그램은 목록을 만들지도, 원소를 옮기지도 않습니다. Cost에 직접 넣은 숫자를 더할 뿐입니다. 배열의 search가 500인 것도 인덱스 조회를 잰 값이 아니라, 위치를 값으로 찾는다는 가정에서 나온 숫자입니다.

이런 모델은 빠뜨린 항목을 찾는 데 쓸모가 있습니다. 연결 목록의 search를 빼고 쓰기 2점만 세면 앞 절의 "삽입은 O(1)"과 같은 실수가 됩니다. 하지만 모델의 결론은 가정이 조금만 달라져도 뒤집힙니다. 위치를 값이 아니라 인덱스로 안다면 배열은 찾는 데 비용이 들지 않으므로 array를 new Cost(0, size - middle)로 바꿔야 하고, 그러면 500점 대 502점으로 배열이 이깁니다. 게다가 이 모델은 배열에서 원소 하나를 미는 일과 노드 하나를 따라가는 일에 똑같이 1점을 주지만, 앞 절에서 본 것처럼 실제로는 앞의 것이 훨씬 가볍습니다. 그래서 가정한 점수의 합만으로는 어느 구현이 실제로 빠른지 결정할 수 없고, 그 판단에는 실제 작업 부하와 측정이 필요합니다.

작업 부하에 맞춰 비용 표 읽기

비용 표는 연산 하나하나의 비용을 알려 줄 뿐입니다. 어느 구현이 나은지는 애플리케이션이 각 연산을 얼마나 자주 하느냐에 달려 있습니다. ArrayList의 장점인 빠른 조회와 순회, LinkedList의 장점인 맨 앞 삽입 가운데 어느 쪽이 중요한지는 연산의 비율을 알아야 정할 수 있습니다. 예를 들어 게시글 저장소의 연산을 기록해 보니 끝 추가가 20%, 전체 순회가 70%, 드문 삭제가 10%였다고 합시다. 이 작업 부하에서는 순회가 대부분이므로 연속된 배열을 훑는 ArrayList가 유리하고, LinkedList의 맨 앞 삽입 장점은 쓰일 일이 거의 없습니다.

목록에 보통 몇 개의 원소가 들어가는지도 함께 봅니다. 원소가 수십 개라면 O(n) 연산도 금방 끝나서 어느 구현을 써도 차이를 느끼기 어렵습니다. 원소가 수십만 개로 늘어나면 O(1)과 O(n)의 차이가 그대로 드러나므로, 이때는 평균 크기만 보지 말고 가장 클 때의 크기도 확인합니다.

이 장의 게시글 저장소 CLI가 하는 일을 다시 보겠습니다. 다음 프로그램의 PostRepository는 Entry[] 배열에 게시글을 담는 배열 기반 저장소로, ArrayList와 같은 구조입니다.

public final class PostRepositoryCliCH148 {
    public static void main(String[] args) {
        PostRepository repository = new PostRepository();
        repository.add("cost-model", 48);
        repository.add("cache-locality", 52);
        repository.print();
        System.out.println("total=" + repository.totalViewCount());
    }

    private static final class PostRepository {
        private Entry[] entries = new Entry[2];
        private int size;

        void add(String title, int viewCount) {
            if (title == null || title.isBlank()) throw new IllegalArgumentException("title");
            if (viewCount <= 0) throw new IllegalArgumentException("viewCount");
            ensureCapacity(size + 1);
            entries[size++] = new Entry(title, viewCount);
        }

        private void ensureCapacity(int required) {
            if (required <= entries.length) return;
            Entry[] grown = new Entry[Math.max(required, entries.length * 2)];
            System.arraycopy(entries, 0, grown, 0, size);
            entries = grown;
        }

        int totalViewCount() {
            int total = 0;
            for (int i = 0; i < size; i++) {
                total += entries[i].viewCount();
            }
            return total;
        }

        void print() {
            for (int i = 0; i < size; i++) {
                Entry entry = entries[i];
                System.out.println(i + ":" + entry.title() + "=" + entry.viewCount());
            }
        }
    }

    private record Entry(String title, int viewCount) {}
}

0:cost-model=48
1:cache-locality=52
total=100

이 CLI의 작업 부하는 끝 추가 두 번, 전체 출력 한 번, 합계를 위한 전체 순회 한 번입니다. 중간 삽입이나 맨 앞 삽입은 한 번도 없습니다. 끝 추가는 빈칸에 쓰기만 하면 되고(처음 용량이 2라서 이 실행에서는 배열을 늘리지도 않습니다), 두 번의 순회는 사용 중인 칸을 앞에서부터 차례로 읽습니다. 배열 기반 구조가 잘하는 일만 하므로 연결 목록으로 바꿀 이유가 없습니다. LinkedList를 고르려면 맨 앞 삽입이나 반복 중 삽입이 실제로 많다는 기록이 있어야 합니다.

LinkedList가 실제로 유리한 경우

LinkedList가 분명히 유리한 것은 원소를 넣거나 지울 위치에 이미 도착해 있을 때입니다. 표준 API에는 노드를 직접 가리키는 방법이 없으므로, 그 역할은 ListIterator가 맡습니다. ListIterator는 목록을 앞뒤로 움직일 수 있는 반복자로, 지금 위치에 원소를 끼워 넣는 add와 방금 돌려준 원소를 지우는 remove를 제공합니다. 다음 프로그램은 "b"를 찾으면 그 바로 뒤에 "new"를 넣습니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public final class InsertAtIteratorPosition {
    public static void main(String[] args) {
        insertAfter(new ArrayList<>(List.of("a", "b", "c")), "b", "new");
        insertAfter(new LinkedList<>(List.of("a", "b", "c")), "b", "new");
    }

    private static void insertAfter(List<String> list, String target, String value) {
        ListIterator<String> cursor = list.listIterator();
        while (cursor.hasNext()) {
            if (cursor.next().equals(target)) {
                cursor.add(value);
                break;
            }
        }
        System.out.println(list.getClass().getSimpleName() + "=" + list);
    }
}

ArrayList=[a, b, new, c]
LinkedList=[a, b, new, c]

두 목록의 결과는 같지만, 끼우는 순간에 하는 일은 다릅니다. LinkedList의 반복자는 지금 위치의 노드를 알고 있으므로 참조 몇 개만 고치면 됩니다. ArrayList의 반복자는 지금 인덱스만 알기 때문에 내부에서 add(index, e)를 호출해 뒤쪽 원소를 모두 밉니다. 이 예에서는 "c" 하나만 밀었지만, 원소 n개를 한 번 훑으면서 여러 곳에 원소를 끼워 넣는다면 차이가 커집니다. ArrayList는 끼울 때마다 최대 n개를 밀어서 최악에는 전체 비용이 n²에 비례하지만, LinkedList는 n번의 순회에 끼울 때마다 상수 시간만 더하면 됩니다.

맨 앞에서 원소를 자주 넣고 빼는 경우도 LinkedList가 O(1)로 처리합니다. 다만 양 끝에서만 넣고 빼는 큐나 스택이라면, 배열을 원형으로 돌려 쓰는 ArrayDeque가 메모리와 순회 속도 면에서 대개 더 나은 선택입니다. 두 클래스는 ArrayDeque로 스택과 큐 다루기에서 비교합니다.

반대로 삭제가 많다는 이유만으로 LinkedList를 고를 필요는 없습니다. 조건에 맞는 원소를 여러 개 지울 때는 removeIf를 쓰면 됩니다. 반복자로 하나씩 지우면 지울 때마다 뒤쪽 원소를 당기느라 최악에는 n²에 비례하는 시간이 듭니다. OpenJDK의 ArrayList는 removeIf를 따로 구현해서, 지울 원소를 먼저 모두 표시해 둔 뒤 남길 원소를 한 번에 앞으로 당깁니다. 그래서 지울 원소가 많아도 원소 수에 비례하는 시간에 끝납니다.

더 깊이: 성능을 재 볼 때 주의할 점

구현 선택이 정말로 성능에 영향을 주는지 알고 싶다면 직접 재 봐야 합니다. 다만 JVM에서 실행 시간을 재는 일은 생각보다 까다롭습니다. JVM은 실행 중에 자주 쓰이는 코드를 기계어로 다시 컴파일(JIT 컴파일)하므로 처음 몇 번의 실행은 느리고, 가비지 컬렉션이나 다른 프로세스의 CPU 사용도 결과를 흔듭니다. 그래서 System.nanoTime()으로 한 번 잰 차이는 잡음일 가능성이 큽니다.

믿을 만한 숫자를 얻으려면 충분히 예열한 뒤 여러 번 반복해 결과의 분포를 봐야 합니다. 이런 일을 대신 해 주는 OpenJDK 프로젝트의 측정 도구 JMH(Java Microbenchmark Harness)를 쓰는 것이 안전합니다. 어떤 도구를 쓰든 측정할 데이터는 측정 구간 밖에서 미리 만들어 두고, 두 구현이 같은 결과를 내는지부터 확인한 다음에 시간을 비교합니다. 측정할 작업 부하도 실제 애플리케이션의 연산 비율과 목록 크기에 맞춰야 합니다.

정리

• 연결 목록의 삽입이 O(1)이라는 말은 위치에 도착한 뒤의 연결 변경만 센 것입니다. 인덱스로 위치를 찾는 비용까지 세면 중간 삽입은 ArrayList도 LinkedList도 O(n)입니다.
• ArrayList는 get과 set이 O(1), 끝 추가가 분할 상환 O(1)이고, 중간 삽입과 삭제는 뒤쪽 원소를 옮기는 O(n)입니다. LinkedList는 양 끝 연산이 O(1)이고, 인덱스를 쓰는 연산은 가까운 끝에서 걸어가는 O(n)입니다.
• 같은 O(n)이라도 배열 구간을 한 번에 복사하거나 연속된 배열을 훑는 일은 노드를 하나씩 따라가는 일보다 훨씬 가볍습니다. LinkedList는 원소마다 노드 객체를 만들어 메모리도 더 씁니다.
• 가정한 점수 모델은 빠뜨린 비용을 찾는 데 쓰고, 어느 구현이 빠른지는 실제 작업 부하와 측정으로 정합니다.
• 측정 결과가 없다면 ArrayList를 기본으로 씁니다. LinkedList는 반복자 위치에서 삽입과 삭제가 잦을 때처럼 그 장점이 실제로 쓰이는 경우에 고릅니다.

연습 문제

1. 크기 1000인 목록에서 중간 조회 700회와 맨 앞 삽입 3회를 한다고 가정합니다. 배열은 조회 한 번에 1점, 맨 앞 삽입 한 번에 1000점을, 연결 목록은 중간 조회 한 번에 500점, 맨 앞 삽입 한 번에 1점을 매겨 두 구현의 총점을 비교하세요. 계산을 단순하게 하려고, 삽입한 뒤에도 크기는 1000으로 고정한다고 봅니다.

public final class MixedListWorkloadSolution {
    public static void main(String[] args) {
        int reads = 700;
        int frontInserts = 3;
        int arrayCost = reads + frontInserts * 1_000;
        int linkedCost = reads * 500 + frontInserts;
        String choice = arrayCost < linkedCost ? "array" : "linked";
        System.out.println("array=" + arrayCost + ", linked=" + linkedCost + ", choice=" + choice);
    }
}

array=3700, linked=350003, choice=array

2. 1번과 같은 점수 규칙과 크기 1000을 그대로 쓰고, 작업 부하만 중간 조회 3회와 맨 앞 삽입 4회로 바꿉니다. 두 구현의 총점과 선택 결과를 구하세요.

3. 원소가 1000개인 표준 LinkedList와 ArrayList에서 각각 add(800, e)를 호출합니다. LinkedList는 노드를 몇 번 따라가고, ArrayList는 원소를 몇 개 옮기나요? add(200, e)라면 어떻게 달라지나요?

다음 글

용도에 맞는 List 고르기에서는 ArrayList와 LinkedList뿐 아니라 List.of, List.copyOf, Arrays.asList로 만든 목록까지 비교합니다. 모두 같은 List 타입이지만 add를 호출할 수 있는지, 원본과 연결되어 있는지가 서로 다르고, 그 차이를 이용해 게시글 저장소가 내부 목록을 안전하게 내보내도록 완성합니다.