Java ArrayList vs LinkedList — 진짜 차이(내부 구조·성능·실무 선택 기준)

Java ArrayList와 LinkedList의 내부 구조와 성능 차이를 실제 사용 패턴 기준으로 비교하고, 실무에서 ArrayList가 기본 선택이 되는 이유를 정리합니다.

 

리스트가 필요해서 List를 고르려는데, IDE 자동완성에 ArrayList와 LinkedList가 나란히 보이면 한 번쯤 고민하게 됩니다. “중간 삽입이 많으면 LinkedList가 빠르다”는 이야기도 들었는데, 막상 실무에서는 ArrayList만 보이는 경우가 많죠. 오늘은 이 간극이 왜 생기는지, 내부 구조와 성능 관점에서 정리해 봅니다.

핵심 개념: Java ArrayList vs LinkedList 차이를 만드는 ‘구조’와 ‘접근 패턴’

ArrayList는 연속 배열, LinkedList는 노드 체인으로 저장되는 구조 비교 그림

ArrayList와 LinkedList는 둘 다 List이지만, 데이터를 담는 방식이 완전히 다릅니다. 이 차이가 성능과 실무 선택을 거의 결정합니다.

ArrayList 내부 구조: “연속된 배열”

ArrayList는 내부에 **가변 크기 배열(Object[])**을 들고 있습니다. 인덱스로 접근할 때는 배열처럼 바로 찾아가므로 get(i)가 빠릅니다. 대신 용량이 부족해지면 더 큰 배열을 만들고 기존 요소를 복사하는 리사이즈 비용이 가끔 발생합니다(보통 용량을 1.5배 정도로 늘립니다).

flowchart LR
  A["ArrayList"] --> B["Object[] array"]
  B --> C["0"]
  B --> D["1"]
  B --> E["2"]
  B --> F["..."]

ArrayList는 내부적으로 연속 메모리(배열)에 요소를 저장해 인덱스 접근이 빠릅니다.

LinkedList 내부 구조: “노드가 서로 연결된 체인”

LinkedList는 요소마다 노드(Node) 객체가 있고, 각 노드는 prev/next/item을 가집니다. 즉 값 하나 넣을 때마다 노드 객체가 추가로 생기고, 포인터(참조)로 앞뒤를 연결합니다.

flowchart LR
  H["head"] --> N1["Node"]
  N1 --> N2["Node"]
  N2 --> N3["Node"]
  N3 --> T["tail"]

LinkedList는 노드들이 참조로 연결되어 있어 중간 삽입은 “연결만 바꾸면 된다”는 구조적 장점이 있습니다.

 

---

“LinkedList는 중간 삽입이 빠르다”가 실무에서 잘 안 먹히는 이유

교과서적으로는 맞습니다. ‘이미 그 위치의 노드를 알고 있다면’ 연결만 바꾸면 되니 삽입/삭제가 O(1)입니다.
하지만 실무에서 흔한 패턴은 이렇습니다.

• “N번째에 넣어야지” → 결국 list.add(index, x) 호출
• 그러면 LinkedList는 index까지 순회해야 합니다 → O(n)
• 순회 과정이 느린 이유는 캐시 친화성이 낮고(메모리가 흩어짐), 노드 객체가 많아 GC 부담도 커지기 때문입니다.

반대로 ArrayList는 add(index, x)에서 뒤 요소를 밀어야 해서 O(n)이지만, **연속된 배열 복사(System.arraycopy)**가 매우 최적화되어 있고 CPU 캐시에도 유리합니다. 그래서 “중간 삽입=LinkedList” 공식이 실제 체감 성능으로는 자주 뒤집힙니다.

---

성능 비교 요약: 무엇이 빠른지 “연산”별로 보세요

아래 표는 Big-O만이 아니라, 실무에서 체감에 영향을 주는 특성(캐시/오버헤드)을 같이 담았습니다.

연산/특성	ArrayList	LinkedList	실무 코멘트
get(i) 인덱스 접근	O(1)	O(n)	LinkedList는 i까지 순회해야 해서 급격히 느려집니다
끝에 추가 add(e)	amortized O(1)	O(1)	둘 다 빠르지만 ArrayList는 리사이즈 순간 비용이 있습니다
중간 삽입/삭제 add(i,e), remove(i)	O(n)	O(n) (탐색 포함)	“탐색이 포함된다”는 점 때문에 LinkedList가 이득 보기 어렵습니다
순회(Iterator)	빠름(캐시 친화)	상대적으로 느림	LinkedList는 포인터 따라가며 캐시 미스가 잦습니다
메모리 사용량	상대적으로 적음	큼(노드 객체 + 참조 2개)	데이터가 커질수록 차이가 커집니다
GC/할당 부담	낮음	높음	노드 객체가 많아져 GC에 불리합니다

결론적으로, 일반적인 애플리케이션(웹/배치/서비스)에서 가장 흔한 작업인 조회, 순회, 끝에 추가 중심이라면 ArrayList가 거의 항상 유리합니다.

---

그럼 LinkedList는 언제 쓰나요?

LinkedList가 “나쁜 컬렉션”은 아닙니다. 다만 정말로 맞는 상황이 좁다는 게 포인트입니다.

• 이미 노드 위치를 알고 있고(예: ListIterator로 이동해 둔 상태), 그 자리에서 삽입/삭제를 반복하는 경우
• 앞/뒤에서의 삽입/삭제를 Deque로 사용하고 싶을 때

다만 여기서도 중요한 함정이 있습니다. Deque 용도라면 LinkedList보다 **ArrayDeque**가 더 좋은 선택인 경우가 대부분입니다(더 적은 오버헤드, 더 좋은 캐시 효율). ArrayDeque는 Java에서 큐/스택 구현의 “기본 추천”에 가깝습니다.

참고: LinkedList는 List이면서 Deque이기도 하지만, “큐가 필요해서 LinkedList”는 요즘 기준으로는 잘 안 맞는 선택이 됩니다.

코드 예제: ArrayList vs LinkedList 성능을 직접 확인하는 간단 벤치마크

아래 코드는 Java 17에서 그대로 실행 가능합니다. 엄밀한 성능 측정은 JMH가 정석이지만, “왜 LinkedList가 느리게 느껴지는지”를 감 잡기에는 충분합니다.

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

public class ListPerformanceDemo {

    private static final int N = 300_000;
    private static final int OPS = 50_000;

    public static void main(String[] args) {
        System.out.println("Java " + System.getProperty("java.version"));
        System.out.println("N=" + N + ", OPS=" + OPS);

        List<Integer> arrayList = new ArrayList<>(N); // 용량 지정: 리사이즈 비용 감소
        List<Integer> linkedList = new LinkedList<>();

        fill(arrayList, N);
        fill(linkedList, N);

        // 워밍업(간단)
        time("warmup array get", () -> randomGets(arrayList, 10_000));
        time("warmup linked get", () -> randomGets(linkedList, 10_000));

        System.out.println("\n--- random get(i) ---");
        time("ArrayList random get", () -> randomGets(arrayList, OPS));
        time("LinkedList random get", () -> randomGets(linkedList, OPS));

        System.out.println("\n--- iterate sum ---");
        time("ArrayList iterate", () -> iterateSum(arrayList));
        time("LinkedList iterate", () -> iterateSum(linkedList));

        System.out.println("\n--- add at middle (index=N/2) ---");
        time("ArrayList add middle", () -> addMiddle(new ArrayList<>(arrayList), OPS));
        time("LinkedList add middle", () -> addMiddle(new LinkedList<>(linkedList), OPS));
    }

    private static void fill(List<Integer> list, int n) {
        for (int i = 0; i < n; i++) list.add(i);
    }

    private static long iterateSum(List<Integer> list) {
        long sum = 0;
        for (int v : list) sum += v;
        return sum;
    }

    private static long randomGets(List<Integer> list, int ops) {
        Random r = new Random(42);
        long sum = 0;
        int size = list.size();
        for (int i = 0; i < ops; i++) {
            int idx = r.nextInt(size);
            sum += list.get(idx); // LinkedList는 여기서 매번 순회가 발생
        }
        return sum;
    }

    private static void addMiddle(List<Integer> list, int ops) {
        int mid = list.size() / 2;
        for (int i = 0; i < ops; i++) {
            list.add(mid, -i);
        }
    }

    private static void time(String label, Runnable r) {
        long start = System.nanoTime();
        r.run();
        long end = System.nanoTime();
        double ms = (end - start) / 1_000_000.0;
        System.out.printf("%-22s : %8.2f ms%n", label, ms);
    }
}

• random get(i)에서 LinkedList가 유독 느리게 나오는 경우가 많습니다(매번 i까지 걸어감).
• iterate는 둘 다 O(n)이지만, LinkedList가 더 느리게 나올 수 있습니다(캐시 미스/노드 오버헤드).
• add middle은 둘 다 O(n)인데, 상황에 따라 ArrayList가 오히려 선전하는 결과도 흔합니다(배열 복사 최적화).

실무 팁

💡 실무에서는: List 타입으로 받되, 기본 구현은 ArrayList로 시작해 보세요

• 메서드 시그니처/필드는 List로 두고(List<User> users), 생성만 new ArrayList<>()로 하는 방식이 유지보수에 유리합니다.
• 성능 문제가 생기면 “구현 교체”가 아니라 **접근 패턴(랜덤 접근/순회/삽입 위치)**부터 점검하는 게 효과가 큽니다.

💡 실무에서는: “큐/스택이 필요해서 LinkedList” 대신 ArrayDeque를 먼저 검토해 보세요

• Deque가 필요하면 ArrayDeque가 대개 더 빠르고 메모리 효율도 좋습니다.
• LinkedList는 노드 객체가 많아져 GC 압박이 커질 수 있고, 예상보다 성능이 안 나오는 케이스가 자주 나옵니다.

---

핵심 요약: ArrayList는 배열 기반이라 조회/순회에 강하고, LinkedList는 노드 기반이라 메모리·캐시·GC 측면에서 불리한 경우가 많습니다.
실무의 대부분 패턴에서는 ArrayList가 기본값이 되며, LinkedList는 “정말 맞는” 특수한 경우에만 선택하면 됩니다.
큐/덱 용도라면 LinkedList보다 ArrayDeque를 먼저 보세요.

다음 글: #14 HashMap 동작 원리와 함정