链表linkList

	数组	链表
查找	连续存储，效率高 O(1)	需要通过前一个元素指向下一个元素 O(n)
插入	插入会引起被插入位后所有的元素索引的变化 O(n)	只需要改变某一个节点的 next O(1)

class LinkList {
  constructor() {
    this.length = 0;
    this.head = null; // 可以用作链表是否为空的判断
  }

  getElementAt(position) {} // 返回索引对应的元素

  append(element) {} // 添加节点

  insert(position, element) {} // 指定位置添加节点

  removeAt(position) {} // 删除指定位置元素

  indexOf(element) {} // 查找给定元素索引

  // ……
}

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

// 返回索引对应的元素
getElementAt(position) {
 if (position < 0 || position >= this.lenght ) return

    let current = this.head
    for (let i = 0; i < position; i++ ) {
        current = current.next
    }
    return current
}

// 添加节点
 append() {
     let node  = new Node(element)

     if (!this.head) {
         this.head = node
     } else {
         let current = this.getElementAt(this.length - 1)
         current.next = node
     }
     this.length++
 }


insert(postion, element) { 
    
 if (position < 0 || position > this.lenght ) return false
    const current  = this.getElementAt(position - 1)

    let node = new Node(element)

    if (postion === 0) {
        node.next === this.head
        this.head = node
    } else {
        let previous = this.getElementAt(position - 1)

        node.next = previous.next
        previous.next = node
    }
    this.length++
    return true
}

removeAt(position) {
    if (position < 0 || position > this.lenght ) return false

    if (postion === 0) {
        this.head = this.head.next
    } else {
        let previous = this.getElementAt(position - 1)
        previous.next === previous.next.next
    }
    this.length--
    return true
}

indexOf(element) {
    let current = this.head
    for (let i = 0; i <   this.length; i++) {
        if (current.element === element) return i
        current = current.next
    }
    return -1
}

双向链表
head <=> node1 <=> node2 <=> … <=> null(tail)

class DoubleLink extends LinkList {
}

class DoubleNode extends Node {
   constructor () {
       super()
       this.prev = null
   }
}