통합 요약노트
Ch.5 연결 리스트
노드와 포인터, Reverse, Fast & Slow, LRU Cache
이 챕터의 내용
노드와 포인터 — ListNode의 탄생
각 데이터가 다음 데이터의 주소를 기억하면 어디든 연결할 수 있습니다. 이것이 포인터의 힘입니다.
기차를 떠올려봅시다. 각 칸은 다음 칸과 연결되어 있습니다
배열은 연속 메모리에 저장하지만 연결 리스트는 흩어진 메모리를 포인터로 연결합니다
연결 리스트의 핵심: 각 노드는 데이터(val)와 다음 노드 주소(next)를 가진다
삽입과 삭제 — 연결 리스트의 진짜 강점
dummy head(가짜 노드)를 쓰면 모든 삽입/삭제를 하나의 로직으로 처리할 수 있습니다.
리스트 맨 앞에 새 노드를 삽입합니다
시간 복잡도: O(1) 포인터 연결만 바꾸면 끝입니다
특정 위치에 삽입하려면 이전 노드(prev)를 먼저 찾아야 합니다
Reverse Linked List — 3포인터의 마법
prev, curr, next 세 변수를 동시에 유지하면 안전하게 방향을 바꿀 수 있습니다.
연결 방향을 바꾸려면 3개의 포인터가 필요합니다
4단계 반복: 저장(nxt) → 뒤집기(curr.next=prev) → 전진(prev, curr) — 시간 O(n), 공간 O(1)
재귀로도 뒤집을 수 있습니다. 끝까지 간 뒤 돌아오면서 방향을 바꿉니다
Fast & Slow 포인터 — 토끼와 거북이
사이클이 있으면 fast가 slow를 반드시 따라잡습니다. 이것이 Floyd's Cycle Detection입니다.
리스트의 중간 노드를 찾으려면 길이를 모를 때 어떻게 할까요?
fast가 2배 빠르므로, fast가 끝에 도달할 때 slow는 정확히 절반 위치입니다
리스트에 사이클이 있으면 fast가 끝에 도달하지 못합니다
이중 연결리스트 & LRU Cache
HashMap으로 O(1) 조회 + DLL로 O(1) 삽입/삭제 = LRU Cache의 완성입니다.
이중 연결리스트는 prev + next 두 방향의 포인터를 가집니다
캐시가 꽉 찼을 때 가장 오래 안 쓴 데이터를 삭제합니다
최근 사용한 데이터는 앞으로, 오래된 데이터는 뒤로 밀립니다
면접실전 — Linked List 핵심 문제 5선
각 문제의 핵심 패턴을 정리하고, 면접에서 어떻게 설명할지 연습합니다.
LeetCode 206 Reverse Linked List
패턴: 3포인터(prev/curr/nxt) — 연결 리스트 면접의 기본 중 기본
LeetCode 21 Merge Two Sorted Lists
챕터5 종합퀴즈 — Linked List 마스터
패턴을 정확히 매칭하면, 처음 보는 문제도 기존 패턴의 변형임을 알 수 있습니다.
ListNode 클래스의 두 필드는?
연결 리스트에서 head 앞에 새 노드를 삽입하는 시간 복잡도는?
배열 대비 연결 리스트의 가장 큰 단점은?
- ListNode: val + next, 순회는 while curr
- 삽입/삭제: 포인터 순서 중요, dummy head로 엣지 케이스 제거
- Reverse: prev/curr/nxt 3포인터 — O(n) 시간, O(1) 공간
- Fast & Slow: 중간 노드 + Floyd's 사이클 탐지
- DLL + HashMap = LRU Cache — 모든 연산 O(1)
핵심 용어 모음
노드(Node)
데이터 + 다음 노드 주소를 담는 단위
포인터(next)
다음 노드의 메모리 주소를 가리키는 참조
head
리스트의 첫 번째 노드를 가리키는 변수
Fast 포인터
한 번에 2칸씩 이동
Slow 포인터
한 번에 1칸씩 이동
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기