[Linear] Doubly linked list

doubly linked list는 양방향 링크드 리스트라고 불리운다.

 

양방향이기 때문에 단방향 리스트하고 비교시 이전값을 가리키는 포인터가 들어있다.

 

1. Linked List와 차이점

  1) 시작과 끝 부분이 거꾸로도 가능하다는 의미이다.

  2) 원하는 element의 이전값이나 다음값으로도 갈 수 가 있다.

  3) 단방향에서는 원하는 element를 놓쳤을 경우 처음부터 돌아가서 탐색해야하는데, 양방향은 그럴 필요없다.

 

 

양방향 연결리스트

2.functional instantiation

맨앞에 추가

맨뒤 삭제

중간삭제

function DoublyLinkedList(){
  let Node = function(item){
    this.element = item;
    this.next = null;
    this.prev = null;  //추가됨.
  };
  
  let length = 0;
  let head = null;
  let tail = null; //추가됨.
    
  this.insert = function (position, item){
    if(position >= 0 && position <= length){
      let node = new Node(item);
      let current = head;   // current는 현재 있는 노드들이야 그냥. 
      let previous;  //추가됨.
      let index =0;
      
      if(position === 0){  //처음자리에 추가.
        if(!head){    //추가된 부분. 
          head = node;
          tail = node; 
        }else{
          node.next = current;
          current.previous = node;  //추가된 부분
          head = node;
        }
      }else if(position === length){ //추가된 부분, 마지막 item찾기. 마지막부분에 추가.
        current = tail;
        current.next = node;
        node.prev = current;
        tail = node;             
      }else{ //중간에 넣기
        while(index++ < position){
          previous = current;
          current = current.next;
        }
        node.next = current;  //추가된 부분
        previous.next = node;  // 추가된 부분
    } 
    length++;
    return true;
      
    }else{
    return false;
    }
  }//end insert
  
  this.removeAt = function(position){
    if(position > -1 && position < length){
      let current = head;
      let previous;
      let index =0;
      
      if(postion === 0){ //첫번째 항목제거.
        head = current.next;
        
        //추가된 부분임. 만약 리스트 전체길이가 1인경우 tail을 업데이트해야한다. 
        if(length ===1){ 
          tail = null
        }else{
          head.prev = null;
        }
      }else if(position === length-1){ //추가된 부분,마지막 아이템 제거 
        current = tail;
        tail = current.prev;
        tail.next = null;
      }else{ //중간값 제거.
        while(index++ < position){
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
        current.next.prev = previous; //추가된 부분
      }
      length --;
      return current.item;
    }else{
      return null;
    }
  }// end removeAt
  
  //나머지는 동일.
}