JS實作資料結構（四）：雙向鏈表

• 單向鏈表只能從從遍歷到尾，缺點是可以輕松到達下一個節點，但是很難回到上一個節點
• 雙向鏈表可以從頭遍歷到尾，也可以從尾遍歷到頭，一個節點既有向前的參考，也有向后的參考
• 雙向鏈表結構- 雙向鏈表方法
  • append（element）：向串列尾部添加一個新的項
  • insert（position，element）：向串列的特定位置插入一個新的項，
  • get（position）：獲取對應位置的元素
  • indexOf（element）：回傳元素在串列中的索引，如果串列中沒有該元素則回傳-1，
  • update（position，element）：修改某個位置的元素
  • removeAt（position）：從串列的特定位置移除一項，
  • remove（element）：從串列中移除一項，
  • isEmpty（）：如果鏈表中不包含任何元素，回傳true，如果鏈表長度大于0則回傳false.
  • size（）：回傳鏈表包含的元素個數，與陣列的length屬性類似，
  • toString（）：由于串列項使用了Node類，就需要重寫繼承自JavaScript物件默認的toString方法，讓其只輸出元素的值，
  • forwardString（）：回傳正向遍歷的節點字串形式
  • backwordString（）：回傳反向遍歷的節點字串形式
• 封裝雙向鏈表

function DoubleLinkedList(){
  //內部類：節點類
  function Node(data){
    this.data = data;
    this.pre =  null;
    this.next = null;
  }
  //屬性
  this.head = null;
  this.tail = null;
  this.length = 0 ;
  
  //1.append()
  DoubleLinkedList.prototype.append = function(data){
    var newNode = new Node(data);
    
    if(this.length === 0){
      this.head = newNode;
      this.tail = newNode;
    }else{
      newNode.pre = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length += 1;
  }
  
  //2.insert()
  DoubleLinkedList.prototype.insert = function(position，data){
    //越界判斷
    if(position < 0 || position > this.lengh) return false;
    //創建新節點
    var newNode = new Node(data);
    //定位
    //判斷鏈表是否為空
    if(this.length === 0){
      this.head = newNode;
      this.tail = newNode;
    }else{
      if(position === 0){
        this.head.pre = newNode;
        newNode.next = this.head;
        this.head = newNode;
      }else if(position = this.length){
        newNode.pre = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
      }else{
        var current = this.head;
        var index = 0
        while(index++ < position){
          current = current.next;
        }
        newNode.next = current;
        newNode.pre = current.pre;
        current.pre.next = newNode;
        current.pre = newNode;
      }
    }
    this.length += 1;
    return true;
  }
  
  //3.get()
  DoubleLinkedList.prototype.get = function(position){
  	if(position < 0 || position >=this.length) return false;
    var current = this.head;
    var index = 0;
    while(index++ < position){
      current = current.next;
    }
    return current.data;
  }
  
   //4.indexOf()
  DoubleLinkedList.prototype.indexOf = function(data){
    var current = this.head;
    var index = 0;
    while(current){
      if(current.data === data){
        return index;
      }else{
        current = current.next;
        index++;
      }
    }
    return -1;
  }
  
  //5.update()
  DoubleLinkedList.prototype.update = function(position){
  	if(position < 0 || position >=this.length) return false;
    var current = this.head;
    var index = 0;
    while(index++ < position){
      current = current.next;
    }
    current.data = data;
  }
  
  //6.removeAt()
  DoubleLinkedList.prototype.removeAt= function(position){
  	if(position < 0 || position >=this.length) return null;
    
    var current = this.head;
    var index = 0 ;
    if(this.length === 1){
      this.head = null;
      this.tail = null;
    }else{
      if(position === 0){
        this.head.next = null;
        this.head = this.head.next;
      }else if(position === this.length-1){
        current = this.tail;
        this.tail.pre.next = null;
        this.tail = this.tail.pre;
      }else{
        while(index++ < position){
          current = current.next;
        }
        current.pre.next = current.next;
        current.next.pre = current.pre;
      }
  	}
    this.length -= 1;
    return current.data
  }
  
  //7.remove()
  DoubleLinkedList.prototype.remove = function(){
  	var index = this.indexOf(data);
    return this.removeAt(index);
  }
  
  //8.isEmpty()
  DoubleLinkedList.prototype.ieEmpty = function(){
    return this.length === 0 ;
  }
  
  //9.size()
   DoubleLinkedList.prototype.size = function(){
    return this.length;
  }
  
  //10.獲取鏈表第一個元素
   DoubleLinkedList.prototype.getHead = function(){
    return this.head.data;
  }
  
  //11.獲取鏈表最后一個元素
   DoubleLinkedList.prototype.getTail = function(){
    return this.tail.data;
  }
  
  //12.toString()
  DoubleLinkedList.prototype.toString = function(){
    return this.backwardString();
  }
  
  //13.toString()
  DoubleLinkedList.prototype.toString = function(){
    return this.backwardString();
  }
  
  //14.forwardString()
  DoubleLinkedList.prototype.forwardString = function(){
    var current = this.tail;
    var resultString = null;
    while(current){
      resultString += current.data + " ";
      current = current.pre
    }
    return resultString;
  }
  //15.backwardString()
  DoubleLinkedList.prototype.backwardString = function(){
  	var current = this.head;
    var resultString = '';
    while(current){
      resultString += current.data + " ";
      current =current.next;
    }
    return resultString;
  }
}