알고리즘 - 10. 연결 리스트
algorithmsdata-structureslinked-listpointersdynamic-memory
By sko•10/7/2025•2 min read
연결 리스트를 사용하는 시기
연결 리스트는 알려진 위치에서 효율적인 삽입/삭제가 필요한 동적 크기가 필요할 때 사용합니다. 배열은 무작위 액세스에 뛰어나지만, 연결 리스트는 다음과 같은 경우에 적합합니다:
- 앞쪽에서 빈번한 삽입/삭제 (클래식 사용 사례)
- 스택과 큐 구현 (O(1) 연산)
- 실행 취소 기능 (작업 기록 유지)
- 음악 재생 목록 (다음/이전 탐색)
- 브라우저 기록 (앞으로/뒤로 탐색)
- 자주 요소를 추가/제거하고 무작위 액세스가 필요 없는 모든 문제
예제 문제
텍스트 에디터 실행 취소 시스템: 무제한 실행 취소/다시 실행 기능을 위해 모든 편집 작업을 추적해야 하는 텍스트 에디터를 만들고 있습니다.
- 사용자가 "Hello" 입력 (5개 작업)
- 사용자가 "lo" 삭제 (2개 작업)
- 사용자가 " World" 입력 (6개 작업)
- 사용자가 마지막 3개 작업 실행 취소를 원함
답변: 연결 리스트는 작업 순서를 완벽하게 유지하여 새 작업의 O(1) 삽입과 실행 취소 작업을 위한 쉬운 역방향 순회를 허용합니다. 배열과 달리 사용하지 않을 수도 있는 공간을 미리 할당하여 메모리를 낭비하지 않습니다.
가장 중요한 통찰력
연결 리스트는 무작위 액세스를 O(1) 시간에 어디서나 삽입/삭제할 수 있는 능력과 교환합니다 - 그리고 경계에서 더미 노드를 사용하여 작업 지점 전후에 항상 노드가 있기 때문에 모든 엣지 케이스를 제거합니다.
멘탈 노트: 연결 리스트의 천재성은 포인터 기반 연결에 있습니다. 각 노드는 즉각적인 이웃만 알고 있어 체인을 만듭니다. 이 로컬 지식은 몇 개의 포인터만 업데이트하여 노드를 삽입하거나 제거할 수 있음을 의미합니다 - 요소 이동이 필요 없습니다. 더미 노드 패턴은 null head/tail을 처리하지 않도록 보장하여 모든 작업을 균일하게 만듭니다.
의사 결정 프레임워크
모든 연결 리스트 작업에서 결정은 포인터 조작에 관한 것입니다:
- 삽입: 새 노드를 체인에 엮기 위해 포인터 업데이트
- 삭제: 대상 노드를 우회하기 위해 포인터 업데이트
- 순회: 한 번에 한 노드씩 체인을 따라감
- 엣지 케이스 제거: 균일한 작업을 보장하기 위해 더미 노드 사용
코드
더미 노드가 있는 단일 연결 리스트
// 리스트의 각 요소는 값과 다음 포인터를 가진 "노드"
class ListNode {
constructor(value) {
this.value = value;
this.next = null; // 체인의 다음 노드를 가리킴
}
}
class LinkedList {
constructor() {
// 더미 헤드는 영구적인 "시작" 마커처럼 작동
this.dummyHead = new ListNode("START");
this.tail = this.dummyHead; // 테일은 마지막 노드를 추적
}
// push: 끝에 추가 (array.push처럼)
push(value) {
const newNode = new ListNode(value);
// 의사 결정 프레임워크: 단순히 테일에 연결
this.tail.next = newNode; // 현재 마지막 노드가 새 노드를 가리킴
this.tail = newNode; // 테일을 새 마지막 노드로 업데이트
}
// pop: 끝에서 제거 (array.pop처럼)
pop() {
// 의사 결정 프레임워크: 리스트가 비어있는지 확인
if (this.dummyHead.next === null) {
return undefined;
}
// 두 번째 마지막 노드 찾기
let current = this.dummyHead;
while (current.next !== this.tail) {
current = current.next;
}
// 반환할 값 저장
const poppedValue = this.tail.value;
// 마지막 노드 제거
current.next = null;
this.tail = current;
return poppedValue;
}
// unshift: 앞에 추가 (array.unshift처럼)
unshift(value) {
const newNode = new ListNode(value);
// 의사 결정 프레임워크: 더미 바로 뒤에 삽입
const oldFirst = this.dummyHead.next;
newNode.next = oldFirst; // 새 노드가 이전 첫 번째를 가리킴
this.dummyHead.next = newNode; // 더미가 새 노드를 가리킴
// 리스트가 비어있었다면 테일 업데이트
if (this.tail === this.dummyHead) {
this.tail = newNode;
}
}
// shift: 앞에서 제거 (array.shift처럼)
shift() {
// 의사 결정 프레임워크: 리스트가 비어있는지 확인
if (this.dummyHead.next === null) {
return undefined;
}
const firstNode = this.dummyHead.next;
const shiftedValue = firstNode.value;
// 첫 번째 노드 우회
this.dummyHead.next = firstNode.next;
// 유일한 노드를 제거했다면 테일 재설정
if (firstNode === this.tail) {
this.tail = this.dummyHead;
}
return shiftedValue;
}
// 헬퍼: 리스트에 무엇이 있는지 확인
display() {
const items = [];
let current = this.dummyHead.next; // 더미 건너뛰기
while (current !== null) {
items.push(current.value);
current = current.next;
}
return items.join(" → ");
}
}
// 예제: 할 일 목록 관리
const todos = new LinkedList();
// 끝에 작업 추가
todos.push("우유 사기");
todos.push("코드 작성");
todos.push("운동하기");
console.log(todos.display()); // 우유 사기 → 코드 작성 → 운동하기
// 긴급 작업을 앞에 추가
todos.unshift("엄마께 전화");
console.log(todos.display()); // 엄마께 전화 → 우유 사기 → 코드 작성 → 운동하기
// 첫 번째 작업 완료
const completed = todos.shift();
console.log(`완료: ${completed}`); // 완료: 엄마께 전화
console.log(todos.display()); // 우유 사기 → 코드 작성 → 운동하기
// 마지막 작업 제거
const removed = todos.pop();
console.log(`제거됨: ${removed}`); // 제거됨: 운동하기
console.log(todos.display()); // 우유 사기 → 코드 작성이중 더미 노드가 있는 이중 연결 리스트
// 각 노드는 다음과 이전 노드 모두에 대한 포인터를 가짐
class DoublyListNode {
constructor(value) {
this.value = value;
this.next = null; // 앞쪽을 가리킴
this.prev = null; // 뒤쪽을 가리킴
}
}
class DoublyLinkedList {
constructor() {
// 두 개의 더미 노드가 영구적인 "북엔드"로 작동
this.dummyHead = new DoublyListNode("START");
this.dummyTail = new DoublyListNode("END");
// 북엔드를 서로 연결
this.dummyHead.next = this.dummyTail;
this.dummyTail.prev = this.dummyHead;
}
// push: 끝에 추가 (array.push처럼)
push(value) {
const newNode = new DoublyListNode(value);
// 의사 결정 프레임워크: 마지막 실제 노드와 dummyTail 사이에 삽입
const lastNode = this.dummyTail.prev;
// 4개의 연결을 모두 연결
newNode.prev = lastNode; // 새 노드가 마지막을 뒤로 가리킴
newNode.next = this.dummyTail; // 새 노드가 더미 테일을 앞으로 가리킴
lastNode.next = newNode; // 마지막 노드가 새 노드를 앞으로 가리킴
this.dummyTail.prev = newNode; // 더미 테일이 새 노드를 뒤로 가리킴
return this; // 체이닝을 위해
}
// pop: 끝에서 제거 (array.pop처럼)
pop() {
// 의사 결정 프레임워크: 리스트가 비어있는지 확인
if (this.dummyHead.next === this.dummyTail) {
return undefined;
}
const lastNode = this.dummyTail.prev;
const secondToLast = lastNode.prev;
const poppedValue = lastNode.value;
// 마지막 노드 우회
secondToLast.next = this.dummyTail;
this.dummyTail.prev = secondToLast;
return poppedValue;
}
// unshift: 앞에 추가 (array.unshift처럼)
unshift(value) {
const newNode = new DoublyListNode(value);
// 의사 결정 프레임워크: dummyHead와 첫 번째 실제 노드 사이에 삽입
const firstNode = this.dummyHead.next;
// 4개의 연결을 모두 연결
newNode.prev = this.dummyHead; // 새 노드가 더미 헤드를 뒤로 가리킴
newNode.next = firstNode; // 새 노드가 첫 번째를 앞으로 가리킴
this.dummyHead.next = newNode; // 더미 헤드가 새 노드를 앞으로 가리킴
firstNode.prev = newNode; // 첫 번째 노드가 새 노드를 뒤로 가리킴
return this; // 체이닝을 위해
}
// shift: 앞에서 제거 (array.shift처럼)
shift() {
// 의사 결정 프레임워크: 리스트가 비어있는지 확인
if (this.dummyHead.next === this.dummyTail) {
return undefined;
}
const firstNode = this.dummyHead.next;
const secondNode = firstNode.next;
const shiftedValue = firstNode.value;
// 첫 번째 노드 우회
this.dummyHead.next = secondNode;
secondNode.prev = this.dummyHead;
return shiftedValue;
}
// 헬퍼: 리스트에 무엇이 있는지 확인
display() {
const items = [];
let current = this.dummyHead.next;
while (current !== this.dummyTail) {
items.push(current.value);
current = current.next;
}
return items.join(" ⟷ ");
}
// 보너스: 역방향 탐색
displayReverse() {
const items = [];
let current = this.dummyTail.prev;
while (current !== this.dummyHead) {
items.push(current.value);
current = current.prev;
}
return items.join(" ⟷ ");
}
}
// 예제: 다음/이전이 있는 음악 재생 목록
const playlist = new DoublyLinkedList();
// 노래 추가
playlist.push("노래 A");
playlist.push("노래 B");
playlist.push("노래 C");
console.log(playlist.display()); // 노래 A ⟷ 노래 B ⟷ 노래 C
// 시작 부분에 노래 추가
playlist.unshift("인트로 노래");
console.log(playlist.display()); // 인트로 노래 ⟷ 노래 A ⟷ 노래 B ⟷ 노래 C
// 역방향으로 재생
console.log("역방향:", playlist.displayReverse()); // 노래 C ⟷ 노래 B ⟷ 노래 A ⟷ 인트로 노래
// 첫 번째 노래 건너뛰기
const skipped = playlist.shift();
console.log(`건너뜀: ${skipped}`); // 건너뜀: 인트로 노래
// 마지막 노래 제거
const removed = playlist.pop();
console.log(`제거됨: ${removed}`); // 제거됨: 노래 C
console.log(playlist.display()); // 노래 A ⟷ 노래 B의심 해소
흔한 의심: "배열이 더 간단해 보이는데 왜 연결 리스트를 사용하나요? 배열은 인덱스로 어떤 요소든 직접 액세스할 수 있습니다!"
이것은 올바른 데이터 구조를 선택하는 것에 대한 근본적인 질문입니다. 트레이드오프를 살펴보겠습니다.
배열이 항상 더 좋다고 생각하는 이유
다음과 같은 배열의 장점을 고려하세요:
- "배열은 인덱스로 O(1) 무작위 액세스 제공"
- "배열은 더 나은 캐시 지역성을 가짐 (요소가 연속적으로 저장됨)"
- "포인터를 위한 추가 메모리 필요 없음"
- "더 간단한 멘탈 모델 - 그냥 연속 블록"
이런 생각이 중요한 시나리오를 놓치는 이유
핵심 인식: 배열은 삽입과 삭제에 숨겨진 비용이 있습니다!
배열 중간에 삽입할 때 일어나는 일을 추적해봅시다:
배열: [A, B, C, D, E]
인덱스 2에 X 삽입:
단계 1: 모든 것을 오른쪽으로 이동하여 공간 만들기
[A, B, _, C, D, E] // C가 인덱스 3으로 이동
[A, B, _, _, D, E] // D가 인덱스 4로 이동
[A, B, _, _, _, E] // E가 인덱스 5로 이동
단계 2: X 삽입
[A, B, X, C, D, E]
총 작업: 평균 n/2 이동 = O(n)구체적인 예: 성능 비교
앞에 1000개 요소 삽입:
배열 접근법:
- 첫 번째 삽입: 0개 요소 이동
- 두 번째 삽입: 1개 요소 이동
- 세 번째 삽입: 2개 요소 이동
- ...
- 1000번째 삽입: 999개 요소 이동
- 총 이동: 0 + 1 + 2 + ... + 999 = 499,500개 작업!
연결 리스트 접근법:
- 모든 삽입: 2개 포인터 업데이트
- 총 작업: 1000 × 2 = 2,000개 작업
연결 리스트로 250배 적은 작업입니다!
각 구조가 빛나는 때
배열 사용 시기:
- 무작위 액세스 필요 (arr[500]에 직접 액세스)
- 데이터 크기가 비교적 고정
- 주로 데이터를 읽음
- 캐시 성능이 중요
연결 리스트 사용 시기:
- 알려진 위치에서 빈번한 삽입/삭제
- 데이터 크기가 크게 변동
- 순차적으로만 순회
- 메모리가 단편화됨 (연결 리스트는 분산된 메모리 사용 가능)
더미 노드가 천재적인 이유
더미 노드가 없으면 모든 작업이 확인해야 함:
- "이것이 첫 번째 노드인가?" (헤드에 대한 특별 케이스)
- "이것이 마지막 노드인가?" (테일에 대한 특별 케이스)
- "리스트가 비어있나?" (어디서나 null 체크)
더미 노드가 있으면:
- 대상 앞에 항상 노드가 있음 (dummyHead)
- 대상 뒤에 항상 노드가 있음 (이중 연결의 dummyTail)
- 빈 리스트에도 더미 구조가 있음
- 모든 작업이 같은 패턴 사용 - 특별 케이스 없음!
보장: 더미 노드는 엣지 케이스로 가득한 데이터 구조를 균일한 작업을 가진 구조로 변환합니다. 이것은 단순한 편의가 아닙니다 - null 포인터 오류와 특별 케이스 처리의 가능성을 제거하여 버그 없는 코드를 작성하는 것입니다.