14 이중 연결 리스트

14.1 이중 연결 리스트(Doubly Linked Lists)

  이중 연결 리스트는 단일 연결 리스트와 별반 다를게 없다. 단일 연결 리스트는 노드들의 연결이 하나의 방향으로만 이어져 있었다면 이중 연결 리스트는 노드와 노드가 서로 양방향으로 이어져 있는 자료 구조이다. 즉 각 노드의 방향 지시가 두 개씩 있다는 것이다. 또한 단일 연결 리스트에 비해 양방향으로 연결되어 있어 노드에 접근할 때 테일 또는 헤드 중에 더 가까운 곳을 택해서 접근할 수 있다. 단일 연결 리스트와 전체적인 구조는 거의 똑같다. 다만 방향을 양쪽으로 다 이어야 한다는 것을 주의하면 된다.

 

14.2 노드와 이중 연결 리스트 클래스 

  단일 연결 리스트와 다른 점은 prev 프로퍼티를 추가한 것 밖에 없다.

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;
    }
}

14.3 push 메서드 구현하기

  이중 연결 리스트의 마지막 위치에 노드를 추가하는 기능이다. 단일 연결 리스트와 다른 점은 노드를 양 방향으로 이어준다는 것 뿐이다.

 

14.4 pop 메서드 

  pop 메서드는 단일 연결 리스트와 같은 방식으로 실행된다. 가장 뒤에 있는 노드를 제거해서 그 값을 반환한다.

 

14.5 shift 메서드 

  shift 메서드는 리스트의 맨 앞에 있는 노드를 제거하는 기능을 한다.

 

14.6 unshift 메서드 

  unshift 메서드는 이중 연결 리시트의 맨 앞에 노드를 추가하는 기능을 한다.

 

14.7 get 메서드 

  인수로 받은 위치에 있는 노드를 찾는 기능을 한다.

 

14.8 set 메서드 

  인수로 받은 위치에 있는 노드를 인수로 받은 값으로 갱신한다.

 

14.9 insert 메서드

  인수로 받은 위치에 인수로 받은 새로운 값을 노드로 추가한다.

 

14.10 remove 메서드

  인수로 받은 위치의 노드를 제거한다.

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){
        var newNode = new Node(val);
        if(this.length === 0){
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    
	pop(){
        if(!this.head) return undefined;
        var 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.length === 0) return undefined;
        var oldHead = this.head;
        if(this.length === 1){
            this.head = null;
            this.tail = null;
        }else{
            this.head = oldHead.next;
            this.head.prev = null;
            oldHead.next = null;
        }
        this.length--;
        return oldHead;
    }
    
    unshift(val){ // 맨 앞 추가
        var newNode = new Node(val);
        if(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;
    }

    get(index){ // 인수로 받은 인덱스에 위치하는 노드 찾기
        if(index < 0 || index >= this.length) return null;
        var count;
        var 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){
        var 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;
        if(index === 0) return !!this.unshift(val);
        if(index === this.length) return !!this.push(val);

        var newNode = new Node(val);
        var beforeNode = this.get(index-1);
        var afterNode = beforeNode.next;

        beforeNode.next = newNode, newNode.prev = beforeNode;
        newNode.next = afterNode, afterNode.prev = newNode;
        this.length++;
        return true;
    }
    
    remove(index){
        if(index < 0 || index >= this.length) return false;
        if(index === this.length-1) return !!this.pop();
        if(index === 0) return !!this.shift();

        var removedNode = this.get(index);
        var beforeNode = removedNode.prev;
        var afterNode = removedNode.next;

        beforeNode.next = afterNode;
        afterNode.prev = beforeNode;

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

 

14.11 단일 연결 리스트와 이중 연결 리스트의 빅오 표기법

(Average Situation)	Singly Linked Lists	Doubly Linked Lists
Insertion	O(1)	O(1)
Removal	O(1) or O(N)	O(1)
Searching	O(N)	O(N)
Access	O(N)	O(N)

  단일 연결 리스트와 이중 연결 리스트의 시간 복잡도는 거의 동일하다. 하지만 이중 연결 리스트는 일정한 상황에서 단일 연결 리스트에 비해 훨씬 유용할 수 있지만 그 대신 메모리를 단일 연결 리스트보다 많이 소비하게 된다.

 

  배열과 비교해 본다면 배열은 인덱스 번호를 가지고 있기 때문에 접근에 굉장히 빠르다. 하지만 삭제, 추가, 삽입은 인덱스 번호의 전면 교체가 필요하므로 오래걸린다.(배열의 맨 뒤의 요소를 제거하거나, 추가하는 경우를 제외하고) 반면 연결 리스트는 삭제, 추가, 삽입이 배열에 비해 빠르다. 인덱스가 없으므로 인덱스 데이터를 바꾸는 작업이 필요하지 않기 때문이다.