(JS 자료구조)이중 연결 리스트

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

• 이중 연결 리스트는 단일 연결 리스트에서 이전의 노드를 가리키는 포인터를 하나 더하는 것 뿐이다. 각각의 노드에 포인터 가 두 개씩 있게 된다.
• 이중 연결 리스트는 이처럼 반대 방향 포인터도 갖게 되어 성능상 유연함을 갖게 됐지만, 더 많은 메모리가 필요하게 됐다.(next,previous)
  

기본 구조

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

DoublyLinkedList

class DoublyLinkedList{
    constructor(){
        this.tail = null;
        this.head = null;
        this.length = 0;
    }

    push(val){
        let pushval = new Node(val);
        if(!this.head){
            this.head = pushval;
            this.tail = this.head;
        }else{
            this.tail.next = pushval;
            pushval.prev = this.tail;
            this.tail = pushval;
        }
        
        this.length++;
        return this;
    }

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

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

    unshift(val){
        let unshiftval = new Node(val);
        if(!this.head){
            this.head = unshiftval;
            this.tail = unshiftval;
        }else{
            this.head.prev = unshiftval;
            unshiftval.next = this.head;
            this.head = unshiftval;
        }
        this.length++;
        return this;
    }

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

    set(index,val){
        let foundindex = this.get(index);
        if(foundindex){
            foundindex.val = val;
            return true;
        }
        return false;
    }

    insert(index,val){
        if(index < 0 || index > this.length) return false;
        let insertval = new Node(val);
        if(index === 0) return !!this.unshift(val);
        if(index === this.length) return !!this.push(val);

        let findindex = this.get(index-1);
        let temp3 = findindex.next;
        
        findindex.next = insertval, insertval.prev = findindex;
        temp3.prev = insertval, insertval.next = temp3;
        this.length++;
        return true;
    }

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

        let removeNode = this.get(index);
        removeNode.prev.next = removeNode.next;
        removeNode.next.prev = removeNode.prev;
        removeNode.next = null;
        removeNode.prev = null;
        
        this.length--;
        return removeNode;
    }
}

이중 연결 리스트의 성능

시간복잡도

• 삽입 : O(1)
• 제거 : O(1)
• 탐색 : O(N)
• 접근 : O(N)

결론

• 이중 연결 리스트는 이전 노드를 향하는 포인터가 추가됐다는 점만 빼면 단일 연결 리스트와 거의 비슷하다.
• 노드를 찾을 때는 이중 연결 리스트가 단일 연결리스트보다 시간을 절반으로 줄일 수 있으므로 더 낫다. 이 외의 이중 연결 리스트의 시간복잡도는 단일 연결 리스트의 성능과 같다.
• 이중 연결 리스트는 추가 포인터 때문에 더 많은 메모리가 필요하다.
• 배열에 비해 삽입과 제거에 유용하다.