이중 연결 리스트

https://visualgo.net/en/list

 

양방향으로 연결이 되어있는 구조 (prev , next)

기본적인 구조는 단일 연결 리스트와 같기에 설명은 생락하고 바로 메소드를 작성하겠다

prev와 next를 둘다 연결해야하기에 코드가 좀 더 복잡해지지만 flexible하게 사용가능해진다

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=0;
      var current=this.head
      if(index<=this.length/2){
        while(count!=index){
          current=current.next
          count++
        }
      }else{
        var count=this.length-1
        var 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 undefined
      if(index===0) return this.shift()
      if(index===this.length-1) return this.pop()
      var removeNode=this.get(index)
      removeNode.prev.next=removeNode.next
      removeNode.next.prev=removeNode.prev
      removeNode.next=null
      removeNode.prev=null
      this.length--
      return removeNode
    }
  }

var list = new DoublyLinkedList()
list.push("Harry")
list.push("Ron")
list.push("Hermione")