### 链表的实现

var LinkedList = function() {  const Node = function(element) {    this.element = element    this.next = null  }
let head = null  let current  let length = 0
// 在链表末尾加入元素  this.append = function(element) {    const node = new Node(element)    if (head === null) {       // 插入第一个链表      head = node    } else {      current = head      while (current.next) {     // 找到最后一个节点        current = current.next      }      current.next = node    }    length++  }
// 移除指定位置元素  this.removeAt = function(position) {    if (position > -1 && position < length) {      let previous      let index = 0      if (position === 0) {         // 如果是第一个链表的话, 特殊对待        head = head.next      } else {        current = head        while (index < position) {  // 循环找到当前要删除元素的位置          previous = current          current = current.next          index++        }        previous.next = current.next      }      length--    }  }
// 在指定位置加入元素  this.insert = function(position, element) {    const node = new Node(element)    let index = 0    let current, previous    if (position > -1 && position < length + 1) {      if (position === 0) { // 在链表最前插入元素        current = head        head = node        head.next = current      } else {        current = head        while (index < position) { // 同 removeAt 逻辑, 找到目标位置          previous = current          current = current.next          index++        }        previous.next = node       // 在目标位置插入相应元素        node.next = current      }      length++    }  }
// 链表中是否含有某个元素, 如果有的话返回相应位置, 无的话返回 -1  this.indexOf = function(element) {    let index = 0    current = head    while (index < length) {      if (current.element === element) {        return index      }      current = current.next      index++    }    return -1  }
// 移除某元素  this.remove = function(element) {    const position = this.indexOf(element)    this.removeAt(position)  }
// 获取大小  this.size = function() {    return length  }
// 是否为空  this.isEmpty = function() {    return length === 0  }
// 打印链表元素  this.log = function() {    current = head    let str = current.element    while (current.next) {      current = current.next      str = str + ' ' + current.element    }    return str  }}
// 测试用例var linkedList = new LinkedList()linkedList.append(5)linkedList.append(10)linkedList.append(15)linkedList.append(20)linkedList.log()         // '5 10 15 20'linkedList.removeAt(1)linkedList.log()         // '5 15 20'linkedList.insert(1, 10)linkedList.log()

### 双向链表

var DbLinkedList = function() {  const Node = function(element) {    this.element = element    this.next = null    this.prev = null  }
let head = null  let tail = null  let current, previous  let length = 0
// 指定任意位置插入元素  this.insert = function(position, element) {    let index = 0    const node = new Node(element)    if (position > -1 && position < length + 1) {      if (position === 0) {             // ① 在开头插入元素        if (head === null) {  // 链表内元素为空          head = node          tail = node        } else {              // 链表内存在元素          current = head          head = node          head.next = current          current.prev = head        }      } else if (position === length) { // ② 在末尾插入元素        current = tail        tail = node        current.next = tail        tail.prev = current      } else {                          // ③ 在链表中插入元素        current = head        while (index < position) { // 找到需插入节点的位置          previous = current          current = current.next          index++        }        previous.next = node        node.next = current
current.prev = node        node.prev = previous      }      length++    }  }
// 删除指定位置的元素  this.removeAt = function(position) {    let index = 0    if (position > -1 && position < length) {      if (position === 0) {                  // 删除链表最开头的元素        if (length === 1) {          head = null          tail = null        } else {          current = head          head = current.next          head.prev = current.prev        }      } else if (position === length - 1) {  // 删除链表最末尾的元素        current = tail        tail = current.prev        tail.next = current.next      } else {                               // 删除链表中的元素        current = head        while (index < position) {          previous = current          current = current.next          index++        }        previous.next = current.next        current.next.prev = previous      }      length--    }  }
this.log = function() {    current = head    let str = current.element    while (current.next) {      current = current.next      str = str + ' ' + current.element    }    return str  }}
var dbLinkedList = new DbLinkedList()dbLinkedList.insert(0, 5)dbLinkedList.insert(1, 10)dbLinkedList.insert(2, 15)dbLinkedList.insert(3, 20)dbLinkedList.insert(4, 25)dbLinkedList.log()         // "5 10 15 20 25"dbLinkedList.removeAt(4)dbLinkedList.removeAt(0)dbLinkedList.removeAt(1)dbLinkedList.log()         // "10 20"