각 노드가 다음 노드를 포인터로 가리킵니다. 위치를 계산할 수 없어 순차 접근만 되고, 대신 삽입과 삭제에서 원소를 밀지 않습니다.
연결 리스트 (Linked List)
구조
단일 연결 리스트:
[10|→] → [20|→] → [30|→] → null
head
이중 연결 리스트:
null ← [←|10|→] ⇄ [←|20|→] ⇄ [←|30|→] → null
head tail
시간 복잡도
| 연산 | 복잡도 | 이유 |
|---|
| 앞에 삽입 | O(1) | head 포인터만 변경 |
| 뒤에 삽입 | O(1) | tail 포인터 있을 때 |
| 중간 삽입 | O(n) | 위치까지 순회 필요 |
| 인덱스 접근 | O(n) | 순차 탐색만 가능 |
| 삭제 | O(1) | 노드 참조 있을 때 |
배열 vs 연결 리스트
| 항목 | 배열 | 연결 리스트 |
|---|
| 메모리 | 연속 할당 | 분산 할당 |
| 캐시 효율 | 높음 | 낮음 |
| 삽입/삭제 | O(n) | O(1) |
| 랜덤 접근 | O(1) | O(n) |
중간 삽입이 빠르다는 말의 조건
노드를 알고 있으면 잇는 것은 즉시 끝납니다. 다만 그 노드를 찾는 것은 앞에서부터 세어야
합니다.
| 하려는 것 | 실제 비용 |
|---|
| 이미 손에 든 노드 뒤에 넣기 | 즉시 |
| 다섯 번째 뒤에 넣기 | 다섯 번 걸어간 다음 즉시 |
| 특정 값을 찾아 지우기 | 찾는 데 전체를 훑을 수 있다 |
그래서 이 자료구조는 순회하면서 넣고 빼는 경로에서 값이 있습니다. 위치로 접근하는
경로에서는 배열이 낫습니다. 표기상 같은 O(1) 이라도 조건이 다릅니다.
흩어져 있는 대가
노드가 메모리 곳곳에 있어 순서대로 훑어도 붙어 있는 배열보다 느립니다.
노드마다 다음 위치를 따라가야 한다
가져온 덩어리 안에 다음 노드가 있을 보장이 없다
노드마다 다음을 가리키는 공간이 따로 든다
셋째도 작지 않습니다. 작은 값을 많이 담으면 값보다 연결 정보가 차지하는 몫이 커집니다.
그래서 실무 목록은 대부분 배열 기반입니다.
실무 포인트
- Java
LinkedList: Deque 인터페이스 구현 (큐/스택 모두 가능)
- LRU 캐시: 이중 연결 리스트 + 해시맵 조합
- 실무에서는 캐시 지역성 때문에 ArrayList가 대부분 빠름
Q.연결 리스트의 장단점을 설명해주세요
크기가 유연하고 삽입과 삭제가 싸지만, 임의 접근과 캐시 효율을 포기합니다.
| 항목 | 내용 |
|---|
| 장점 | 미리 크기를 정할 필요가 없다 |
| 장점 | 노드를 들고 있으면 삽입과 삭제가 O(1) |
| 장점 | 확장할 때 전체를 복사하지 않는다 |
| 단점 | i번째 원소를 O(n)에 찾는다 |
| 단점 | 노드마다 포인터와 헤더가 붙어 메모리를 더 쓴다 |
| 단점 | 노드가 흩어져 순회 시 캐시 미스가 잦다 |
흔한 실수: "삽입과 삭제가 O(1)"만 외우는 것. 그 위치를 찾는 비용이 따로 들고, 인덱스로 찾는다면 탐색이 O(n)이라 이득이 사라집니다. O(1)이 성립하는 것은 이미 그 노드를 참조하고 있을 때입니다.
Q.LRU 캐시를 연결 리스트로 구현하는 방법은?
이중 연결 리스트와 해시 맵을 함께 씁니다. 둘 다 있어야 모든 연산이 O(1)이 됩니다.
| 자료구조 | 역할 |
|---|
| 해시 맵 | 키에서 노드를 O(1)에 찾는다 |
| 이중 연결 리스트 | 최근 사용 순서를 유지한다. 맨 앞이 최신 |
| 동작 | 처리 |
|---|
| 조회 | 맵에서 노드를 찾아 리스트 맨 앞으로 옮긴다 |
| 저장 | 맨 앞에 넣는다. 용량을 넘으면 맨 뒤를 버리고 맵에서도 지운다 |
이중인 이유는 노드를 떼어낼 때 앞 노드를 알아야 하기 때문입니다. 단일 연결이면 앞 노드를 찾으려고 처음부터 훑어야 해서 O(n)이 됩니다.
흔한 실수: 해시 맵만으로 만들려는 것. 맵은 순서를 모르므로 무엇을 버릴지 고를 수 없습니다. 반대로 리스트만 쓰면 조회가 O(n)입니다.
Q.단일 vs 이중 연결 리스트 차이는?
노드가 다음만 가리키는지, 이전까지 가리키는지의 차이입니다. 그 차이가 삭제 비용을 가릅니다.
| 항목 | 단일 | 이중 |
|---|
| 노드당 포인터 | 1개 | 2개 |
| 역방향 순회 | 불가능 | 가능 |
| 특정 노드 삭제 | 앞 노드를 찾아야 해서 O(n) | 앞을 알고 있어 O(1) |
| 메모리 | 더 적다 | 포인터 하나만큼 더 쓴다 |
그래서 LRU 캐시나 OS의 대기 큐처럼 중간 노드를 자주 떼어내는 곳은 이중을 씁니다. 한 방향으로만 훑고 버리는 구조라면 단일이 가볍습니다.
흔한 실수: 단일 연결에서 노드 삭제가 불가능하다고 답하는 것. 지울 노드의 다음 값을 현재 노드에 복사하고 다음 노드를 떼는 우회법이 있습니다. 다만 마지막 노드에는 쓸 수 없습니다.
Q.연결 리스트에서 사이클을 검출하는 방법은?
두 포인터를 다른 속도로 움직입니다. 한 칸씩 가는 것과 두 칸씩 가는 것을 함께 보냅니다.
| 포인터 | 이동 |
|---|
| 느린 쪽 | 한 번에 한 칸 |
| 빠른 쪽 | 한 번에 두 칸 |
| 경우 | 결과 |
|---|
| 사이클이 없다 | 빠른 쪽이 끝에 먼저 닿는다 |
| 사이클이 있다 | 빠른 쪽이 고리를 돌다가 느린 쪽을 반드시 따라잡는다 |
매 걸음마다 둘의 간격이 1씩 줄어들기 때문에 고리 안에서는 반드시 만납니다. 시간은 O(n)이고 추가 메모리는 상수입니다.
방문한 노드를 집합에 담는 방법도 O(n)이지만 메모리를 n만큼 씁니다. 면접에서 원하는 답은 대개 두 포인터입니다.
흔한 실수: 만나는 지점을 사이클의 시작점이라고 답하는 것. 만난 뒤 한 포인터를 머리로 되돌리고 둘을 한 칸씩 움직이면 그때 만나는 곳이 시작점입니다.
먼저 스스로 답해보고 아래 답변과 견줘보세요. 막히는 부분은 문제로 확인할 수 있어요.
읽었으면 문제로 확인해보세요
자료구조 문제를 풀면 틀린 문제가 자동으로 노트에 쌓입니다. 가입 없이 5문제를 먼저 풀어볼 수도 있어요.