[Udemy] 이중 연결 리스트 (Double Linked List) 구현

정의

이중 연결 리스트는 단일 연결리스트에서 각 node에 prev(포인터)만 추가된 자료구조이다.

prev(포인터)가 있어 유연성이 늘어난 만큼 메모리가 더 크다.

이중 연결 리스트

 

코드 및 구현

1. Node 객체 구현

class Node {
    constructor(val) {
        this.val = val
        this.next = null;
        this.prev = null;
    }
}

 

단일 연결 리스트의 Node 클래스의 constructor에 prev 포인터를 추가했다.

 

 

2. DoubleLinked List 구현

2.1. push 메서드 구현

단일 연결 리스트의 마지막 부분에서 요소를 추가하는 메서드

push(val) {
        let node = new Node(val);

        if (!this.head) { // if (this.length === 0) 동일
            this.head = node;
        } else {
            node.prev = this.tail;
            this.tail.next = node;
        }
        this.tail = node;
        this.length++;
        return this;
}

 

새로 추가되는 node의 prev 포인터를 지정해줘야한다.

 

 

2.2. pop 메서드 구현

단일 연결 리스트의 마지막 요소를 제거하는 메서드

pop() {
        if (!this.head) return;

        let popped = this.tail;
        if (this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.tail = popped.prev;
            this.tail.next = null;
            popped.prev = null
            
        }
        this.length--;
        return popped;
}

 

단일 연결 리스트에서는 반복문을 통해 마지막 직전 요소에 도달해야만 했다.

하지만 이중 연결리스트는 prev 포인터가 있으므로 쉽게 마지막 직전 요소에 접근할 수 있다.

 

❗️주의할 점은 popped으로 제거된 요소의 prev 값도 null 초기화 해줘야한다는 점이다.

만약 popped 된 객체를 변수에 저장했을 경우 popped를 참조하여 연결리스트에 접근할 수 있기 때문이다.

 

 

2.3. shift 메서드 구현

단일 연결 리스트의 첫번째 요소를 제거하는 메서드

shift() {
        if (!this.head) return;

        let shifted = this.head;
        if (this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.head = shifted.next;
            this.head.prev = null;
            shifted.next = null
        }
        this.length--;
        return shifted;
}

 

shift 메서드 역시 맨 앞에 제거된 shifted 요소의 next 포인터를 null로 초기화 해줘야한다.

그렇지 않으면 shifted된 요소로 이중 연결 리스트에 접근 가능하기 때문이다.

 

 

2.4. unshift 메서드 구현

단일 연결 리스트의 첫번째 부분에 요소를 추가하는 메서드

unshift(val) {
        let node = new Node(val);

        if (this.length === 0) {
            this.head = node;
            this.tail = node;
        } else {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
        this.length++;
        return this;
}

 

새롭게 추가되는 node의 prev, next 포인터를 모두 지정해줘야한다.

 

 

2.5. get 메서드 구현

단일 연결 리스트의 인덱스에 해당하는 node 객체를 반환하는 메서드

get(index) {
        if (index < 0 || index >= this.length) return null;
        let curr;
        if (index <= this.length / 2) {
            curr = this.head;
            for (let i = 0; i < index; i++) {
                curr = curr.next;
            }
        } else {
            curr = this.tail;
            for (let i = 0; i < this.length - index - 1; i++) {
                curr = curr.prev
            }
        }
        return curr;
}

 

이중 연결 리스트에서는 tail에서 부터 접근이 가능하므로, index와 연결 리스트의 중간 길이를 비교하여

중간 길이보다 작으면 head에서, 중간 길이보다 크면 tail에서 시작하여

코드를 최적화 할 수 있다.

 

 

2.6. set 메서드 구현

단일 연결 리스트의 인덱스에 해당하는 node 객체의 val을 수정하는 메서드

set(val, index) {
        let node = this.get(index);

        if (!node) return false;

        node.val = val;
        return true;
}

 

단일 연결 리스트의 set과 동일하다.

 

 

2.7. insert 메서드 구현

단일 연결 리스트의 인덱스에 해당하는 위치에 node 객체를 추가하는 메서드

insert(val,index) {
        if (index < 0 || index > this.length) return false;
        if (index === 0) return !!this.unshift(val);
        if (index === this.length) return !!this.push(val);
        
        let node = new Node(val);
        let curr = this.get(index - 1);
        node.next = curr.next;
        node.next.prev = node;
        node.prev = curr;
        curr.next = node;
        this.length++;
        return true;
}

 

단일 연결 리스트와 비슷하지만 prev 포인터가 추가되었으므로 이를 고려해줘야한다.

 

 

2.8. remove 메서드 구현

단일 연결 리스트의 인덱스에 해당하는 node 객체를 제거하는 메서드

remove(index) {
        if (index < 0 || index >= this.length) return;
        if (index === 0) return !!this.shift();
        if (index === this.length - 1) return !!this.pop();

        let removed = this.get(index);

        removed.next.prev = removed.prev
        removed.prev.next = removed.next;
        removed.next = null;
        removed.prev = null;
        this.length--;
        return removed;
}

 

remove된 요소로 연결 리스트에 접근하지 못하도록 next, prev를 null로 초기화한다.

 

 

2.9. reverse 메서드 구현

단일 연결 리스트를 역순으로 재배치하는 메서드

reverse(){
        if(this.length <= 1) return this;
        
        let temp = this.head;
        this.head = this.tail
        this.tail = temp
        
        let prev = this.tail;
        let curr = prev.next;
        let next = curr.next;
        
        while (next) {
            curr.next = prev;
            prev.prev = curr;
            prev = curr;
            curr = next;
            next = curr.next
        }
        curr.next = prev;
        prev.prev = curr;
        this.head.prev = null
        this.tail.next = null;
        return this;
}

 

prev, curr, next 변수를 옮겨가며 prev의 포인터, curr의 포인터를 수정한다.

 

 

시간복잡도

 

단일 연결 리스트와 동일한 시간복잡도를 갖는다.

삽입의 경우, 최악의 상황에선 O(n)이 될 수도 있다.

 

검색은 index가 길이의 중간보다 큰지 작은지에 따라 최적화할 수 있으므로 O(n/2)가 되지만,

이는 O(n)과 큰 차이는 없다.

 

 

참조

Udemy - Js 알고리즘 & 자료구조 강의