이중 연결리스트 (Doubly Linked List)

이중 연결리스트의 간략한 구조 (Colt Steele 강의자료 캡처)

 

 

 

이중 연결리스트(Doubly Linked List)

이중 연결리스트는 각 노드가 데이터와 함께 이전 노드와 다음 노드를 모두 가리키는 포인터를 가진 선형 데이터 구조이다. 각 노드는 양방향으로 연결되어 있어 이전 노드와 다음 노드 모두에 접근이 가능하다.

장점:

1. 양방향 순회 가능 - 이전/다음 노드 모두 접근 가능
2. 삭제 연산 최적화 - 이전 노드 참조가 있어 O(1)로 가능
3. 특정 노드 탐색 최적화 - 양쪽에서 탐색 가능하여 단일 연결리스트 대비 평균 탐색 시간 절반
4. 단일 연결리스트의 장점(동적 크기, 유연한 메모리 할당) 유지

단점:
1. 추가 메모리 공간 필요 (이전 노드 포인터 추가)
2. 삽입/삭제 시 포인터 처리가 더 복잡
3. 구현이 단일 연결리스트보다 복잡
4. 특정 인덱스 접근은 여전히 O(n), 다만 평균적으로 더 빠름

필수 구현 메서드

단일 연결리스트와 동일하다. 다만 이전 노드 포인터(prev)를 추가로 관리해야 한다:

• push() - 끝에 추가할 때 이전 노드 연결
• pop() - 끝에서 삭제할 때 이전 노드 처리
• shift() - 앞에서 삭제할 때 새로운 head의 prev를 null로
• unshift() - 앞에 추가할 때 이전 head의 prev 연결
• get() - 양방향 탐색으로 최적화된 조회
• set() - get으로 찾은 노드의 값만 변경
• insert() - 양쪽 노드와의 연결 처리
• remove() - 양쪽 노드와의 연결 처리

주요 구현 포인트

1. get 메서드 최적화: 찾고자 하는 인덱스가 전체 길이의 절반보다 작으면 head에서부터, 크면 tail에서부터 탐색하여 효율성 증대

2. 노드 삽입/삭제 시 4개의 포인터 처리:

// 삽입 예시
beforeNode.next = newNode;
newNode.prev = beforeNode;
afterNode.prev = newNode;
newNode.next = afterNode;

// 삭제 예시
beforeNode.next = afterNode;
afterNode.prev = beforeNode;
removed.next = null;
removed.prev = null;

3. 메모리 관리를 위해 불필요한 참조 제거:
   - 노드 삭제 시 해당 노드의 prev, next를 null로 설정
   - 리스트가 비었을 때 head, tail을 null로 설정

이중 연결리스트는 양방향 접근이 가능하다는 장점 때문에 일반적으로 단일 연결리스트보다 선호됨.

특히 브라우저의 방문 기록이나 최근 작업 목록과 같이 양방향 탐색이 필요한 경우에 유용.

 

 

구현 코드와 설명

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
        this.prev = null;    // 이전 노드를 참조하는 프로퍼티가 추가됨
    }
}

class DoublyLinkedList {
    // 메서드를 제외한 기본 속성은 단일연결리스트와 같음
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    
    /*  리스트의 끝에 노드를 추가하는 메서드    */
    push(val) {
        const newNode = new Node(val);
        if(this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;    //기존 테일의 넥스트에 생성한 노드를 할당
            newNode.prev = this.tail;    // 생성한 노드의 prev에도 기존 테일을 할당.
            this.tail = newNode;        // 생성한 노드를 신규 테일로 할당
        }
        this.length++;
        return this;
    }
    
    /*  리스트의 테일을 반환하고 제거하는 메서드    */
    pop() {
        if(!this.head) return undefined; //또는 this.length === 0
        const poppedNode = this.tail;
        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.tail = poppedNode.prev;
            this.tail.next = null;
            poppedNode.prev = null;
        }
        this.length--;
        return poppedNode;
    }
    
    /*  리스트의 헤드를 반환하고 제거하는 메서드    */
    shift() {
        if(!this.head) return undefined;
        const oldHead = this.head;
        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.head = this.head.next;
            this.head.prev = null;
            oldHead.next = null;
        }
        this.length--;
        return oldHead;
    }
    
    /*  리스트의 맨 앞에 새로운 노드를 추가하는 메서드    */
    unshift(val) {
        const newNode = new Node(val);
        if(!this.head) {    // 또는 this.length === 0
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
    
    /*  인덱스를 통해 특정 노드의 값을 반환하는 메서드. 노드 제거 X    */
    get(index) {
        if(index < 0 || index >= this.length) return null;
        let count;
        let current;
        if(index <= this.length / 2) {    // 입력값인 인덱스를 중앙의 인덱스와 비교하여 빠른 쪽에서 탐색
            count = 0;
            current = this.head;
            
            while(count !== index) {
                current = current.next;
                count++;
            }
        } else {
            count = this.length - 1;
            current = this.tail;
            
            while(count !== index) {
                current = current.prev;
                count--;
            }
        }
        return current;
    }
    
    /*  인덱스와 값을 받아서 특정 노드의 값을 변경        */
    set(index, val) {
        const foundNode = this.get(index);
        if(foundNode !== null) {
            foundNode.val = val;
            return true;
        }
        return false;
    }
    
    /* 인덱스와 값을 받아서    리스트의 중간에 노드 삽입    */
    insert(index, val) {
        if(index < 0 || index > this.length) return false; // >= this.length가 아님에 주의
        if(index === 0) return !!this.unshift(val); // 입력 인덱스가 0인 경우 헤드에 추가이므로 언쉬프트
        if(index === this.length) return !!this.push(val);    //입력인덱스가 배열의 길이인 경우 push
        //중간 삽입이라면
        const newNode = new Node(val);
        
        const beforeNode = this.get(index - 1);
        const afterNode = beforeNode.next;    //원래 해당 인덱스를 가지고 있던 노드. 처리 후에는 삽입노드의 next 노드가 됨.
        beforeNode.next = newNode;
        newNode.prev = beforeNode;    // 직전 인덱스 노드의 넥스트는 신규노드. 신규노드의 prev는 직전노드로 할당
        afterNode.prev = newNode;
        newNode.next = afterNode;    // 직후 노드의 prev는 신규노드, 신규노드의 next는 직후노드
        this.length++;
        
        return true;
    }
    
    /*  중간 노드 제거    */
    remove(index) {
        if(index < 0 || index >= this.length) return null;
        if(index === 0) return this.shift();
        if(index === this.length - 1) return this.pop();
        const removed = this.get(index);
        const beforeNode = removed.prev;
        const afterNode = removed.next;
        
        beforeNode.next = afterNode;
        afterNode.prev = beforeNode;
        removed.prev = null;
        removed.next = null;
        this.length--;
        return removed;    // 또는 return true;
    }
    
    /*  리스트의 방향 바꾸기    */
    reverse() {
        let node = this.head;
        this.head = this.tail;
        this.tail = node;
        let next;
        let prev = null;
        for(let i = 0; i < this.length; i++) {
            next = node.next;    // 최초에는 기존 1번 인덱스 노드, 그 다음에는 기존 2번 인덱스 노드가 next에 할당됨. 
            node.next = prev;    //최초에는 null이 할당됨. 그 다음은 테일
            node.prev = next;    // 기존에는 next였던 노드가 prev가 됨.
            prev = node;    // 기존 node를 남겨놓음
            node = next;    // 이제 테일이 된 노드의 바로 앞 노드로 이동.
        }
    }

    /*  현재 리스트의 상태를 문자열로 반환하는 메서드    */
    toString() {
        let arr = [];
        let current = this.head;
        while(current) {
            arr.push(current.val);
            current = current.next;
        }
        return arr.join(' <-> ');
    }
}

 

 

 

위에서 구현한 이중 연결리스트의 용례

 

// 리스트 생성 및 노드 추가
const list = new DoublyLinkedList();
list.push(1);
list.push(2);
list.push(3);
console.log(list.toString()); // 출력: 1 <-> 2 <-> 3

// 앞뒤로 노드 추가
list.unshift(0);
list.push(4);
console.log(list.toString()); // 출력: 0 <-> 1 <-> 2 <-> 3 <-> 4

// 중간 삽입
list.insert(2, 1.5);
console.log(list.toString()); // 출력: 0 <-> 1 <-> 1.5 <-> 2 <-> 3 <-> 4

// 노드 값 수정
list.set(2, 'Hi');
console.log(list.toString()); // 출력: 0 <-> 1 <-> Hi <-> 2 <-> 3 <-> 4

// 양 끝에서 노드 제거
list.pop();
list.shift();
console.log(list.toString()); // 출력: 1 <-> Hi <-> 2 <-> 3

// 중간 노드 제거
list.remove(1);
console.log(list.toString()); // 출력: 1 <-> 2 <-> 3

// 리스트 뒤집기
list.reverse();
console.log(list.toString()); // 출력: 3 <-> 2 <-> 1

// 리스트의 속성 확인
console.log('Length:', list.length); // 출력: Length: 3
console.log('Head Value:', list.head.val); // 출력: Head Value: 3
console.log('Tail Value:', list.tail.val); // 출력: Tail Value: 1