배열은 데이터를 한 덩어리로 붙여 놓지만, 연결 리스트(Linked List)는 데이터를 여기저기 흩어 두고 화살표로 이어요. 그 대신 맨 앞 삽입·삭제가 아주 빨라져요. 배열과 뭐가 다른지 확실히 잡아봐요.
next가 바로 이 화살표라서, 노드를 연결할 땐 값을 옮기지 않고 화살표만 다시 걸면 끝이에요.head
│
▼
[ 10 | next ] ──▶ [ 20 | next ] ──▶ [ 30 | next ] ──▶ null
// 각 칸 = 노드(값 + 다음 노드 참조)
// 마지막 노드의 next 는 null (더 이상 이어질 칸이 없다는 표시)head에서 시작해 next를 따라가면 10 → 20 → 30 순서로 지나가요. 마지막 노드의 next가 null이면 "여기가 끝"이라는 뜻이에요.
O(1)은 데이터가 아무리 많아져도 항상 한 번 만에 끝난다는 뜻이고, O(n)은 데이터 개수(n)만큼 하나씩 다 확인해야 한다는 뜻이에요. 예를 들어 연결 리스트에서 5번째 칸을 찾으려면 head부터 1·2·3·4·5번째 칸까지 한 칸씩 세며 지나가야 하니 O(n)인 거예요.연결 리스트의 부품인 노드(node)는 딱 두 가지를 들고 있어요. 하나는 담고 있는 값(data), 다른 하나는 다음 노드를 가리키는 참조(next)예요. 이 두 개만 있으면 노드들을 줄줄이 이을 수 있어요.
next가 null이고, 다른 노드와 연결되면 그때부터 그 노드를 가리키게 돼요.class Node {
constructor(data) {
this.data = data; // 이 노드가 담는 값
this.next = null; // 다음 노드를 가리키는 참조 (없으면 null)
}
}
// 노드 세 개를 손으로 이어 붙이기
const a = new Node(10);
const b = new Node(20);
const c = new Node(30);
a.next = b; // 10 ──▶ 20
b.next = c; // 20 ──▶ 30
// c.next 는 null → c 가 마지막 노드
const head = a; // 첫 노드를 head 로 잡는다a.next = b처럼 참조만 바꾸면 노드가 이어져요. 값을 옮겨 담는 게 아니라 화살표(연결)만 다시 거는 거예요.
💡 핵심은 "노드는 값 하나 + 다음 노드로 가는 화살표 하나"예요. 이 그림만 확실하면 연결 리스트의 절반은 이해한 거예요.
let cur = head; // head 부터 시작
while (cur !== null) { // 끝(null)을 만날 때까지
console.log(cur.data); // 10, 20, 30 순서로 출력
cur = cur.next; // 다음 노드로 이동
}arr[2]로 바로 못 가고, head부터 next를 따라 한 칸씩 걸어가야 해요. 이게 뒤에서 나올 인덱스 접근 O(n)의 이유예요.
배열은 데이터가 한 줄로 붙어 있어서 인덱스로 위치를 바로 계산할 수 있어요. 그래서 arr[5] 접근이 O(1)이에요. 대신 중간에 값을 끼우거나 빼면 뒤 요소를 전부 밀어야 하니 O(n)이에요.
연결 리스트는 반대예요. 데이터가 흩어져 있어 인덱스로 바로 못 가고 head부터 따라가야 하므로 접근이 O(n)이에요. 하지만 맨 앞에 노드를 끼우거나 빼는 건 화살표(연결)만 바꾸면 되니 O(1)이에요.
| 연산 | 배열 (Array) | 연결 리스트 (Linked List) |
|---|---|---|
인덱스로 접근 get(i) | O(1) 바로 계산 | O(n) head부터 따라감 |
| 맨 앞 삽입/삭제 | O(n) 전부 밀어야 함 | O(1) 연결만 바꿈 |
| 맨 뒤 삽입 (tail 알 때) | O(1) 보통 | O(1) tail 알 때 |
| 값 탐색 (찾기) | O(n) | O(n) |
| 메모리 배치 | 연속(한 덩어리) | 흩어짐 + next 참조 저장 |
// head 앞에 값 5 를 새로 끼우기
function pushFront(head, value) {
const node = new Node(value);
node.next = head; // 새 노드가 기존 head 를 가리키게
return node; // 새 노드가 새로운 head 가 됨
}
// [10]▶[20]▶null 에서
// head = pushFront(head, 5) → [5]▶[10]▶[20]▶null[10 | next] ──▶ [20 | next] ──▶ [30 | next] ──▶ nullnull ◀── [prev | 10 | next] ◀──▶ [prev | 20 | next] ──▶ null
// 각 노드가 prev 와 next 를 모두 가짐 → 뒤로도 이동 가능arr[i]처럼 무작위 접근이 많으면 배열이 훨씬 나아요.