이미지 로딩 중...
AI Generated
2025. 11. 6. · 4 Views
이중 연결 리스트로 양방향 탐색 완벽 가이드
이중 연결 리스트의 핵심 개념부터 실무 활용까지, 양방향 탐색이 필요한 모든 상황을 다룹니다. 브라우저 히스토리, 텍스트 에디터의 Undo/Redo, 음악 플레이어 등 실제 애플리케이션에서 어떻게 활용되는지 코드와 함께 배워보세요.
목차
- 이중 연결 리스트 기본 구조 - 노드와 포인터의 이해
- 리스트 끝에 추가하기 - append 메서드 구현
- 리스트 시작에 추가하기 - prepend 메서드 구현
- 양방향 순회하기 - 정방향과 역방향 탐색
- 특정 위치에 삽입하기 - insertAt 메서드 구현
- 특정 노드 삭제하기 - remove 메서드 구현
- 인덱스로 접근하기 - get 메서드 구현
- 실전 활용 - LRU 캐시 구현하기
- 브라우저 히스토리 구현 - 앞으로/뒤로 가기
- 음악 플레이어 플레이리스트 - 순환 이중 연결 리스트
1. 이중 연결 리스트 기본 구조 - 노드와 포인터의 이해
시작하며
여러분이 음악 플레이어를 개발하면서 "이전 곡으로 가기" 기능을 구현할 때 이런 상황을 겪어본 적 있나요? 배열로 구현했더니 현재 곡에서 이전 곡을 찾으려면 인덱스를 관리해야 하고, 곡을 중간에 추가하거나 삭제할 때마다 인덱스가 꼬이는 문제가 발생합니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. 단방향으로만 이동 가능한 자료구조를 사용하면 뒤로 가기 위해 처음부터 다시 순회해야 하거나, 별도의 인덱스 관리 로직이 필요해집니다.
이는 코드를 복잡하게 만들고 성능 저하를 유발합니다. 바로 이럴 때 필요한 것이 이중 연결 리스트입니다.
각 노드가 다음 노드뿐만 아니라 이전 노드도 가리키기 때문에, 양방향으로 자유롭게 이동할 수 있습니다.
개요
간단히 말해서, 이중 연결 리스트는 각 노드가 데이터와 함께 두 개의 포인터(이전 노드, 다음 노드)를 가지는 자료구조입니다. 왜 이 개념이 필요한지 실무 관점에서 설명하자면, 브라우저의 뒤로 가기/앞으로 가기, 텍스트 에디터의 Undo/Redo, 캐시 구현(LRU Cache) 등에서 필수적으로 사용됩니다.
예를 들어, 브라우저에서 현재 페이지에서 바로 이전 페이지로 이동해야 하는 경우, 단방향 리스트라면 처음부터 다시 순회해야 하지만 이중 연결 리스트는 즉시 접근이 가능합니다. 기존 단방향 연결 리스트에서는 next 포인터만 있어서 앞으로만 이동할 수 있었다면, 이중 연결 리스트는 prev 포인터가 추가되어 뒤로도 자유롭게 이동할 수 있습니다.
이 구조의 핵심 특징은 첫째, 양방향 순회가 가능하다는 점입니다. 둘째, 특정 노드를 삭제할 때 이전 노드에 접근하기 위해 처음부터 순회할 필요가 없습니다.
셋째, 역방향 순회가 필요한 알고리즘을 효율적으로 구현할 수 있습니다. 이러한 특징들이 실시간 데이터 처리나 사용자 인터랙션이 많은 애플리케이션에서 중요한 이유는 응답 속도와 사용자 경험에 직접적인 영향을 주기 때문입니다.
코드 예제
// Node 클래스: 데이터와 양방향 포인터를 포함
class Node {
constructor(data) {
this.data = data; // 실제 저장할 데이터
this.prev = null; // 이전 노드를 가리키는 포인터
this.next = null; // 다음 노드를 가리키는 포인터
}
}
// DoublyLinkedList 클래스: 리스트의 시작과 끝을 관리
class DoublyLinkedList {
constructor() {
this.head = null; // 리스트의 첫 번째 노드
this.tail = null; // 리스트의 마지막 노드
this.length = 0; // 리스트의 길이 추적
}
}
설명
이것이 하는 일: 이중 연결 리스트의 기본 뼈대를 구성하는 클래스 두 개를 정의합니다. Node는 개별 데이터 항목을 담는 컨테이너이고, DoublyLinkedList는 이 노드들을 관리하는 관리자 역할을 합니다.
첫 번째로, Node 클래스는 세 가지 속성을 가집니다. data는 실제로 저장하고 싶은 값(숫자, 문자열, 객체 등 무엇이든)을 담고, prev는 이전 노드를 가리키며, next는 다음 노드를 가리킵니다.
생성 시점에는 prev와 next가 모두 null인데, 이는 아직 어떤 노드와도 연결되지 않았다는 의미입니다. 그 다음으로, DoublyLinkedList 클래스가 실행되면서 전체 리스트를 관리하는 구조를 만듭니다.
head는 리스트의 첫 번째 노드를 가리키고, tail은 마지막 노드를 가리킵니다. 빈 리스트에서는 둘 다 null입니다.
length 속성으로 현재 리스트에 몇 개의 노드가 있는지 추적하는데, 이는 배열의 length와 비슷하지만 직접 관리해야 합니다. 마지막으로, 이 구조의 핵심은 prev 포인터입니다.
단방향 리스트와 달리 각 노드가 이전 노드를 알고 있기 때문에, 어떤 노드에서든 양쪽 방향으로 이동할 수 있습니다. 예를 들어 tail에서 시작해서 head까지 역순으로 순회하는 것이 가능합니다.
여러분이 이 코드를 사용하면 데이터를 양방향으로 자유롭게 탐색할 수 있는 기반을 마련할 수 있습니다. 실무에서는 삽입과 삭제가 빈번하면서도 양방향 탐색이 필요한 경우, 노드 삭제 시 이전 노드 참조가 필요한 경우, 역방향 반복이 필요한 경우에 이 구조를 활용하면 됩니다.
실전 팁
💡 length 속성을 꼭 유지하세요. 매번 노드를 세는 것보다 삽입/삭제 시 증감시키는 것이 훨씬 효율적입니다.
💡 head와 tail이 null인지 항상 체크하세요. 빈 리스트에서 연산을 시도하면 null 참조 에러가 발생합니다.
💡 메모리 누수 방지를 위해 노드 삭제 시 prev와 next를 명시적으로 null로 설정하세요. 특히 대용량 데이터를 다룰 때 중요합니다.
💡 디버깅 시에는 toString() 메서드를 추가해서 리스트 전체를 출력할 수 있게 하면 편리합니다.
2. 리스트 끝에 추가하기 - append 메서드 구현
시작하며
여러분이 채팅 애플리케이션을 만들면서 새로운 메시지를 메시지 목록 끝에 추가하는 기능을 구현할 때, 가장 최근 메시지를 빠르게 찾아야 하는 상황을 상상해보세요. 배열을 사용하면 push는 간단하지만, 특정 메시지를 삭제하거나 중간에 삽입할 때 성능 문제가 발생합니다.
이런 문제는 실제로 타임라인이나 피드 기능에서 자주 마주치게 됩니다. 데이터가 계속 추가되면서 동시에 이전 데이터로의 빠른 접근이 필요한 경우, 적절한 자료구조 선택이 중요합니다.
바로 이럴 때 필요한 것이 이중 연결 리스트의 append 메서드입니다. 리스트의 끝에 새 노드를 추가하면서 양방향 연결을 자동으로 유지해줍니다.
개요
간단히 말해서, append 메서드는 새로운 데이터를 리스트의 맨 끝에 추가하는 연산입니다. 시간복잡도는 O(1)로, tail 포인터 덕분에 즉시 접근이 가능합니다.
왜 이 메서드가 필요한지 실무 관점에서 설명하자면, 로그 시스템, 메시지 큐, 작업 대기열 등에서 새로운 항목을 계속 추가하면서도 이전 항목들에 빠르게 접근해야 하는 경우가 많습니다. 예를 들어, 서버 로그를 실시간으로 수집하면서 최근 100개 로그를 양방향으로 탐색해야 하는 경우에 매우 유용합니다.
배열의 push()와 비교하면, 배열은 중간 삭제 시 O(n)의 시간이 걸리지만, 이중 연결 리스트는 O(1)에 가능합니다. 또한 배열은 크기 재조정이 필요할 수 있지만, 연결 리스트는 메모리만 있으면 계속 추가할 수 있습니다.
이 메서드의 핵심 특징은 첫째, 빈 리스트와 비어있지 않은 리스트를 다르게 처리한다는 점입니다. 둘째, 새 노드의 prev를 기존 tail에 연결하고, 기존 tail의 next를 새 노드에 연결하는 양방향 연결을 수행합니다.
셋째, tail 포인터를 새 노드로 업데이트하여 다음 추가 작업을 준비합니다. 이러한 특징들이 중요한 이유는 연결의 무결성을 보장하고, 항상 O(1) 성능을 유지하기 때문입니다.
코드 예제
class DoublyLinkedList {
// ... 이전 코드 ...
// 리스트 끝에 새 노드 추가
append(data) {
const newNode = new Node(data);
// 빈 리스트인 경우: head와 tail 모두 새 노드를 가리킴
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
// 기존 tail의 next를 새 노드로 연결
this.tail.next = newNode;
// 새 노드의 prev를 기존 tail로 연결
newNode.prev = this.tail;
// tail을 새 노드로 업데이트
this.tail = newNode;
}
this.length++;
return this; // 메서드 체이닝을 위해 this 반환
}
}
설명
이것이 하는 일: 새로운 데이터를 리스트의 맨 끝에 추가하면서, 기존 노드들과의 연결 관계를 올바르게 설정합니다. 빈 리스트와 그렇지 않은 경우를 구분하여 처리하는 것이 핵심입니다.
첫 번째로, 새 Node 객체를 생성하고 if 조건으로 리스트가 비어있는지 확인합니다. !this.head가 true라면 리스트가 비어있다는 의미이므로, 첫 번째 노드가 되는 것입니다.
이 경우 head와 tail 모두 새 노드를 가리켜야 합니다. 왜냐하면 노드가 하나뿐이면 그것이 동시에 첫 번째이자 마지막이기 때문입니다.
그 다음으로, 리스트에 이미 노드가 있는 경우(else 블록)에는 세 단계의 연결 작업이 실행됩니다. 먼저 this.tail.next = newNode로 기존 마지막 노드의 next 포인터를 새 노드로 설정합니다.
그 다음 newNode.prev = this.tail로 새 노드가 기존 tail을 가리키게 합니다. 이렇게 양방향 연결이 완성됩니다.
마지막으로 this.tail = newNode로 tail 포인터를 새 노드로 옮깁니다. 세 번째 단계에서는 this.length++로 리스트의 길이를 증가시킵니다.
이는 나중에 size() 메서드를 호출할 때 O(1) 시간에 결과를 반환하기 위함입니다. 최종적으로 return this를 통해 메서드 체이닝(list.append(1).append(2).append(3))을 가능하게 합니다.
여러분이 이 코드를 사용하면 어떤 순서로든 데이터를 추가할 수 있고, 나중에 tail에서 역방향으로 순회하거나 특정 노드를 삭제할 때 효율적으로 작업할 수 있습니다. 실무에서는 실시간 데이터 스트림 처리, 이벤트 로깅, 작업 큐 관리 등에서 이 패턴을 자주 사용하게 됩니다.
실전 팁
💡 return this를 활용해 메서드 체이닝을 구현하면 코드가 간결해집니다. list.append(1).append(2).append(3) 형태로 사용 가능합니다.
💡 빈 리스트 체크를 !this.head 대신 !this.tail로 해도 되지만, 관례적으로 head를 사용하는 것이 더 직관적입니다.
💡 대용량 데이터를 추가할 때는 여러 개를 한 번에 추가하는 appendMany([...]) 메서드를 별도로 만들어 사용하면 편리합니다.
💡 추가 작업 후 리스트의 무결성을 검증하는 validate() 메서드를 개발 환경에서 활용하면 디버깅이 쉬워집니다.
3. 리스트 시작에 추가하기 - prepend 메서드 구현
시작하며
여러분이 실시간 알림 시스템을 개발하면서 가장 최신 알림을 항상 맨 앞에 표시해야 하는 상황을 생각해보세요. 배열의 unshift()를 사용하면 모든 요소를 한 칸씩 뒤로 밀어야 해서 O(n)의 시간이 걸립니다.
알림이 초당 수십 개씩 들어온다면 성능 병목이 발생합니다. 이런 문제는 뉴스 피드, 최근 검색어, 브라우저 히스토리 등 최신 항목을 우선적으로 보여주는 모든 기능에서 발생합니다.
단순히 배열로 구현하면 데이터가 많아질수록 점점 느려집니다. 바로 이럴 때 필요한 것이 이중 연결 리스트의 prepend 메서드입니다.
리스트의 맨 앞에 새 노드를 O(1) 시간에 추가하면서 양방향 연결을 유지합니다.
개요
간단히 말해서, prepend 메서드는 새로운 데이터를 리스트의 맨 앞에 추가하는 연산으로, head 포인터를 활용하여 즉시 삽입이 가능합니다. 왜 이 메서드가 필요한지 실무 관점에서 설명하자면, 스택(Stack) 구현, 최근 항목 우선 표시, Undo 기능 등에서 필수적입니다.
예를 들어, 텍스트 에디터에서 사용자의 각 작업을 히스토리에 기록할 때, 가장 최근 작업을 맨 앞에 추가하면 Undo 시 바로 접근할 수 있습니다. 배열의 unshift()와 비교하면, 배열은 모든 요소를 이동시켜야 하지만(O(n)), 이중 연결 리스트는 포인터만 조정하면 되므로(O(1)) 훨씬 빠릅니다.
특히 데이터가 수천, 수만 개일 때 이 차이는 매우 크게 나타납니다. 이 메서드의 핵심 특징은 첫째, append와 유사하지만 head를 조작한다는 점입니다.
둘째, 기존 head의 prev를 새 노드로 연결해야 한다는 점입니다. 셋째, 빈 리스트의 경우 tail도 함께 설정해야 합니다.
이러한 특징들이 중요한 이유는 양방향 연결의 무결성을 유지하면서도 최고의 성능을 보장하기 때문입니다.
코드 예제
class DoublyLinkedList {
// ... 이전 코드 ...
// 리스트 시작 부분에 새 노드 추가
prepend(data) {
const newNode = new Node(data);
// 빈 리스트인 경우: head와 tail 모두 새 노드를 가리킴
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
// 새 노드의 next를 기존 head로 연결
newNode.next = this.head;
// 기존 head의 prev를 새 노드로 연결
this.head.prev = newNode;
// head를 새 노드로 업데이트
this.head = newNode;
}
this.length++;
return this; // 메서드 체이닝 지원
}
}
설명
이것이 하는 일: 새로운 데이터를 리스트의 맨 앞에 추가하면서, 기존 첫 번째 노드와의 양방향 연결을 설정합니다. append와 거울 관계에 있는 메서드입니다.
첫 번째로, 새 Node를 생성한 후 리스트가 비어있는지 확인합니다. 빈 리스트라면 append와 동일하게 head와 tail 모두 새 노드를 가리키도록 설정합니다.
이 경우 노드가 하나뿐이므로 어느 방향에서 접근하든 같은 노드에 도달합니다. 그 다음으로, 리스트에 노드가 이미 있는 경우에는 세 단계의 포인터 조작이 진행됩니다.
먼저 newNode.next = this.head로 새 노드가 기존 첫 번째 노드를 가리키게 합니다. 그 다음 this.head.prev = newNode로 기존 첫 번째 노드가 역으로 새 노드를 가리키도록 합니다.
이 두 단계로 양방향 연결이 완성됩니다. 세 번째 단계와 최종 결과로, this.head = newNode를 통해 head 포인터를 새 노드로 옮깁니다.
이제 새 노드가 리스트의 공식적인 첫 번째 노드가 됩니다. length를 증가시키고 this를 반환하여 메서드 체이닝을 지원합니다.
여러분이 이 코드를 사용하면 최신 데이터를 우선적으로 처리하는 시스템을 효율적으로 구현할 수 있습니다. 실무에서는 브라우저의 뒤로 가기 히스토리, 최근 검색어 목록, 실시간 알림 시스템, 게임의 액션 리플레이 기능 등에서 이 패턴을 활용합니다.
특히 데이터 양이 많고 삽입이 빈번한 경우 배열 대비 큰 성능 이점을 얻을 수 있습니다.
실전 팁
💡 prepend와 append를 조합하면 Deque(양쪽 끝에서 삽입/삭제 가능한 큐) 자료구조를 쉽게 구현할 수 있습니다.
💡 최근 N개 항목만 유지하는 기능을 만들 때, prepend 후 length가 N을 초과하면 tail을 제거하는 패턴을 사용하세요.
💡 스택을 구현할 때는 prepend로 push, removeFirst로 pop을 구현하면 모두 O(1)에 동작합니다.
💡 성능 테스트 시 배열의 unshift와 비교해보세요. 데이터가 1만 개 이상일 때 차이가 극명하게 드러납니다.
4. 양방향 순회하기 - 정방향과 역방향 탐색
시작하며
여러분이 음악 플레이어의 플레이리스트 기능을 개발하면서 "다음 곡", "이전 곡" 버튼을 구현할 때를 생각해보세요. 배열로 구현하면 인덱스를 계속 추적해야 하고, 플레이리스트가 수정되면 인덱스가 무효화되는 문제가 있습니다.
또한 특정 곡에서 앞뒤로 몇 곡씩 미리보기를 보여주는 기능을 만들기도 번거롭습니다. 이런 문제는 갤러리 뷰어, 문서 네비게이션, 게임의 턴 시스템 등 현재 위치에서 앞뒤로 이동하는 모든 기능에서 발생합니다.
명시적인 인덱스 관리는 코드를 복잡하게 만들고 버그를 유발합니다. 바로 이럴 때 필요한 것이 이중 연결 리스트의 양방향 순회입니다.
각 노드의 next와 prev 포인터를 따라가며 자연스럽게 앞뒤로 이동할 수 있습니다.
개요
간단히 말해서, 양방향 순회는 리스트를 head에서 tail로, 또는 tail에서 head로 탐색하는 것을 의미합니다. 각 노드가 양쪽 이웃을 알고 있어서 어느 방향으로든 이동이 자유롭습니다.
왜 이 개념이 필요한지 실무 관점에서 설명하자면, 데이터의 순서가 중요하면서 역방향 접근도 필요한 경우가 많습니다. 예를 들어, 텍스트 에디터에서 커서 위치를 기준으로 앞뒤 단어를 찾거나, 브라우저에서 현재 페이지 기준으로 방문 기록을 앞뒤로 탐색하는 경우에 필수적입니다.
배열의 정방향 반복(for 루프)과 역방향 반복(역순 for 루프)과 비교하면, 배열은 인덱스가 필요하고 중간 삽입/삭제 시 인덱스가 변경되지만, 이중 연결 리스트는 노드 참조만으로 안전하게 순회할 수 있습니다. 이 순회 방식의 핵심 특징은 첫째, current 변수로 현재 위치를 추적하며 이동한다는 점입니다.
둘째, 정방향은 current.next를, 역방향은 current.prev를 사용합니다. 셋째, 순회 중 노드를 삭제하거나 추가해도 포인터만 올바르게 유지하면 안전합니다.
이러한 특징들이 중요한 이유는 복잡한 데이터 조작 중에도 안정적인 탐색을 보장하기 때문입니다.
코드 예제
class DoublyLinkedList {
// ... 이전 코드 ...
// 정방향 순회: head에서 tail로
traverseForward() {
const values = [];
let current = this.head;
// current가 null이 될 때까지 반복
while (current) {
values.push(current.data); // 현재 노드의 데이터 수집
current = current.next; // 다음 노드로 이동
}
return values;
}
// 역방향 순회: tail에서 head로
traverseBackward() {
const values = [];
let current = this.tail;
// current가 null이 될 때까지 반복
while (current) {
values.push(current.data); // 현재 노드의 데이터 수집
current = current.prev; // 이전 노드로 이동
}
return values;
}
}
설명
이것이 하는 일: 리스트의 모든 노드를 방문하면서 데이터를 수집합니다. 정방향과 역방향 모두 같은 패턴을 사용하지만 시작점과 이동 방향이 다릅니다.
첫 번째로, traverseForward()는 current 변수를 this.head로 초기화합니다. 이것이 순회의 시작점입니다.
while (current) 조건은 current가 null이 아닌 동안 계속 반복한다는 의미입니다. 리스트의 마지막 노드 다음은 null이므로, 자연스럽게 모든 노드를 방문하고 종료됩니다.
그 다음으로, 루프 내부에서는 두 가지 작업이 실행됩니다. values.push(current.data)로 현재 노드의 데이터를 배열에 추가하고, current = current.next로 다음 노드로 이동합니다.
이 순서가 중요한데, 먼저 데이터를 수집한 후에 이동해야 모든 노드를 빠짐없이 처리할 수 있습니다. 세 번째 단계와 최종 결과로, traverseBackward()는 같은 패턴을 역방향으로 수행합니다.
this.tail에서 시작하여 current.prev를 따라 거슬러 올라갑니다. 결과적으로 [마지막 데이터, ..., 첫 번째 데이터] 순서로 배열이 만들어집니다.
여러분이 이 코드를 사용하면 데이터를 양방향으로 자유롭게 탐색할 수 있습니다. 실무에서는 회고록 기능(이전 항목 보기), 슬라이드쇼(앞/뒤 버튼), 페이지네이션(이전/다음 페이지), 브라우저 히스토리 등에 활용됩니다.
특히 사용자가 어느 방향으로든 자유롭게 이동해야 하는 UI에서 필수적인 패턴입니다.
실전 팁
💡 실무에서는 제네레이터 함수(function*)를 사용해 *forward()와 *backward()를 구현하면 더 메모리 효율적입니다.
💡 순회 중 조건을 추가해 특정 데이터만 필터링하는 find(), filter() 메서드로 확장할 수 있습니다.
💡 대용량 리스트를 화면에 표시할 때는 전체를 순회하지 말고, 현재 위치 기준 앞뒤 N개만 가져오는 방식을 사용하세요.
💡 디버깅 시 양방향 순회 결과가 서로 역순인지 검증하면 리스트 무결성을 확인할 수 있습니다.
💡 성능이 중요한 경우 배열을 생성하지 않고 콜백 함수를 받아 각 노드에 대해 실행하는 forEach(callback) 방식을 고려하세요.
5. 특정 위치에 삽입하기 - insertAt 메서드 구현
시작하며
여러분이 작업 관리 앱을 개발하면서 사용자가 드래그 앤 드롭으로 작업 순서를 바꿀 수 있는 기능을 만든다고 생각해보세요. 작업을 특정 위치에 삽입해야 하는데, 배열을 사용하면 splice()가 내부적으로 모든 요소를 이동시켜 O(n)의 비용이 발생합니다.
작업이 수백 개라면 드래그할 때마다 버벅임이 느껴질 수 있습니다. 이런 문제는 플레이리스트 편집, 댓글 스레드 삽입, 레이어 순서 조정 등 사용자가 자유롭게 항목 순서를 변경하는 모든 기능에서 발생합니다.
성능과 사용자 경험이 직결되는 부분입니다. 바로 이럴 때 필요한 것이 이중 연결 리스트의 insertAt 메서드입니다.
특정 인덱스에 새 노드를 삽입하면서 주변 노드들의 포인터만 조정하면 되므로, 실제 데이터 이동이 발생하지 않습니다.
개요
간단히 말해서, insertAt 메서드는 지정된 인덱스 위치에 새 데이터를 삽입하는 연산입니다. 해당 위치까지 순회하는 O(n) 시간이 걸리지만, 실제 삽입은 O(1)에 이루어집니다.
왜 이 메서드가 필요한지 실무 관점에서 설명하자면, 정렬된 리스트 유지, 우선순위 큐 구현, 사용자 정의 순서 관리 등에서 필수적입니다. 예를 들어, 알림 목록에서 긴급 알림을 특정 위치에 삽입하거나, 플레이리스트에서 "다음에 재생" 기능을 구현할 때 유용합니다.
배열의 splice(index, 0, item)과 비교하면, 배열은 삽입 위치 이후의 모든 요소를 이동시켜야 하지만, 이중 연결 리스트는 4개의 포인터만 조정하면 됩니다. 삽입 위치가 중간이고 데이터가 많을수록 이 차이는 커집니다.
이 메서드의 핵심 특징은 첫째, 인덱스 유효성 검사를 먼저 수행한다는 점입니다. 둘째, 인덱스 0이나 마지막 위치는 prepend/append로 위임하여 코드를 단순화합니다.
셋째, 삽입할 위치의 앞 노드를 찾은 후 새 노드를 그 사이에 끼워넣습니다. 이러한 특징들이 중요한 이유는 엣지 케이스를 안전하게 처리하면서도 효율적인 삽입을 보장하기 때문입니다.
코드 예제
class DoublyLinkedList {
// ... 이전 코드 ...
// 특정 인덱스에 새 노드 삽입
insertAt(index, data) {
// 인덱스 유효성 검사
if (index < 0 || index > this.length) {
throw new Error('Index out of bounds');
}
// 맨 앞에 삽입하는 경우
if (index === 0) return this.prepend(data);
// 맨 뒤에 삽입하는 경우
if (index === this.length) return this.append(data);
const newNode = new Node(data);
let current = this.head;
// 삽입 위치 바로 앞 노드까지 이동
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
// 새 노드를 current와 current.next 사이에 삽입
newNode.next = current.next; // 새 노드가 다음 노드를 가리킴
newNode.prev = current; // 새 노드가 이전 노드를 가리킴
current.next.prev = newNode; // 다음 노드가 새 노드를 가리킴
current.next = newNode; // 이전 노드가 새 노드를 가리킴
this.length++;
return this;
}
}
설명
이것이 하는 일: 지정된 인덱스 위치에 새 노드를 삽입하면서, 기존 노드들 사이의 연결을 끊지 않고 새로운 연결을 추가합니다. 엣지 케이스를 먼저 처리하고 일반 케이스를 나중에 다루는 구조입니다.
첫 번째로, 인덱스 유효성 검사를 수행합니다. index < 0이거나 this.length보다 크면 에러를 던집니다.
왜 this.length와 같은 것은 허용하냐면, 맨 끝에 추가하는 것은 유효한 연산이기 때문입니다. index === 0이면 prepend()를, index === this.length면 append()를 호출하여 조기 반환합니다.
이렇게 하면 특수 케이스를 간단히 처리할 수 있습니다. 그 다음으로, 일반적인 중간 삽입의 경우 for 루프로 삽입 위치 바로 앞 노드까지 이동합니다.
index가 3이라면 0, 1, 2번째 노드를 지나 2번째 노드(index - 1)에서 멈춥니다. 이 노드를 current라고 하면, 새 노드는 current와 current.next 사이에 들어가야 합니다.
세 번째 단계에서는 4개의 포인터 조정이 순서대로 진행됩니다. 첫째, newNode.next = current.next로 새 노드가 다음 노드를 가리킵니다.
둘째, newNode.prev = current로 새 노드가 이전 노드를 가리킵니다. 셋째, current.next.prev = newNode로 원래 다음 노드가 새 노드를 가리킵니다.
넷째, current.next = newNode로 이전 노드가 새 노드를 가리킵니다. 이 순서가 중요한데, current.next를 먼저 바꾸면 원래 다음 노드에 접근할 수 없게 되기 때문입니다.
여러분이 이 코드를 사용하면 사용자가 자유롭게 항목 순서를 조정할 수 있는 유연한 UI를 만들 수 있습니다. 실무에서는 칸반 보드의 카드 재배치, 플레이리스트 편집, 문서의 섹션 순서 변경, 쇼핑 카트 항목 우선순위 조정 등에 활용됩니다.
배열 기반 구현 대비 삽입 성능이 우수하여 대용량 데이터에서 특히 빛을 발합니다.
실전 팁
💡 포인터 조정 순서가 매우 중요합니다. 잘못하면 노드가 손실되거나 순환 참조가 발생할 수 있으니, 항상 원래 연결을 참조한 후에 새 연결을 만드세요.
💡 중간 지점에 자주 삽입하는 경우, 인덱스가 length/2보다 크면 tail에서 역방향으로 순회하면 성능을 개선할 수 있습니다.
💡 여러 개를 연속으로 삽입할 때는 정렬 상태를 유지하는 insertSorted() 메서드를 별도로 구현하는 것을 고려하세요.
💡 삽입 후 리스트의 무결성을 검증하려면, 삽입된 노드의 prev.next === 삽입 노드 && next.prev === 삽입 노드인지 확인하세요.
💡 프로덕션 코드에서는 try-catch로 에러를 처리하고, 의미 있는 에러 메시지를 제공하세요.
6. 특정 노드 삭제하기 - remove 메서드 구현
시작하며
여러분이 SNS 피드에서 사용자가 게시물을 삭제하는 기능을 구현한다고 생각해보세요. 배열로 피드를 관리하면 삭제할 게시물을 찾은 후 splice()로 제거하는데, 이때 이후의 모든 항목이 한 칸씩 앞으로 이동합니다.
게시물이 수천 개라면 이 작업이 눈에 띄게 느려질 수 있습니다. 이런 문제는 채팅 메시지 삭제, 장바구니 항목 제거, 작업 목록에서 완료된 작업 제거 등 동적으로 항목을 삭제하는 모든 기능에서 발생합니다.
특히 실시간으로 업데이트되는 목록에서는 성능이 사용자 경험에 직접 영향을 줍니다. 바로 이럴 때 필요한 것이 이중 연결 리스트의 remove 메서드입니다.
삭제할 노드의 앞뒤 포인터만 조정하면 되므로, 다른 노드들은 전혀 영향을 받지 않습니다.
개요
간단히 말해서, remove 메서드는 특정 데이터를 가진 첫 번째 노드를 찾아서 리스트에서 제거하는 연산입니다. 노드를 찾는 데 O(n), 삭제 자체는 O(1)의 시간이 걸립니다.
왜 이 메서드가 필요한지 실무 관점에서 설명하자면, 사용자 액션에 따른 항목 제거, 캐시 무효화, 중복 제거, 필터링 등에서 필수적입니다. 예를 들어, LRU 캐시에서 가장 오래된 항목을 제거하거나, 실시간 알림 목록에서 읽은 알림을 지우는 경우에 사용됩니다.
배열의 filter() 또는 splice()와 비교하면, 배열은 삭제 후 요소 이동이 필요하지만(O(n)), 이중 연결 리스트는 포인터만 조정하면 됩니다(O(1)). 또한 이중 연결 리스트는 노드 자체에 대한 참조가 있으면 즉시 삭제할 수 있지만, 배열은 인덱스를 찾아야 합니다.
이 메서드의 핵심 특징은 첫째, head나 tail을 삭제하는 경우를 별도로 처리한다는 점입니다. 둘째, 삭제할 노드의 prev.next와 next.prev를 조정하여 노드를 우회합니다.
셋째, 삭제된 노드의 포인터를 null로 설정하여 메모리 누수를 방지합니다. 이러한 특징들이 중요한 이유는 리스트의 무결성을 유지하면서도 메모리를 효율적으로 관리하기 때문입니다.
코드 예제
class DoublyLinkedList {
// ... 이전 코드 ...
// 특정 값을 가진 첫 번째 노드 삭제
remove(data) {
if (!this.head) return null; // 빈 리스트
let current = this.head;
// 삭제할 노드를 찾을 때까지 순회
while (current) {
if (current.data === data) {
// head를 삭제하는 경우
if (current === this.head) {
this.head = current.next;
if (this.head) this.head.prev = null;
else this.tail = null; // 노드가 하나뿐이었던 경우
}
// tail을 삭제하는 경우
else if (current === this.tail) {
this.tail = current.prev;
this.tail.next = null;
}
// 중간 노드를 삭제하는 경우
else {
current.prev.next = current.next;
current.next.prev = current.prev;
}
this.length--;
// 메모리 누수 방지: 삭제된 노드의 포인터 제거
current.prev = null;
current.next = null;
return current.data;
}
current = current.next;
}
return null; // 찾지 못한 경우
}
}
설명
이것이 하는 일: 주어진 데이터와 일치하는 첫 번째 노드를 찾아서 리스트에서 제거합니다. 삭제 위치에 따라 처리 방법이 달라지므로 세 가지 케이스로 나누어 처리합니다.
첫 번째로, 빈 리스트 체크 후 while 루프로 순회하며 current.data === data인 노드를 찾습니다. 찾으면 삭제 로직을 실행하는데, 여기서 중요한 것은 삭제할 노드가 head인지, tail인지, 중간인지에 따라 처리가 다르다는 점입니다.
그 다음으로, head를 삭제하는 경우를 봅시다. this.head = current.next로 head를 다음 노드로 이동시킵니다.
새로운 head가 존재하면 그것의 prev를 null로 설정합니다. 만약 새로운 head가 null이라면(노드가 하나뿐이었다면) tail도 null로 설정합니다.
세 번째로, tail을 삭제하는 경우는 반대입니다. this.tail = current.prev로 tail을 이전 노드로 이동시키고, 그것의 next를 null로 설정합니다.
중간 노드를 삭제하는 경우는 가장 간단합니다. current.prev.next = current.next로 이전 노드가 다음 노드를 가리키게 하고, current.next.prev = current.prev로 다음 노드가 이전 노드를 가리키게 합니다.
이렇게 하면 current 노드가 우회됩니다. 마지막으로, length를 감소시키고 current.prev = current.next = null로 삭제된 노드의 포인터를 정리합니다.
이는 가비지 컬렉션을 돕고 메모리 누수를 방지합니다. 삭제된 데이터를 반환하여 호출자가 확인할 수 있게 합니다.
여러분이 이 코드를 사용하면 동적인 데이터 관리가 필요한 애플리케이션을 효율적으로 구현할 수 있습니다. 실무에서는 채팅 메시지 삭제, 알림 제거, 장바구니 항목 삭제, 작업 완료 표시, 캐시 엔트리 무효화 등에 활용됩니다.
특히 삭제가 빈번하게 일어나는 시스템에서 배열보다 훨씬 나은 성능을 제공합니다.
실전 팁
💡 삭제된 노드의 포인터를 null로 설정하는 것을 잊지 마세요. 특히 대용량 객체를 저장하는 경우 메모리 누수의 원인이 됩니다.
💡 특정 조건을 만족하는 모든 노드를 삭제하려면 removeAll(predicate) 메서드를 별도로 구현하세요.
💡 노드 자체에 대한 참조가 있다면 removeNode(node) 메서드를 만들어 O(1)에 삭제할 수 있습니다.
💡 삭제 작업이 실패했을 때(노드를 찾지 못함) 어떻게 처리할지 명확히 정의하세요. null 반환, 예외 발생, 또는 boolean 반환 등의 옵션이 있습니다.
💡 실무에서는 soft delete(삭제 플래그 설정) 패턴도 고려하세요. 나중에 복구가 필요한 경우에 유용합니다.
7. 인덱스로 접근하기 - get 메서드 구현
시작하며
여러분이 페이지네이션 기능을 개발하면서 "3페이지로 이동" 같은 직접 접근 기능을 구현할 때를 생각해보세요. 배열이라면 arr[index]로 즉시 접근할 수 있지만, 연결 리스트는 순차 접근만 가능합니다.
하지만 양방향이라는 특성을 활용하면 최적화할 수 있습니다. 이런 상황은 특정 순번의 항목에 접근해야 하는 모든 경우에 발생합니다.
연결 리스트의 약점이지만, 이중 연결 리스트는 최적화 여지가 있습니다. 바로 이럴 때 필요한 것이 최적화된 get 메서드입니다.
인덱스가 앞쪽에 가까우면 head에서, 뒤쪽에 가까우면 tail에서 시작하여 순회 거리를 절반으로 줄입니다.
개요
간단히 말해서, get 메서드는 지정된 인덱스의 노드에 접근하는 연산으로, 양방향 특성을 활용하여 최적화됩니다. 평균 O(n/2)의 시간복잡도를 가집니다.
왜 이 최적화가 필요한지 실무 관점에서 설명하자면, 리스트의 뒷부분에 자주 접근하는 경우(예: 최근 항목 조회) 성능 차이가 크게 납니다. 예를 들어, 1000개 항목 중 900번째에 접근할 때, 단방향이면 900번 순회하지만 양방향은 100번만 순회하면 됩니다.
배열의 arr[index]와 비교하면, 배열은 O(1)이지만 중간 삽입/삭제가 O(n)입니다. 이중 연결 리스트는 접근이 O(n/2)이지만 삽입/삭제가 O(1)입니다.
용도에 맞게 선택해야 합니다. 이 메서드의 핵심 특징은 첫째, 인덱스를 length/2와 비교하여 순회 방향을 결정한다는 점입니다.
둘째, 정방향과 역방향 순회 로직을 모두 포함합니다. 셋째, 유효하지 않은 인덱스를 체크하여 안전성을 보장합니다.
이러한 특징들이 중요한 이유는 성능을 최적화하면서도 안정성을 유지하기 때문입니다.
코드 예제
class DoublyLinkedList {
// ... 이전 코드 ...
// 인덱스로 노드에 접근 (양방향 최적화)
get(index) {
// 인덱스 유효성 검사
if (index < 0 || index >= this.length) {
return null;
}
let current;
// 인덱스가 앞쪽 절반에 있는 경우: head에서 정방향 순회
if (index < this.length / 2) {
current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
}
// 인덱스가 뒤쪽 절반에 있는 경우: tail에서 역방향 순회
else {
current = this.tail;
for (let i = this.length - 1; i > index; i--) {
current = current.prev;
}
}
return current;
}
// 인덱스의 데이터만 반환하는 헬퍼 메서드
getAt(index) {
const node = this.get(index);
return node ? node.data : null;
}
}
설명
이것이 하는 일: 주어진 인덱스의 노드를 찾되, 인덱스 위치에 따라 더 가까운 쪽(head 또는 tail)에서 시작하여 순회 거리를 최소화합니다. 이는 단방향 리스트에서는 불가능한 최적화입니다.
첫 번째로, 인덱스 유효성을 검사합니다. 0보다 작거나 length 이상이면 null을 반환합니다.
이는 배열의 undefined 반환과 비슷한 동작입니다. 그 다음 핵심 최적화 로직이 시작됩니다.
그 다음으로, if (index < this.length / 2) 조건으로 인덱스가 리스트의 앞쪽 절반에 있는지 판단합니다. 예를 들어 길이가 100이고 인덱스가 30이라면 앞쪽 절반이므로, head에서 시작해서 30번 이동합니다.
current = current.next를 반복하며 정방향으로 순회합니다. 세 번째로, 인덱스가 뒤쪽 절반에 있는 경우(else 블록)를 봅시다.
길이가 100이고 인덱스가 80이라면, tail에서 시작해서 역방향으로 19번만 이동하면 됩니다. for (let i = this.length - 1; i > index; i--)로 역순 카운트하며 current = current.prev로 이전 노드로 이동합니다.
이렇게 하면 80번 대신 20번만 순회하면 됩니다. 마지막으로, 찾은 노드를 반환하거나, getAt() 헬퍼 메서드를 통해 노드 대신 데이터만 반환할 수도 있습니다.
getAt()는 배열처럼 사용하고 싶을 때 편리합니다. 여러분이 이 코드를 사용하면 연결 리스트의 랜덤 액세스 성능을 최대 50%까지 개선할 수 있습니다.
실무에서는 페이지네이션, 슬라이더 컴포넌트, 게임 리플레이 시스템, 대용량 로그 뷰어 등에서 특정 위치로의 빠른 점프가 필요할 때 활용합니다. 배열만큼 빠르지는 않지만, 삽입/삭제가 빈번한 상황에서는 전체적으로 더 나은 성능을 제공합니다.
실전 팁
💡 set(index, data) 메서드도 같은 방식으로 최적화할 수 있습니다. get()으로 노드를 찾은 후 data만 변경하세요.
💡 자주 접근하는 인덱스를 캐싱하는 전략도 고려해보세요. 예를 들어 마지막으로 접근한 인덱스와 노드를 저장해두면 연속된 접근 시 유리합니다.
💡 실무에서 인덱스 접근이 매우 빈번하다면 연결 리스트보다 배열이나 해시맵을 사용하는 것이 나을 수 있습니다. 자료구조 선택은 사용 패턴에 따라 달라집니다.
💡 디버깅 시 get(0)은 head, get(length-1)은 tail과 같은지 확인하여 리스트 무결성을 검증할 수 있습니다.
💡 TypeScript를 사용한다면 null 대신 undefined를 반환하거나, Option 타입을 사용하는 것을 고려하세요.
8. 실전 활용 - LRU 캐시 구현하기
시작하며
여러분이 이미지 뷰어 앱을 개발하면서 최근 본 이미지를 캐싱하는 기능을 만든다고 생각해보세요. 메모리는 한정되어 있으니 최대 100개만 유지하고, 새 이미지를 볼 때마다 가장 오래 전에 본 이미지를 제거해야 합니다.
또한 이미 캐시된 이미지를 다시 보면 그것을 "최근"으로 옮겨야 합니다. 이런 LRU(Least Recently Used) 캐시 패턴은 실제로 브라우저 캐시, 데이터베이스 쿼리 캐시, API 응답 캐시 등 거의 모든 시스템에서 사용됩니다.
배열로 구현하면 "최근" 위치로 이동시킬 때마다 요소들을 재배치해야 해서 비효율적입니다. 바로 이럴 때 필요한 것이 이중 연결 리스트와 해시맵의 조합입니다.
해시맵으로 O(1) 접근을, 이중 연결 리스트로 O(1) 삽입/삭제를 달성할 수 있습니다.
개요
간단히 말해서, LRU 캐시는 용량이 제한된 캐시로, 용량 초과 시 가장 오래 전에 사용된 항목을 자동으로 제거합니다. 이중 연결 리스트로 사용 순서를, 해시맵으로 빠른 조회를 구현합니다.
왜 이 패턴이 필요한지 실무 관점에서 설명하자면, 메모리가 제한된 환경에서 자주 사용되는 데이터만 유지하여 성능을 최적화하는 핵심 기법입니다. 예를 들어, Redis, Memcached 같은 캐시 시스템, 운영체제의 페이지 교체 알고리즘, CDN의 콘텐츠 캐싱 등에서 널리 사용됩니다.
단순 배열이나 객체로 구현하면 용량 관리와 순서 유지가 어렵지만, 이중 연결 리스트는 tail(가장 오래된)과 head(가장 최근) 관리가 명확하고, 중간 노드를 head로 이동시키는 것도 O(1)에 가능합니다. 이 구현의 핵심 특징은 첫째, Map으로 key-node 매핑을 유지하여 O(1) 조회를 달성합니다.
둘째, 리스트의 head가 가장 최근 사용, tail이 가장 오래된 항목입니다. 셋째, 캐시 히트 시 해당 노드를 제거하고 head에 다시 추가하여 "최근 사용"으로 표시합니다.
이러한 특징들이 중요한 이유는 모든 연산이 O(1)에 동작하여 대규모 시스템에서도 일정한 성능을 보장하기 때문입니다.
코드 예제
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map(); // key -> node 매핑
this.list = new DoublyLinkedList();
}
// 캐시에서 값 가져오기
get(key) {
if (!this.cache.has(key)) return null;
const node = this.cache.get(key);
// 노드를 제거하고 맨 앞으로 이동 (최근 사용 표시)
this.list.removeNode(node);
this.list.prepend(node.data);
// Map의 참조도 업데이트
this.cache.set(key, this.list.head);
return node.data.value;
}
// 캐시에 값 추가
put(key, value) {
// 이미 존재하면 제거
if (this.cache.has(key)) {
const node = this.cache.get(key);
this.list.removeNode(node);
}
// 새 항목을 맨 앞에 추가
this.list.prepend({ key, value });
this.cache.set(key, this.list.head);
// 용량 초과 시 가장 오래된 항목(tail) 제거
if (this.cache.size > this.capacity) {
const removed = this.list.tail;
this.list.remove(removed.data);
this.cache.delete(removed.data.key);
}
}
}
설명
이것이 하는 일: 제한된 용량의 캐시를 구현하여, 자주 사용되는 데이터는 유지하고 오래된 데이터는 자동으로 제거합니다. 모든 연산이 O(1)에 동작하도록 Map과 이중 연결 리스트를 조합합니다.
첫 번째로, 생성자에서 capacity(최대 용량), cache(Map 객체), list(DoublyLinkedList 인스턴스)를 초기화합니다. cache는 key에서 리스트의 노드로의 빠른 매핑을 제공하고, list는 사용 순서를 유지합니다.
그 다음으로, get(key) 메서드를 봅시다. 먼저 this.cache.has(key)로 존재 여부를 확인합니다.
없으면 null 반환(캐시 미스). 있으면 해당 노드를 가져와서 리스트에서 제거한 후 prepend()로 맨 앞에 다시 추가합니다.
이렇게 하면 "방금 사용됨"으로 표시됩니다. cache Map의 참조도 새 head로 업데이트합니다.
세 번째로, put(key, value) 메서드는 더 복잡합니다. 만약 key가 이미 존재하면 기존 노드를 제거합니다.
그 다음 { key, value } 객체를 데이터로 가진 새 노드를 맨 앞에 추가하고, cache에 key-node 매핑을 저장합니다. 이 시점에서 cache.size가 capacity를 초과하면, tail(가장 오래된 항목)을 리스트와 Map 양쪽에서 제거합니다.
마지막으로, 이 구조의 핵심은 Map이 O(1) 조회를 제공하고, 이중 연결 리스트가 O(1) 삽입/삭제와 순서 유지를 제공한다는 점입니다. 단일 자료구조로는 불가능한 성능을 두 개를 조합하여 달성합니다.
여러분이 이 코드를 사용하면 API 응답 캐싱, 이미지/비디오 프리로딩, 데이터베이스 쿼리 결과 캐싱, 계산 결과 메모이제이션 등 다양한 최적화 시나리오에 적용할 수 있습니다. 실무에서는 Redis와 같은 전문 솔루션을 사용하지만, 클라이언트 측 캐싱이나 임베디드 환경에서는 직접 구현하는 것이 유용합니다.
메모리 제한이 있는 모든 상황에서 효과적인 패턴입니다.
실전 팁
💡 removeNode(node) 메서드는 노드 참조로 직접 삭제하므로 O(1)입니다. DoublyLinkedList 클래스에 추가 구현이 필요합니다.
💡 실전에서는 TTL(Time To Live)도 함께 구현하여 오래된 항목을 시간 기반으로도 무효화하세요.
💡 캐시 히트율을 추적하는 통계 기능을 추가하면 캐시 크기 조정에 도움이 됩니다.
💡 async 환경에서는 동시성 제어를 추가해야 합니다. 같은 key에 대한 동시 put을 방지하세요.
💡 WeakMap을 사용하면 자동 가비지 컬렉션이 가능하지만, size 제한이 어려우므로 용도에 맞게 선택하세요.
9. 브라우저 히스토리 구현 - 앞으로/뒤로 가기
시작하며
여러분이 웹 브라우저의 뒤로 가기/앞으로 가기 기능을 구현한다고 상상해보세요. 사용자가 페이지를 방문할 때마다 히스토리에 추가하고, 뒤로 가기를 누르면 이전 페이지로, 앞으로 가기를 누르면 다음 페이지로 이동해야 합니다.
새 페이지를 방문하면 현재 위치 이후의 "앞으로 가기" 히스토리는 모두 삭제됩니다. 이런 패턴은 실제로 브라우저뿐만 아니라 텍스트 에디터의 Undo/Redo, 이미지 뷰어의 이전/다음, PDF 리더의 페이지 네비게이션 등에서 널리 사용됩니다.
배열로 구현할 수도 있지만, 현재 위치 이후를 삭제하거나 빈번한 탐색 시 이중 연결 리스트가 더 자연스럽습니다. 바로 이럴 때 필요한 것이 이중 연결 리스트 기반 히스토리 관리입니다.
current 포인터로 현재 위치를 추적하고, prev/next로 자유롭게 이동할 수 있습니다.
개요
간단히 말해서, 브라우저 히스토리는 current 포인터를 유지하는 이중 연결 리스트로, 방문한 페이지를 순서대로 저장하고 앞뒤로 이동할 수 있게 합니다. 왜 이 패턴이 필요한지 실무 관점에서 설명하자면, 사용자 네비게이션 기록 관리는 UX의 핵심입니다.
예를 들어, SPA(Single Page Application)에서 브라우저 API 없이 자체 히스토리를 구현하거나, 커스텀 네비게이션 스택을 만들 때 필수적입니다. 배열로 구현하면 currentIndex를 유지하고 배열을 자르는(splice) 방식이지만, 이중 연결 리스트는 노드 삭제가 더 효율적이고, 특히 메모리 관리 측면에서 유리합니다.
또한 히스토리가 매우 길어질 때 성능이 더 안정적입니다. 이 구현의 핵심 특징은 첫째, current 포인터가 현재 페이지를 가리킨다는 점입니다.
둘째, 새 페이지 방문 시 current 이후의 모든 노드를 제거합니다. 셋째, back()과 forward()는 단순히 current 포인터를 이동시키기만 합니다.
이러한 특징들이 중요한 이유는 직관적이고 효율적인 히스토리 관리를 가능하게 하기 때문입니다.
코드 예제
class BrowserHistory {
constructor(homepage) {
this.current = new Node(homepage); // 현재 페이지
this.current.prev = null;
this.current.next = null;
}
// 새 페이지 방문: 현재 위치 이후는 모두 삭제
visit(url) {
const newNode = new Node(url);
// 현재 위치 다음에 연결
newNode.prev = this.current;
this.current.next = newNode;
// current를 새 페이지로 이동
this.current = newNode;
// 새 페이지 이후는 null (앞으로 가기 히스토리 삭제)
this.current.next = null;
}
// 뒤로 가기: current를 이전 노드로 이동
back(steps = 1) {
while (steps > 0 && this.current.prev) {
this.current = this.current.prev;
steps--;
}
return this.current.data;
}
// 앞으로 가기: current를 다음 노드로 이동
forward(steps = 1) {
while (steps > 0 && this.current.next) {
this.current = this.current.next;
steps--;
}
return this.current.data;
}
// 현재 페이지 반환
getCurrentPage() {
return this.current.data;
}
}
설명
이것이 하는 일: 웹 브라우저의 페이지 히스토리를 관리합니다. 방문한 페이지들을 연결 리스트로 저장하고, current 포인터로 현재 위치를 추적하여 자유롭게 앞뒤로 이동할 수 있게 합니다.
첫 번째로, 생성자에서 homepage를 담은 노드를 만들고 this.current로 설정합니다. 처음에는 이전 페이지도 다음 페이지도 없으므로 prev와 next 모두 null입니다.
이것이 히스토리의 시작점입니다. 그 다음으로, visit(url) 메서드를 봅시다.
새 노드를 생성하고 현재 위치(this.current) 다음에 연결합니다. newNode.prev = this.current로 역방향 링크를 만들고, this.current.next = newNode로 정방향 링크를 만듭니다.
그 다음 this.current = newNode로 포인터를 새 페이지로 옮깁니다. 마지막으로 this.current.next = null을 설정하는데, 이게 핵심입니다.
만약 사용자가 뒤로 가기를 여러 번 한 후 새 페이지를 방문하면, 기존의 "앞으로 가기" 히스토리가 모두 사라져야 하기 때문입니다. 세 번째로, back(steps)과 forward(steps)는 매우 간단합니다.
while 루프로 steps만큼 반복하면서, back은 current = current.prev로, forward는 current = current.next로 이동합니다. 더 이상 갈 곳이 없으면(null이면) 멈춥니다.
최종적으로 현재 페이지의 데이터를 반환합니다. 마지막으로, getCurrentPage()는 단순히 this.current.data를 반환하여 현재 어떤 페이지에 있는지 알려줍니다.
이 메서드는 UI 업데이트 시 자주 호출됩니다. 여러분이 이 코드를 사용하면 SPA 라우팅, 커스텀 네비게이션 스택, 멀티 탭 히스토리 관리, 게임의 액션 리플레이 등을 구현할 수 있습니다.
실무에서는 History API를 사용하지만, 모바일 앱이나 데스크톱 앱, 또는 복잡한 네비게이션 로직이 필요한 경우 직접 구현하는 것이 더 나을 수 있습니다. 특히 히스토리를 로컬 스토리지에 저장하거나, 특정 조건에서 히스토리를 건너뛰는 등의 커스터마이징이 필요할 때 유용합니다.
실전 팁
💡 canGoBack()과 canGoForward() 메서드를 추가해서 UI 버튼을 활성화/비활성화하세요. return !!this.current.prev 형태로 구현합니다.
💡 최대 히스토리 길이를 제한하려면, visit 시 tail에서부터 오래된 항목을 제거하는 로직을 추가하세요.
💡 히스토리를 배열로 변환하는 toArray() 메서드를 만들면 UI에 전체 히스토리를 표시하기 좋습니다.
💡 state 객체를 함께 저장하면 페이지별 스크롤 위치, 폼 데이터 등을 복원할 수 있습니다. { url, state } 형태로 저장하세요.
💡 실제 브라우저는 세션 스토리지에 히스토리를 저장합니다. JSON.stringify로 직렬화하여 저장/복원 기능을 추가하면 새로고침 후에도 유지됩니다.
10. 음악 플레이어 플레이리스트 - 순환 이중 연결 리스트
시작하며
여러분이 음악 플레이어를 개발하면서 "반복 재생" 기능을 구현한다고 생각해보세요. 마지막 곡 다음에 "다음 곡" 버튼을 누르면 첫 번째 곡으로 돌아가고, 첫 번째 곡에서 "이전 곡"을 누르면 마지막 곡으로 가야 합니다.
일반 리스트로는 tail.next가 null이므로 별도 로직이 필요합니다. 이런 순환 구조는 슬라이드쇼, 캐러셀 UI, 게임의 턴 시스템, 타이머의 시간 표시 등에서 자주 등장합니다.
끝에 도달하면 처음으로 돌아가는 무한 루프가 필요한 모든 상황입니다. 바로 이럴 때 필요한 것이 순환 이중 연결 리스트(Circular Doubly Linked List)입니다.
tail의 next를 head로, head의 prev를 tail로 연결하여 끝없이 순회할 수 있습니다.
개요
간단히 말해서, 순환 이중 연결 리스트는 tail.next가 head를 가리키고 head.prev가 tail을 가리키는 구조로, 어느 방향으로든 무한히 순회할 수 있습니다. 왜 이 구조가 필요한지 실무 관점에서 설명하자면, 순환 동작이 자연스러운 데이터에 적합합니다.
예를 들어, 음악 플레이어의 반복 재생, 이미지 갤러리의 무한 스크롤, 게임의 플레이어 턴 순환, 라운드 로빈 스케줄링 등에서 사용됩니다. 일반 이중 연결 리스트와 비교하면, 일반 리스트는 끝 체크(null 검사)가 필요하지만, 순환 리스트는 끝이 없으므로 경계 조건 처리가 단순해집니다.
대신 무한 루프에 주의해야 합니다. 이 구조의 핵심 특징은 첫째, 모든 노드가 항상 prev와 next를 가진다는 점(null이 없음)입니다.
둘째, 삽입/삭제 시 순환 연결을 유지해야 합니다. 셋째, 순회 시 시작점을 기억해야 무한 루프를 방지할 수 있습니다.
이러한 특징들이 중요한 이유는 끝없는 탐색이 가능하면서도 구조적 무결성을 유지하기 때문입니다.
코드 예제
class CircularPlaylist {
constructor() {
this.current = null; // 현재 재생 중인 곡
this.size = 0;
}
// 곡 추가
addSong(title) {
const newNode = new Node(title);
if (!this.current) {
// 첫 번째 노드: 자기 자신을 가리킴
newNode.next = newNode;
newNode.prev = newNode;
this.current = newNode;
} else {
// 마지막 위치에 삽입
const tail = this.current.prev; // 현재 tail
newNode.next = this.current; // 새 노드 -> head
newNode.prev = tail; // 새 노드 <- tail
tail.next = newNode; // tail -> 새 노드
this.current.prev = newNode; // head <- 새 노드
}
this.size++;
}
// 다음 곡으로 이동
next() {
if (!this.current) return null;
this.current = this.current.next;
return this.current.data;
}
// 이전 곡으로 이동
previous() {
if (!this.current) return null;
this.current = this.current.prev;
return this.current.data;
}
// 현재 곡 반환
getCurrentSong() {
return this.current ? this.current.data : null;
}
}
설명
이것이 하는 일: 음악 플레이리스트를 순환 구조로 관리하여, 마지막 곡 다음은 첫 곡, 첫 곡 이전은 마지막 곡이 되도록 합니다. 끝 없이 계속 재생할 수 있는 구조입니다.
첫 번째로, addSong()에서 첫 번째 노드를 추가하는 경우를 봅시다. 노드가 하나뿐이므로 자기 자신을 가리켜야 합니다.
newNode.next = newNode, newNode.prev = newNode로 설정합니다. 이렇게 하면 next()나 previous()를 몇 번 호출하든 항상 같은 노드를 가리킵니다.
그 다음으로, 두 번째 이후 노드를 추가하는 경우입니다. 핵심은 현재 tail을 찾는 것인데, 순환 구조에서는 this.current.prev가 항상 tail입니다.
새 노드를 tail 다음, head 이전에 삽입해야 하므로 네 개의 포인터를 조정합니다. newNode.next = this.current로 새 노드가 head를 가리키고, newNode.prev = tail로 새 노드가 tail을 가리킵니다.
그 다음 tail.next = newNode와 this.current.prev = newNode로 양방향 연결을 완성합니다. 이제 새 노드가 새로운 tail이 됩니다.
세 번째로, next()와 previous()는 매우 간단합니다. this.current = this.current.next 또는 this.current = this.current.prev로 포인터를 이동하기만 하면 됩니다.
null 체크가 필요 없습니다. 마지막 곡에서 next()를 호출하면 자동으로 첫 곡으로 돌아갑니다.
마지막으로, 이 구조의 장점은 경계 조건을 신경 쓰지 않아도 된다는 점입니다. 일반 리스트에서는 "다음 곡이 있는가?"를 체크해야 하지만, 순환 리스트는 항상 다음 곡이 있습니다.
여러분이 이 코드를 사용하면 음악 플레이어, 이미지 슬라이더, 광고 로테이션, 게임 턴 시스템 등 순환 동작이 필요한 모든 기능을 자연스럽게 구현할 수 있습니다. 실무에서는 "반복 재생" 모드를 켜고 끌 수 있도록 플래그를 추가하거나, 셔플 재생을 위한 랜덤 순회 로직을 결합하기도 합니다.
사용자가 끝없이 탐색할 수 있는 직관적인 UX를 제공합니다.
실전 팁
💡 전체 플레이리스트를 출력하려면 시작 노드를 기억하고 다시 돌아올 때까지만 순회하세요. 무한 루프를 방지할 수 있습니다.
💡 shuffle() 기능을 추가하려면 Fisher-Yates 알고리즘으로 배열을 섞은 후 리스트를 재구성하세요.
💡 removeSong()을 구현할 때 노드가 하나만 남으면 순환 연결을 끊고 일반 단일 노드로 만드세요.
💡 플레이리스트가 매우 길 때는 Map으로 곡 ID -> 노드 매핑을 유지하여 특정 곡으로 바로 점프할 수 있게 하세요.
💡 "현재부터 N곡 미리보기" 기능은 current부터 next를 N번 따라가며 데이터를 수집하면 됩니다.