Unit 5.3 — LinkedList 내부 (노드 연결)
F-LAB JAVA · 2주차 · Phase 5 · 컬렉션 프레임워크 내부 구조
📌 학습 목표
이 Unit을 끝내면 다음을 답할 수 있어야 한다.
- LinkedList의 Node 클래스 정확한 구조는?
- 자바 LinkedList가 단일/이중 연결 중 어느 쪽인가?
- head, tail, size 의 역할은?
- 인덱스 접근
get(i)가 O(n) + 최적화의 정확한 동작은? - 메모리 단위로 흩어진 결과는?
- LinkedList의 진짜 강점은 무엇이고, 언제 써야 하나?
- ILIC에서 LinkedList가 적합한 시나리오는?
🎯 핵심 한 문장
LinkedList = "Node 객체들의 사슬"이다.
ArrayList의 연속된 배열과 달리, 각 Node가 다른 Node의 메모리 주소를 가리키는 방식으로 연결.
그래서 앞/뒤 추가/삭제는 O(1), 그러나 인덱스 접근은 O(n) — 사슬을 따라가야 하니까.
메모리도 Object Header가 더 커서 ArrayList보다 무겁다.
비유 — 보물 찾기 메모
| 시스템 | 비유 |
|---|---|
| ArrayList | 책장에 책이 번호 순으로 — 7번 책? 7번 자리 |
| LinkedList | 메모에 "다음 메모는 ___에 있음" — 7번 메모? 1번부터 6번까지 거쳐야 |
| head | 첫 번째 메모의 위치 |
| tail | 마지막 메모의 위치 |
| 이중 연결 | 메모마다 "이전 메모 위치"도 적혀있음 |
→ 인덱스 빠르지 않지만, 메모 끼우고 빼는 건 매우 간단 (이전/다음 메모만 수정).
🧭 9개 섹션 로드맵
1. LinkedList의 내부 — Node 사슬
2. Node 클래스 정밀
3. head, tail, size의 역할
4. add / remove 동작 추적
5. get(i)의 O(n) — 사슬 따라가기 최적화
6. 메모리 효율 vs ArrayList
7. ILIC 실무 — LinkedList가 진짜 빛나는 곳
8. 흔한 실수 + 디버깅
9. 면접 질문 + 자기 점검1️⃣ LinkedList의 내부 — Node 사슬
1.1 핵심 필드
public class LinkedList<E> {
transient int size = 0;
transient Node<E> first; // head
transient Node<E> last; // tail
// Node 내부 클래스
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
}→ ArrayList의 Object[] 대신 Node 사슬.
1.2 Node의 정확한 구조
private static class Node<E> {
E item; // 실제 데이터 (참조)
Node<E> next; // 다음 Node 참조
Node<E> prev; // 이전 Node 참조
}각 Node:
- 데이터 (item)
- 다음 Node 주소 (next)
- 이전 Node 주소 (prev)
→ 이중 연결 리스트 (Doubly Linked List).
1.3 메모리 시각화
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");Heap 메모리:
LinkedList 객체:
┌─────────────────────┐
│ first ──────────────┼──┐
│ last ──────────────┼──┤
│ size = 3 │ │
└─────────────────────┘ │
│
┌────────────────────────┘
│
▼
┌──────────────────┐
│ Node A │
│ item = "A" │
│ prev = null │
│ next ───────────┼──┐
└──────────────────┘ │
│
┌────────────────────┘
│
▼
┌──────────────────┐
│ Node B │
│ item = "B" │
│ prev ←──────────┼──────┐ ← Node A
│ next ───────────┼──┐ │
└──────────────────┘ │ │
│ │
┌────────────────────┘ │
│ │
▼ │
┌──────────────────┐ │
│ Node C │ │
│ item = "C" │ │
│ prev ←──────────┼─────────┘ ← Node B
│ next = null │
└──────────────────┘
▲
│
└─── LinkedList.last→ Node들이 Heap 곳곳에 흩어져 화살표로 연결.
1.4 ArrayList와의 결정적 차이
ArrayList:
Object[] elementData:
┌──┬──┬──┬──┬──┬──┐
│A │B │C │ │ │ │ ← 연속된 메모리
└──┴──┴──┴──┴──┴──┘
LinkedList:
Node A ──► Node B ──► Node C ← 흩어진 메모리, 화살표로 연결
◄──── ◄────→ 연속 vs 흩어짐.
→ 인덱스 접근 vs 순차 탐색.
2️⃣ Node 클래스 정밀
2.1 자바 LinkedList는 이중 연결
private static class Node<E> {
E item; // 데이터
Node<E> next; // 다음
Node<E> prev; // 이전
}자기 점검 답변:
단일 연결 리스트와 이중 연결 리스트의 차이?
자바 LinkedList는 어느 쪽인가?
답:
- 단일 연결: next만 (한 방향)
- 이중 연결: prev + next (양방향)
- 자바 LinkedList: 이중 연결 ★
2.2 이중 연결의 이점
단일 연결의 한계:
- 역방향 순회 불가
- 마지막 노드 접근에 O(n) (head부터 끝까지)
- 노드 삭제 시 "이전 노드"를 찾아야 함
이중 연결의 이점:
- 양방향 순회 가능
- tail(last) 포인터로 끝 접근 O(1)
- 노드 삭제 시 prev/next만 수정2.3 메모리 비용
Node 1개의 메모리 (Compressed Oops):
Object Header: 16 bytes
item (참조): 4 bytes
next (참조): 4 bytes
prev (참조): 4 bytes
Padding: 4 bytes
─────────────
총: 32 bytes
ArrayList의 한 요소:
Object[] 의 한 슬롯: 4 bytes (참조만)
비교:
10000 요소 보관 시
ArrayList: ~40KB (elementData)
LinkedList: ~320KB (Node 객체들)
→ 약 8배 메모리 사용→ LinkedList는 메모리 비용이 큼.
→ 각 요소마다 추가 객체 (Node) 생성.
2.4 캐시 효율
ArrayList:
연속 메모리 → CPU 캐시에 잘 들어감
순회 시 매우 빠름 (캐시 hit)
LinkedList:
흩어진 메모리 → 캐시 miss 빈번
순회 시 메모리 접근 비용 증가→ 같은 size여도 순회 성능 차이 큼.
→ ArrayList가 보통 빠른 이유 중 하나.
2.5 Node 객체 자체의 부담
LinkedList.add() 시:
- Node 객체 생성 (new)
- GC에 의해 결국 회수
ArrayList.add() 시:
- 그냥 배열 슬롯에 참조 저장
- Node 객체 생성 안 함
→ 100만 건 add 시:
ArrayList: Object[] 1개 + 추가 객체 없음
LinkedList: Node 100만 개! (GC 부담)3️⃣ head, tail, size의 역할
3.1 head (first) — 시작점
transient Node<E> first;- LinkedList의 첫 Node 참조
getFirst(),add(0, e)등에서 사용- 비어있으면 null
3.2 tail (last) — 끝점
transient Node<E> last;- LinkedList의 마지막 Node 참조
getLast(),add(e)(끝 추가) 등에서 사용- 비어있으면 null
→ tail이 있어서 끝 작업 O(1).
3.3 size — 카운터
transient int size = 0;- 현재 Node 개수
size()호출 시 O(1) 반환
만약 size 필드 없으면:
- size() = O(n) (모든 Node 카운트)
- 자주 호출되는 메서드라 캐싱 필수
3.4 빈 LinkedList
LinkedList<String> list = new LinkedList<>();
// first = null
// last = null
// size = 0→ ArrayList의 Lazy 초기화처럼, 초기 메모리 비용 거의 0.
3.5 ArrayList와 비교
ArrayList:
Object[] elementData; // 항상 배열 있음 (또는 빈 배열)
int size;
LinkedList:
Node first; // 비어있으면 null
Node last; // 비어있으면 null
int size;빈 컬렉션 메모리:
- ArrayList: 약 40 bytes (객체 헤더 + 빈 배열)
- LinkedList: 약 40 bytes (객체 헤더 + null 참조들)
거의 같음. 빈 컬렉션 비용은 차이 없음.
4️⃣ add / remove 동작 추적
4.1 끝에 add — O(1)
list.add("D");내부 동작:
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}추적:
Before:
first → A → B → C ← last
linkLast("D"):
1. l = last (= C)
2. newNode = new Node(prev=C, item="D", next=null)
3. last = newNode (= D)
4. l.next = newNode → C.next = D
After:
first → A → B → C → D ← last→ tail 참조 덕에 O(1).
4.2 앞에 add — O(1)
list.add(0, "Z");
// 또는
list.addFirst("Z");void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
}추적:
Before:
first → A → B → C ← last
linkFirst("Z"):
1. f = first (= A)
2. newNode = new Node(prev=null, item="Z", next=A)
3. first = newNode (= Z)
4. f.prev = newNode → A.prev = Z
After:
first → Z → A → B → C ← last→ head 참조 덕에 O(1).
4.3 중간에 add — O(n) 위치 찾기 + O(1) 삽입
list.add(2, "X");public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index)); // ← node(index)가 O(n)
}
Node<E> node(int index) {
if (index < (size >> 1)) {
// 앞쪽 절반이면 head부터 순회
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 뒤쪽 절반이면 tail부터 역순회
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}최적화: 이중 연결 덕에 가까운 쪽부터 탐색.
- 앞 절반이면 first부터
- 뒤 절반이면 last부터
- 평균 n/4 비교 → 그래도 O(n)
4.4 중간 삽입 후 연결 변경
Before (index 2에 X 삽입):
first → A → B → C → D ← last
↑
index 2 (= C 자리)
Step 1: node(2) = C 찾기
O(n) 탐색 (또는 n/2, n/4 평균)
Step 2: linkBefore("X", C):
newNode = new Node(prev=B, item="X", next=C)
B.next = newNode
C.prev = newNode
After:
first → A → B → X → C → D ← last→ 위치 찾기는 O(n), 실제 삽입은 O(1) (참조만 변경).
4.5 remove — 위치만 알면 O(1)
Node<E> node = ...; // 어떻게든 알고 있음
void unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
}→ 이전/다음 참조만 변경. O(1).
다이어그램:
Before:
A → B → C → D
↑
삭제 대상
unlink(B):
- A.next = C
- C.prev = A
- B 노드는 isolated → GC 대상
After:
A → C → D→ 위치를 안다면 삭제는 O(1).
→ 위치를 모르면 찾는 데 O(n) 먼저.
4.6 Deque로서의 LinkedList
자바 LinkedList는 Deque 인터페이스 구현.
Deque<Shipment> deque = new LinkedList<>();
deque.offerFirst(s); // O(1)
deque.offerLast(s); // O(1)
deque.pollFirst(); // O(1)
deque.pollLast(); // O(1)
deque.peekFirst(); // O(1)
deque.peekLast(); // O(1)→ Queue, Stack 으로도 사용 가능.
5️⃣ get(i)의 O(n) — 사슬 따라가기 최적화
5.1 인덱스 접근의 본질
LinkedList<String> list = ...;
list.get(5); // 어떻게 5번째 찾나?ArrayList의 get(5):
elementData[5]한 번에 접근 → O(1)
LinkedList의 get(5):
- head부터 next 5번 따라가기
- O(n)
5.2 이중 연결 활용 최적화
자바 LinkedList의 node(int index):
Node<E> node(int index) {
if (index < (size >> 1)) {
// 앞 절반: first부터
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 뒤 절반: last부터 역방향
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}→ 최악 n/2 까지 단축.
→ 그래도 O(n).
5.3 시각화
size 10 LinkedList에서:
get(2): first부터 next 2번 → 2 steps
get(5): first부터 next 5번 → 5 steps (또는 last부터 역순 4번)
get(8): last부터 prev 1번 → 1 step (역순 최적화)
get(9): last부터 prev 0번 → 0 step (last)5.4 순회의 함정
LinkedList<Shipment> list = ...; // 10000개
// ❌ 절대 이렇게 하지 말 것
for (int i = 0; i < list.size(); i++) {
Shipment s = list.get(i); // O(n) × n = O(n²)
process(s);
}
// → 10000 × 10000 = 1억 작업해결:
// ✓ Iterator 또는 for-each
for (Shipment s : list) {
process(s); // 순차 순회 → 전체 O(n)
}
// ✓ Stream
list.stream().forEach(this::process);→ for-each는 내부적으로 Iterator 사용.
→ Iterator는 현재 Node를 기억하고 next 한 번씩 → O(n) 전체.
5.5 for-each vs index loop
ArrayList:
for (int i = 0; i < list.size(); i++) {
list.get(i); // ArrayList는 O(1) → 전체 O(n) OK
}
for (E e : list) {
// 같음
}LinkedList:
for (int i = 0; i < list.size(); i++) {
list.get(i); // LinkedList는 O(n) → 전체 O(n²) ❌
}
for (E e : list) {
// Iterator 사용 → 전체 O(n) ✓
}→ List에는 항상 for-each 또는 Iterator 사용.
→ 인덱스 접근은 ArrayList의 특권.
5.6 자기 점검 답변
자바 LinkedList의 인덱스 접근은 정말 O(n)인가?
답:
- O(n)이 맞음
- 이중 연결로 양쪽에서 접근 가능 → 평균 n/4
- 여전히 빅 O는 O(n)
- 절대 인덱스 접근 빈번하게 쓰면 안 됨
6️⃣ 메모리 효율 vs ArrayList
6.1 같은 데이터의 메모리 사용
1000개 Integer 보관:
ArrayList<Integer>:
Object[] elementData: 4 bytes × 1000 = 4KB
Integer 객체들 (Heap에 별도): 자동 캐싱 (-128~127) 또는 16 bytes × 1000 = ~16KB
ArrayList 객체 자체: ~40 bytes
총: ~20KB
LinkedList<Integer>:
Node 1000개: 32 bytes × 1000 = 32KB
Integer 객체들: 동일 ~16KB
LinkedList 객체 자체: ~40 bytes
총: ~48KB
→ LinkedList가 약 2.4배 큼6.2 캐시 효율 차이
CPU L1/L2/L3 캐시:
- 캐시 라인 = 64 bytes
- 메모리 접근 시 64 bytes 단위로 로드
ArrayList 순회:
연속 메모리 → 캐시 라인 1번 로드로 16개 정수 처리
→ 매우 빠름
LinkedList 순회:
Node들이 흩어짐 → 매 Node마다 새 캐시 라인 로드
→ 메모리 접근 횟수 16배
→ CPU 활용도 낮음→ 이론적 빅 O는 같아도 실제 성능 큰 차이.
6.3 GC 부담
ArrayList 사용 후 GC:
- elementData 배열 1개 회수
- 빠름
LinkedList 사용 후 GC:
- Node 1000개 회수
- Mark + Sweep 비용 ↑
- 거대 컬렉션이면 부담 큼6.4 측정 — 실제 벤치마크
JMH (가상):
1000개 Integer add 후 순회:
ArrayList: 5 μs
LinkedList: 50 μs ← 10배 느림 (캐시 미스)
1000개 contains:
ArrayList: 5 μs
LinkedList: 100 μs ← 20배 느림
1000개 끝에 추가:
ArrayList: ~10 μs (확장 포함)
LinkedList: ~30 μs (Node 객체 생성)→ 거의 모든 작업에서 ArrayList가 빠름.
7️⃣ ILIC 실무 — LinkedList가 진짜 빛나는 곳
7.1 LinkedList 사용 시나리오 — 매우 드물다
거의 항상 ArrayList가 정답.
LinkedList가 유리한 경우:
1. 양쪽 끝에서만 add/remove
2. 인덱스 접근 거의 안 함
3. 순회만 함7.2 사용처 1 — Queue / Deque
// FIFO 큐
Queue<Task> queue = new LinkedList<>();
queue.offer(task1);
queue.offer(task2);
Task t = queue.poll(); // O(1)
// 또는 ArrayDeque (더 권장)
Queue<Task> queue = new ArrayDeque<>();→ ArrayDeque가 일반적으로 더 빠름. LinkedList는 차선.
7.3 사용처 2 — Stack 시뮬레이션
Deque<Element> stack = new LinkedList<>();
stack.push(e);
Element top = stack.pop();→ 또 ArrayDeque가 빠름.
7.4 사용처 3 — 매우 많은 양쪽 작업
// 슬라이딩 윈도우 알고리즘
Deque<Integer> window = new LinkedList<>();
// 한 쪽에서 추가, 다른 쪽에서 제거 빈번→ ArrayDeque가 더 권장.
7.5 ILIC에서의 결론
박승제씨가 ILIC에서 LinkedList 쓸 일?
거의 없음.
이유:
- ArrayList가 거의 모든 경우 더 빠름
- Queue/Deque 필요 시 ArrayDeque 권장
- 메모리 효율도 LinkedList가 나쁨
LinkedList의 진짜 가치:
교육용 (자료구조 학습)
Deque 인터페이스 구현체 중 하나
알고리즘 문제 풀 때 가끔7.6 ArrayList vs LinkedList 의사결정
ArrayList 선택:
- 인덱스 접근 필요
- 끝에만 추가
- 순회 빈도 높음
- 메모리 효율 중요
- 멀티스레드 안 함
LinkedList 선택:
- 양쪽 끝 빈번 작업
- 인덱스 접근 안 함
- (사실 ArrayDeque가 더 나음)7.7 ArrayDeque — LinkedList의 대안
// LinkedList 대신
Deque<Shipment> deque = new ArrayDeque<>();
// O(1) 양쪽 끝 작업
deque.offerFirst(s);
deque.offerLast(s);
deque.pollFirst();
deque.pollLast();ArrayDeque 장점:
- 내부 배열 기반 → 캐시 효율 ↑
- Node 객체 생성 없음 → 메모리 효율 ↑
- 양쪽 끝 작업 O(1)
- 메모리 효율 ArrayList 수준
ArrayDeque 한계:
- 중간 작업 비효율 (그래도 ArrayList 수준)
- Queue 인터페이스에 null 추가 불가
→ Deque/Stack 필요 시 ArrayDeque 최우선.
7.8 ILIC 권장 의사결정
// 일반 컬렉션 → ArrayList
List<Shipment> shipments = new ArrayList<>();
// Queue/Deque → ArrayDeque
Deque<Task> taskQueue = new ArrayDeque<>();
// LinkedList → 거의 사용 X박승제씨 코드 리뷰 체크리스트에 추가:
- "LinkedList 보이면 이유 물어보기"
- "대체로 ArrayList 또는 ArrayDeque로 변경"
8️⃣ 흔한 실수 + 디버깅
실수 1 — LinkedList에 인덱스 루프
LinkedList<Shipment> list = ...;
for (int i = 0; i < list.size(); i++) {
process(list.get(i)); // O(n²)!
}해결:
for (Shipment s : list) { // O(n)
process(s);
}실수 2 — "삽입/삭제 많으니 LinkedList" 라는 오해
// ❌ 잘못된 추론
List<Item> list = new LinkedList<>(); // "삽입/삭제 많아서"
// 그런데 코드 보면:
for (int i = 0; i < list.size(); i++) {
if (list.get(i).needsRemoval()) {
list.remove(i); // 위치 찾기 O(n) + 삭제 O(1) = O(n) 매번
}
}→ 위치 찾기 O(n)이 결국 시간 잡아먹음.
→ ArrayList도 O(n)이지만 캐시 효율 좋아서 더 빠름.
해결:
- ArrayList.removeIf() 사용
- 또는 Iterator.remove()
실수 3 — LinkedList를 List로 받아 인덱스 사용
public void process(List<Shipment> list) {
for (int i = 0; i < list.size(); i++) { // 호출자가 LinkedList 넘기면 O(n²)
// ...
}
}해결:
- API에서 for-each 강제 (RandomAccess 인터페이스 확인)
- Stream 사용
public void process(List<Shipment> list) {
list.forEach(this::handle); // 어떤 List든 O(n)
}실수 4 — Node를 외부에 노출
// ❌ 다행히 자바 LinkedList는 Node를 노출 안 함
// 만약 직접 LinkedList 구현 시 Node를 public으로 두면 위험자바의 LinkedList 는 Node 클래스를 private static으로 캡슐화.
→ 외부에서 Node 직접 접근 불가.
→ 안전.
실수 5 — null 요소
LinkedList<Shipment> list = new LinkedList<>();
list.add(null); // ✓ LinkedList는 null 허용
ArrayDeque<Shipment> deque = new ArrayDeque<>();
deque.offer(null); // ❌ NullPointerException→ ArrayDeque는 null 거부.
→ LinkedList는 null 허용 (대부분 컬렉션).
이 차이로 인해 ArrayDeque로 마이그레이션 시 주의.
실수 6 — LinkedList 직렬화 위험
LinkedList<Shipment> list = ...;
// 직렬화 시 N개 Node 모두 직렬화 → 큰 데이터
ArrayList<Shipment> list = ...;
// 배열 + 요소만 → 더 효율적→ JSON, RMI 등 직렬화 시 ArrayList가 더 효율적.
실수 7 — instanceof RandomAccess 무시
List<Shipment> list = ...; // ArrayList? LinkedList?
if (list instanceof RandomAccess) {
// ArrayList — 인덱스 접근 OK
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
} else {
// LinkedList — Iterator 사용
for (Shipment s : list) { }
}자바 표준 라이브러리의 알고리즘들이 사용:
Collections.binarySearchCollections.shuffle
자기 코드에선 보통 for-each 사용으로 충분.
9️⃣ 면접 질문 + 자기 점검
9.1 면접 단골 질문 매핑
| Q | 핵심 답변 |
|---|---|
| LinkedList 내부? | Node 사슬. first, last, size |
| Node의 구조? | item + next + prev |
| 자바는 단일/이중 연결? | 이중 연결 |
| 이중 연결 이점? | 양방향 순회, last O(1) 접근, 삭제 시 prev 자동 |
| head/tail 역할? | 시작/끝 Node 참조. O(1) 접근 |
| get(i) 시간 복잡도? | O(n). 이중 연결로 n/4 평균 |
| ArrayList 대비 메모리? | 약 8배 더 (Node 객체) |
| 캐시 효율? | LinkedList가 훨씬 떨어짐 (메모리 흩어짐) |
| 진짜 사용 시점? | 거의 없음. ArrayDeque 권장 |
| RandomAccess 인터페이스? | 인덱스 접근이 빠른 List 표시 (ArrayList O) |
9.2 자기 점검 체크리스트
기본 이해
- Node 클래스 구조를 그릴 수 있다
- 이중 연결 vs 단일 연결 차이를 안다
- head, tail, size 역할을 안다
- add/remove의 정확한 동작 (Node 연결 변경)을 추적할 수 있다
- get(i)의 최적화 (반대편에서 접근)를 안다
실전 적용
- LinkedList에 인덱스 루프 절대 안 씀
- for-each / Iterator 사용
- Queue/Deque 필요 시 ArrayDeque 우선
- LinkedList 거의 사용 안 함
- RandomAccess 인터페이스 의미 안다
면접 대비 — 5분 답변
- LinkedList 메모리 구조
- ArrayList와의 차이
- 시간 복잡도 비교
- 캐시 효율
- 실무 선택 기준
🎯 핵심 요약 — 3줄 정리
1. LinkedList = 이중 연결 Node 사슬
- Node: item + next + prev
- first(head) + last(tail) + size
- Node 객체들이 Heap에 흩어져서 화살표로 연결
2. 양쪽 끝 작업은 O(1), 인덱스는 O(n)
- add/remove first/last: O(1) — head/tail 참조 활용
- get(i): O(n) — 사슬 따라가야 함 (이중 연결로 n/4)
- 메모리는 ArrayList의 약 8배
3. 실무 — 거의 사용 안 함
- ArrayList가 보통 더 빠름 (캐시 효율)
- Queue/Deque 필요 시 ArrayDeque 권장
- LinkedList는 교육용 + 알고리즘 문제
📚 다음으로...
Unit 5.4 — 삽입/삭제 효율의 진짜 이유 (코드 검증)
이번 Unit과 Unit 5.2에서 ArrayList와 LinkedList를 따로 봤다면, 다음은 종합 비교.
핵심 질문:
"ArrayList도 LinkedList도 결국 O(n)인데, 왜 LinkedList가 삽입/삭제에 유리하다고 하는가?"
답: 비용의 종류가 다르다.
- ArrayList: 위치 찾기 O(1) + 실제 삽입/삭제 O(n) 복사
- LinkedList: 위치 찾기 O(n) + 실제 삽입/삭제 O(1) 참조 변경
코드로 검증하면서 박승제씨가 자료구조 선택 마스터.
Phase 5 진행 상황
🚀 Phase 5 — 컬렉션 내부 구조
✅ Unit 5.1 List/Set/Map의 본질적 차이
✅ Unit 5.2 ArrayList 내부
✅ Unit 5.3 LinkedList 내부 ← 여기
⏭ Unit 5.4 삽입/삭제 효율의 진짜 이유 (Phase 5 완주)
Software Developer