핵심 인사이트 (3줄 요약)
- 본질: 연결 리스트 (Linked List)는 각 노드가 데이터와 다음 노드 포인터를 보유하여 메모리 비연속적으로 체인을 이루는 선형 자료구조로, 임의 위치 삽입·삭제가 O(1)이다.
- 가치: 배열과 달리 원소 이동 없이 포인터 변경만으로 삽입·삭제가 완료되므로, 삽입·삭제가 빈번한 LRU 캐시·undo/redo 스택에서 실질적 이점을 가진다.
- 판단 포인트: 인덱스 기반 임의 접근이 필요하면 배열, 잦은 중간 삽입·삭제가 필요하면 연결 리스트를 선택한다. 캐시 효율은 배열이 우수하다.
Ⅰ. 개요 및 필요성
배열은 연속 메모리를 요구하므로 중간 삽입 시 O(n) 원소 이동이 발생한다. 연결 리스트는 각 노드를 힙의 임의 위치에 할당하고 포인터로 연결함으로써 이 문제를 해결한다. 삽입·삭제 지점의 포인터만 변경하면 되므로 O(1) 조작이 가능하다(단, 삽입 위치에 도달하는 탐색 비용은 O(n)).
연결 리스트의 시간 복잡도
| 연산 | 단일 연결 | 이중 연결 |
|---|---|---|
| 접근 (index) | O(n) | O(n) |
| 헤드 삽입/삭제 | O(1) | O(1) |
| 테일 삽입 | O(n)* | O(1) |
| 중간 삽입/삭제 | O(n) 탐색 + O(1) | O(n) 탐색 + O(1) |
*테일 포인터를 별도 유지 시 O(1)
📢 섹션 요약 비유: 연결 리스트는 각자 "다음 사람이 누구인지" 적은 명찰을 달고 있는 줄 서기다. 새 사람을 중간에 끼우려면 앞사람 명찰만 바꾸면 된다.
Ⅱ. 아키텍처 및 핵심 원리
단일 연결 리스트 (Singly Linked List)
HEAD
│
▼
┌──────┬────┐ ┌──────┬────┐ ┌──────┬──────┐
│ 10 │ ●──┼──▶│ 20 │ ●──┼──▶│ 30 │ NULL │
└──────┴────┘ └──────┴────┘ └──────┴──────┘
Node(data=10) Node(data=20) Node(data=30)
각 노드: {data, next} — 한 방향 탐색만 가능
이중 연결 리스트 (Doubly Linked List)
HEAD TAIL
│ │
▼ ▼
┌────┬────┬────┐ ┌────┬────┬────┐ ┌────┬────┬────┐
│NULL│ 10 │ ●──┼──▶│ ●──│ 20 │ ●──┼──▶│ ●──│ 30 │NULL│
└────┴────┴────┘◀──┼────┘ └────┘◀──┼────┘ └────┘
prev data next prev data next prev data next
각 노드: {prev, data, next} — 양방향 탐색 가능, 삭제 시 이전 노드를 O(1)에 찾음
순환 연결 리스트 (Circular Linked List)
┌──────┬────┐ ┌──────┬────┐ ┌──────┬────┐
│ 10 │ ●──┼──▶│ 20 │ ●──┼──▶│ 30 │ ●──┼──┐
└──────┴────┘ └──────┴────┘ └──────┴────┘ │
▲ │
└────────────────────────────────────────┘
마지막 노드의 next가 첫 번째 노드를 가리킴. 라운드-로빈 스케줄링, 순환 버퍼에 활용.
삽입 예시: 노드 B를 A와 C 사이에 삽입 (단일)
Before: A → C
After: A → B → C
코드:
B.next = A.next // B가 C를 가리킴
A.next = B // A가 B를 가리킴
📢 섹션 요약 비유: 이중 연결 리스트는 양쪽 손을 잡고 서 있는 사람들의 줄—앞뒤 모두 잡을 수 있어 빠진 사람을 채우거나 빼기가 더 쉽다.
Ⅲ. 비교 및 연결
배열 vs 단일 vs 이중 연결 리스트
| 항목 | 배열 | 단일 연결 | 이중 연결 |
|---|---|---|---|
| 임의 접근 | O(1) | O(n) | O(n) |
| 헤드 삽입 | O(n) | O(1) | O(1) |
| 중간 삽입 | O(n) | O(n) | O(n) |
| 역방향 탐색 | O(n) 역변환 | ❌ 불가 | O(1) |
| 메모리 오버헤드 | 없음 | next 포인터 1개 | prev/next 2개 |
| 캐시 효율 | 높음 | 낮음 | 낮음 |
실제 응용: LRU 캐시 (Least Recently Used Cache)
LRU 캐시는 이중 연결 리스트 + 해시맵으로 O(1) get/put을 구현한다.
- 해시맵: key → 노드 포인터 (O(1) 검색)
- 이중 연결 리스트: 접근 순서 유지, 헤드에 최신, 테일에 최오래 (O(1) 이동·삭제)
해시맵: {A→node_A, B→node_B, C→node_C}
연결리스트: [최신]C ↔ A ↔ B[최오래]
용량 초과 시 테일(B) 제거
📢 섹션 요약 비유: LRU 캐시는 최근에 쓴 물건을 책상 위에 두고, 가장 오래된 물건을 서랍 맨 뒤로 넣는 정리 습관이다.
Ⅳ. 실무 적용 및 기술사 판단
주요 활용 사례
- LRU / LFU 캐시: 운영체제 페이지 교체 알고리즘, Redis 캐시 제거 정책
- Undo/Redo: 텍스트 편집기의 변경 이력 (양방향 탐색 필요 → 이중 연결)
- 파일 시스템: inode 블록 체인, 디렉터리 엔트리
- Java LinkedList:
java.util.LinkedList는 이중 연결 리스트로 Deque 인터페이스 구현 - 메모리 할당자: Free list (가용 블록 연결 리스트)
기술사 판단 기준
캐시 히트율 중요 + 인덱스 접근 필요 → 배열 / ArrayList
삽입/삭제 O(1) + 순서 유지 필요 → 이중 연결 리스트
스택/큐 구현 (헤드만 조작) → 단일 연결 리스트
순환 처리 (라운드-로빈) → 순환 연결 리스트
📢 섹션 요약 비유: 연결 리스트는 유연하지만 원하는 항목을 찾으려면 처음부터 따라가야 한다—색인 없는 소설책처럼 특정 페이지를 찾으려면 앞에서 넘겨야 한다.
Ⅴ. 기대효과 및 결론
연결 리스트는 포인터 조작으로 O(1) 삽입·삭제를 달성하는 대신, O(n) 임의 접근과 캐시 미스 증가라는 트레이드오프를 감수한다. 이중 연결 리스트는 역방향 탐색을 추가하여 LRU 캐시·deque 구현에 적합하며, 순환 연결 리스트는 끝없는 반복 처리에 유리하다.
결론: 삽입·삭제 위주 + 순차 접근 패턴에 적합하며, 특히 LRU 캐시처럼 해시맵과 결합할 때 O(1) get/put의 진가를 발휘한다.
📌 관련 개념 맵
| 개념 | 관계 |
|---|---|
| 배열 (Array) | 연속 메모리 대안, 인덱스 O(1) |
| 스택 (Stack) | 단일 연결 리스트로 구현 가능 |
| 큐 (Queue) | 단일/이중 연결 리스트로 구현 |
| LRU 캐시 | 이중 연결 리스트 + 해시맵 |
| 해시 테이블 (Hash Table) | 체이닝 시 버킷을 연결 리스트로 |
| 건너뜀 리스트 (Skip List) | 다층 연결 리스트 |
📈 관련 키워드 및 발전 흐름도
[배열 (Array)]
│
▼
[스택 (Stack)]
│
▼
[큐 (Queue)]
│
▼
[LRU 캐시]
│
▼
[해시 테이블 (Hash Table)]
이 흐름도는 배열 (Array)에서 출발해 건너뜀 리스트 (Skip List)까지 이어지며, 중간 단계가 기초 개념을 실무 구조로 발전시키는 과정을 보여준다.
👶 어린이를 위한 3줄 비유 설명
- 연결 리스트는 보물찾기 쪽지야—각 쪽지에 "다음 단서는 저기"라고 적혀서 하나씩 따라가야 해.
- 이중 연결 리스트는 앞뒤 이웃 집 주소를 모두 아는 마을이라 뒤로도 걸어갈 수 있어.
- 중간에 새 집을 짓고 싶으면 앞뒤 이웃 주소만 바꾸면 되니까 훨씬 쉬워!