<Day4- 鏈結串鏈>

• 動態的資料結構 可以從中任意添加或移除項目 會按需要進行擴充
• 比較
  • 陣列缺點： 多數語言中 陣列大小是固定的 在中間插入或移除成本很高 要移動元素
  • 鏈結串列 元素在記憶體中並不是鏈續放置的
    • 一個存放元素本身的節點和一個指向下個元素的引用（指位器or鏈結）
• 結論：
  • 優點： 添加或移不誤須移動其他元素
  • 缺點：指位器需要注意 避免出錯 ; 要想存取中間某個元素 陣列可以直接存取,鏈結串列要從頭 開始直到找到所需的元素
• coding重點：使用變數引用我們需要控制的節點 index, previous, current

1. 鏈結串列
   1. 尾部追加元素
      1. 場景
         1. 串列為空
         2. 串列不為空
   2. 移除元素
      1. 場景
         1. 移除第一個元素
         2. 移除第一個以外的元素
      2. 方法
         1. 從特定位置移除一個元素
         2. 根據元素的值移除元素
   3. 再任意位置插入一個元素
      1. 在首位插入
      2. 在其他位置插入
   4. 其他
      1. toString
      2. indexOf
      3. isEmpty
      4. size
      5. getHead

//建立鏈結串列
function LinkedList() {
  //環境設定
  let Node = function(element){
    this.element = element
    this.next = null
  }

  let length = 0
  let head = null
  //加入到最後
  this.append = function(element){
    let node = new Node(element), current
    if(head === null){
      head = node
    }
    else{
      current = head
      while(current.next){
        current = current.next
      }
      current.next = node
    }
    length++

  }
  //插入
  this.insert = function(position,element){
    //檢查
    if(position >= 0 && position <= length){

      let node = new Node(element), current = head, previous, index = 0

      if(position === 0){
        node.next = current 
        head = node
        
      }else{
        while(index++ < position){
          previous = current
          current = current.next
        }
        node.next = current
        previous.next = node
      }
      length++
      return true
      
    }else{
      return false
    }
  }
  //移除第幾項
  this.removeAt = function(position){
    //檢查越界值 position是否有效
    if(position > -1 && position < length){
      let current = head, previous, index = 0
      if(position === 0 ){
        head = current.next
      }else {
        while ( index++ < position){
          previous = current
          current = current.next
        }
        previous.next = current.next 
      length--
      return current.element
      }
    }
    else {
      return null
    }
  }
  //移除 誰
  this.remove = function(element){
    let index = this.indexOf(element)
    return this.removeAt(index)
  }
  this.indexOf = function(element){
    let current = head , index = -1 
    while(current){
      if(element === current.element){
        return index
      }
      index++
      current = current.next
    }
    return -1
  }
  //是否為空
  this.isEmpty = function(){
    return length === 0
  }
  this.size = function(){
    return length
  }
  this.getHead = function(){
    return head
  }
  //檢視
  this.toString = function(){
    let current = head, string = ''
    while(current){
      string = current.element
      current = current.next
    }
    return string
  }

}


//使用
var list = new LinkedList()
list.append(15)
list.append(10)

2. 雙向鏈結串列

• 從頭到尾 也可 從尾到頭

//雙向鏈結串列
function DoublyLinkedList(){

  let Node = function(element){
    element,
    this.next = null
    this.prev = null
  }

  let length = 0, head = null, tail = null

  this.insert =function(position,element){
    //檢查position是否有效
    if(position >= 0 && position <= length){

      let node = new Node(element),
          current = head, previous, index = 0

      if(position === 0){
        if (!head){
          head = node
          tail = node
        }else {
          node.next = current
          current.prev = node
          head = node
        }
      }else if( position === length){
        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
        cureent.prev= node
        node.prev = previous
      }
      length++
      return true

    }else{
      return false
    }
  }
  //可以有更有效能的方法 當position > length/2 從後面開始找

  this.removeAt = function(position){
    if(position > -1 && position < length){

      let current = head, previous, index = 0

      if(position === 0){
        head = current.next

        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.element

    }else{
      return null
    }
  }
  this.isEmpty = function(){
    return length === 0
  }
  this.size = function(){
    return length
  }

}

//使用
var dblist = new DoublyLinkedList()

3. 環狀鏈結串列

• head.prev指向tail，tail.next指向head