연결 리스트
연결 리스트 맨 앞에 값을 넣을 때는 포인터 두 개만 바꾸면 됩니다. 값이 4개든 400만 개든 마찬가지입니다.
다음 값을 가리키는 값
배열은 값을 나란히 붙여 두기 때문에 앞쪽을 바꾸기가 비쌉니다. 연결 리스트는 이 규칙을 버립니다. 값 하나하나가 노드라는 작은 기록에 따로 담기고, 노드는 메모리 어디에 있어도 됩니다. MIT 6.006 강의 노트는 노드에 두 칸이 있다고 설명합니다. 항목(item)과, 다음 노드를 가리키는 포인터 next입니다. 리스트 자체는 첫 노드만 기억하는데, 이것을 head라고 합니다. 마지막 노드의 next는 null이고, 이것이 끝을 나타냅니다.
리스트를 읽으려면 head에서 출발해 next 포인터를 하나씩 따라갑니다. 다음 쪽지가 숨은 곳이 적힌 쪽지를 차례로 찾아가는 것과 같습니다. 여기에는 비용이 따릅니다. 네 번째 노드의 주소를 구하는 공식이 없으므로 i번 자리의 값을 얻으려면 노드 i + 1개를 방문해야 합니다. MIT는 연결 리스트의 get at(i)를 O(n)으로 적습니다. 배열은 한 단계면 됐습니다.
// one node per value: { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// walk the list
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4포인터를 다시 이어 바꾸기
이득은 리스트를 바꿀 때 나옵니다. 맨 앞에 새 값을 넣으려면 next가 지금의 head를 가리키는 노드를 만들고, head가 새 노드를 가리키게 합니다. 포인터 두 개를 바꿀 뿐 다른 것은 움직이지 않습니다. 맨 앞 노드를 지우는 일은 한 번만 바꾸면 됩니다. head가 head.next를 가리키게 하면 됩니다. 같은 연산에서 배열은 모든 값을 옮겼습니다.
가운데에서는 자리를 찾는 일이 대부분입니다. i번 자리에 넣으려면 바로 앞 노드까지 걸어간 뒤(방문 i번) 같은 방식으로 포인터 두 개를 바꿉니다. new.next = prev.next를 먼저, prev.next = new를 나중에 합니다. 순서가 중요합니다. prev.next를 먼저 바꾸면 나머지 리스트를 가리키는 것이 없어져 잃어버립니다. 실험실에서 한 단계는 노드 하나 방문 또는 포인터 하나 바꾸기이므로, 노드 4개짜리 리스트의 2번 자리에 넣으면 방문 2번과 바꾸기 2번, 4단계입니다.
끌어서 돌리고, 휠이나 두 손가락으로 확대하세요.
| 연산 | 배열(값 n개) | 연결 리스트(노드 n개) |
|---|---|---|
| i번 자리 값 가져오기 | 1 | 방문 i + 1번 |
| 맨 앞에 넣기 | 옮기기 n + 쓰기 1 | 포인터 바꾸기 2번 |
| 맨 앞 지우기 | 읽기 1 + 옮기기 (n − 1) | 포인터 바꾸기 1번 |
| i번 자리에 넣기 | 옮기기 (n − i) + 쓰기 1 | 방문 i번 + 바꾸기 2번 |
| 값 찾기 | 최대 n번 읽기 | 최대 n번 방문 |
언제 쓸까
연결 리스트는 바꾸는 일이 대부분 이미 포인터를 쥐고 있는 곳(맨 앞 같은 곳)에서 일어나고, i번 자리를 찾을 일이 드물 때 잘 맞습니다. 큐와 스택을 연결 리스트로 만들 수 있고, 다음 단원 해시 테이블 속 사슬도 연결 리스트입니다. 변형도 있습니다. 이중 연결 리스트는 노드마다 prev 포인터도 두어 뒤로 걸어갈 수 있고, 노드를 쥐고 있으면 한 단계에 지울 수 있습니다. head와 함께 tail 포인터도 두면 끝에 넣기가 싸집니다.
평소 자바스크립트에서는 연결 리스트를 직접 쓸 일이 드뭅니다. 배열이 잘 최적화되어 있고, 요즘 프로세서의 캐시는 나란히 붙은 값을 더 빨리 읽기 때문입니다. 그래도 이 생각은 중요합니다. 트리, 그래프, 여러 라이브러리 자료 구조가 바로 이런 노드와 포인터로 만들어집니다.
- 단일 연결 리스트의 노드에는 어떤 두 칸이 있을까요?
- 항목과 next
- 번호와 값
- left와 right
- head와 tail
- 리스트 12 → 7 → 30 → 4에서 맨 앞에 새 값을 넣으면 몇 단계일까요(포인터 바꾸기)?
- 같은 리스트에서 2번 자리에 넣으면 몇 단계일까요(방문과 포인터 바꾸기 합)?
- 같은 리스트에서 30을 찾으면 노드를 몇 개 방문할까요?
- 같은 리스트에서 99를 찾으면 null에 닿기 전까지 노드를 몇 개 방문할까요?
- 같은 리스트에서 3번 자리 노드(4)를 지우면 몇 단계일까요?
- 빈칸이 넉넉한 배열에 값 1,000개가 있습니다. 맨 앞에 넣으면 몇 단계일까요?
- 배열보다 연결 리스트가 더 잘 맞는 일은?
- 500번 자리 값을 여러 번 읽기
- 맨 앞에서 여러 번 넣고 빼기
- 이진 탐색
- 번호로 정렬하기
- 노드 p 뒤에 넣을 때 나머지 리스트를 잃지 않는 순서는?
- p.next = new 다음에 new.next = p.next
- new.next = p.next 다음에 p.next = new
- 어느 순서든 된다
- p를 먼저 지운다
- 1956년 무렵 RAND에서 만들어져 칸을 이어 붙인 리스트 처리를 처음 선보인 언어는?
- 포트란
- IPL
- C
- 자바스크립트
- 연결 리스트는 값마다 next 포인터가 있는 노드에 담고, 리스트는 head를 기억합니다.
- 맨 앞에서 넣거나 지우면 포인터 1~2개만 바뀌고 아무것도 옮기지 않습니다.
- i번 자리에 가려면 i + 1번 방문하므로 get at(i)는 O(n)입니다.
- 앞 노드를 다시 잇기 전에 new.next부터 정합니다.
이 과정의 출처 (5)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon), lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append), 4 Hashing (chaining, pigeonhole collisions, chain length n/m), 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1), Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262), 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements"), Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
확인한 날: 2026-10-18