Java Academy · 강의

LinkedList와 ArrayList의 장단점

적절한 리스트 유형을 선택하도록 삽입, 삭제, 임의 접근 성능을 비교합니다.

LinkedList와 ArrayList의 장단점은(는) CoddyKit의 무료 Java Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Java Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

핵심 질문

ArrayList와 LinkedList는 모두 List를 구현하므로 동일한 API를 공유합니다. 차이점은 내부 데이터 구조와 각 구조가 효율적으로 수행하는 연산에 있습니다.

ArrayList 내부 구조

ArrayList는 요소를 연속 배열에 저장합니다. 배열이 가득 차면 기존 배열보다 1.5배 큰 새 배열로 교체하고 모든 요소를 복사합니다.

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

다시 살펴보는 LinkedList 내부 구조

각 요소는 prev/next 포인터를 가진 자체 Node 객체에 저장됩니다. 연속된 메모리를 사용하지 않으므로 Node는 힙의 어느 위치에나 있을 수 있습니다.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

무작위 접근: ArrayList의 우세

ArrayList.get(i)는 배열 인덱스에 직접 접근하므로 O(1)입니다. LinkedList.get(i)는 최대 n/2개의 Node를 순회하므로 O(n)입니다.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

첫 부분 삽입: LinkedList의 우세

ArrayList의 인덱스 0에 추가하려면 모든 요소를 이동해야 하므로 O(n)입니다. LinkedList는 두 포인터만 갱신하므로 O(1)입니다.

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

마지막 부분 삽입: 대체로 동일

ArrayList와 LinkedList 모두 마지막 부분에 요소를 추가하는 작업의 분할 상환 시간 복잡도가 O(1)입니다. ArrayList는 가끔 크기를 늘리며 복사해야 하지만 분할 상환 기준으로는 여전히 O(1)입니다. LinkedList는 새 Node를 할당하므로 크기 조정이 필요하지 않습니다.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

메모리 사용량

ArrayList: 요소당 약 8바이트(배열에 저장된 참조 하나). LinkedList: 요소당 약 48바이트(data, prev, next와 객체 헤더를 가진 Node 객체). 대규모 데이터셋에서는 ArrayList가 훨씬 적은 메모리를 사용합니다.

순회 성능

순차 순회(for-each 또는 반복자)는 두 구조 모두 O(n)입니다. 그러나 ArrayList는 요소가 메모리에 연속으로 배치되어 CPU 캐시 프리페칭의 이점을 얻습니다. LinkedList의 Node는 힙 전체에 흩어져 있어 캐시 누락이 발생합니다.

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

중간 삽입/삭제

두 구조 모두 위치를 찾는 데 O(n)이 필요합니다. 위치를 찾은 후 ArrayList는 요소를 O(n)만큼 이동하고, LinkedList는 연결만 해제하므로 O(1)입니다. 따라서 이미 반복자를 보유한 상태에서 중간 변경을 자주 수행한다면 LinkedList가 우세하고, 그렇지 않다면 두 구조가 비슷합니다.

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

선택 가이드

주로 수행하는 연산을 기준으로 선택하십시오.

ArrayList: 무작위 접근, 순회, 마지막 부분 추가 — 사용 사례의 90%를 처리합니다
LinkedList: 첫 부분/마지막 부분의 삽입과 제거가 잦거나 큐/덱/스택을 구현할 때 사용합니다
ArrayDeque: 순수한 큐나 스택이 필요할 때 사용합니다(LinkedList보다 좋습니다)

성능 측정 요약

성능을 이해하기 위한 기준:

get(i): ArrayList O(1), LinkedList O(n)
add(0,x): ArrayList O(n), LinkedList O(1)
add(x): 둘 다 분할 상환 O(1)
반복자의 remove: 위치를 찾은 후에는 둘 다 O(1)
요소당 메모리: ArrayList 약 8B, LinkedList 약 48B

빠른 확인

초당 수백만 번 작업이 끝에 추가되고 앞에서 제거되는 작업 큐를 만들고 있습니다. 어떤 데이터 구조가 가장 적합합니까?

복습: LinkedList와 ArrayList 비교

핵심 내용:

ArrayList는 무작위 접근(O(1))과 캐시에 친화적인 순회에 뛰어납니다
LinkedList는 헤드와 테일에서의 O(1) 연산에 뛰어납니다
메모리: ArrayList는 요소당 약 8B, LinkedList는 요소당 약 48B입니다
큐나 스택에는 LinkedList보다 ArrayDeque를 사용하는 것이 좋습니다
대부분의 상황에서 ArrayList가 적절한 기본 선택입니다

자주 묻는 질문

“LinkedList와 ArrayList의 장단점” 강의는 무료인가요?

네 — “LinkedList와 ArrayList의 장단점” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Java Academy 강의 전체를 잠금 해제할 수 있습니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“LinkedList와 ArrayList의 장단점”에서 뭘 배우나요?

적절한 리스트 유형을 선택하도록 삽입, 삭제, 임의 접근 성능을 비교합니다. 브라우저에서 직접 실행하는 실습 코드로 Java Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Java Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Java Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

“LinkedList와 ArrayList의 장단점” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Java Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Java Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← Java Academy(으)로 돌아가기