각 노드가 값과 다음 노드를 가리키는 포인터를 가지고 사슬처럼 이어진 자료구조. 리스트는 맨 앞(Head)과 맨 뒤(Tail), 길이 정도만 기억한다. 배열과 달리 인덱스가 없다.
class Node<T> { next: Node<T> | null = null; constructor(public val: T) {} }
class LinkedList<T> {
head: Node<T> | null = null
tail: Node<T> | null = null
length = 0
push(val: T) {
const node = new Node(val)
if (!this.tail) this.head = this.tail = node
else { this.tail.next = node; this.tail = node }
this.length++
}
}배열과 비교
| 연산 | 배열 | 연결 리스트 |
|---|---|---|
| i번째 접근 | O(1) | O(n), 앞에서부터 따라간다 |
| 맨 앞에 추가·삭제 | O(n), 전부 민다 | O(1) |
| 맨 뒤에 추가 | O(1) | O(1), tail이 있으면 |
이중 연결 리스트
이중 연결 리스트(Doubly Linked List)는 노드가 이전 노드 포인터(prev)도 가진다. 메모리를 더 쓰는 대신 뒤에서부터 탐색할 수 있고, 맨 뒤 삭제도 O(1)이 된다(단일 연결 리스트(Singly Linked List)는 tail 바로 앞 노드를 찾으려고 처음부터 걸어야 한다). 브라우저의 뒤로·앞으로 기록, 최근 사용 순서를 관리하는 LRU 캐시에 쓴다.
자주 하는 연산: 뒤집기(포인터 세 개로 방향을 바꾸며 한 바퀴), 중간에 삽입·삭제(앞 노드를 찾은 뒤 포인터만 바꾼다). 스택과 큐를 구현하는 바탕이 되고, 해시 테이블의 충돌 처리에도 쓰인다. 복잡도 감각은 빅오 표기법.