介绍

链表是一种以列表存储值的数据结构，在列表中每一个值都被当作为一个节点，每一个节点都通过指针与列表的下一个值关联（若该节点是列表最后一个元素则下一个值为 null）。

有两种链表：单链表和双链表。两种链表的运作方式类似，但是在单链表中每一个节点有单指针指向下一个节点，在双链表中，每一个节点有双指针，一个指向下一个节点，一个指向上一个节点。

列表的第一个元素被当作头，列表的最后一个元素被当作尾。和数组一样，列表的长度由列表中的元素个数决定。

列表和数组主要不同包括：

• 列表没有索引，列表中的每一个值仅“知道”其通过指针连接到的值。
• 因为列表没有索引，所以我们不能随机访问列表中的元素。当我们想要访问一个值，必须通过从头到尾遍历整个列表的方法。
• 没有索引的好处是添加或删除列表中任意部分比在数组中更高效。我们只需要重新分配指针指向的“相邻”值，但是在数组中，我们需要重新分配余下所有值的索引。

和其他所有数据结构一样，可以采用不同的方法来操作以链表存储的数据。通常会使用：push（在尾部添加）、pop（在尾部删除）、unshift（在头部添加）、shift（在头部删除）、get（获取）、set（设置）、remove（删除）和 reverse（反转）。

代码实现

单链表

function Node(element){ 
    this.element = element; 
    this.next = null; 
} 
function List(){ 
    this.head = new Node('head'); 
    this.find = find; 
    this.insert = insert; 
    this.display = display; 
    this.findPrevious = findPrevious;
    this.remove = remove;
} 
function find(item){ 
    let currNode = this.head; 
    while(currNode.element!==item){ 
        currNode = currNode.next; 
    } 
    return currNode; 
} 
function insert(newElement, item){ 
    let newNode = new Node(newElement); 
    var currNode = this.find(item); 
    newNode.next = currNode.next; 
    currNode.next = newNode; 
} 
function display(){ 
    let currNode = this.head; 
    while(currNode.next!=null){ 
        console.log(currNode.next.element); 
        currNode = currNode.next; 
    } 
} 
function findPrevious (item){ 
    let currNode = this.head; 
    while(currNode.next!=null && currNode.next.element!=item){ 
        currNode = currNode.next; 
    } 
    return currNode; 
} 
function remove(item){ 
    let prevNode = this.findPrevious(item); 
    let currNode = this.find(item); 
    if(currNode.next!=null){ 
        prevNode.next = currNode.next; 
        currNode.next = null; 
    } 
}

双链表

function Node (val) {
  // 每一个节点包含三个属性，其值，一个指向上一个节点的指针，一个指向下一个节点的指针
  this.val = val;
  this.next = null;
  this.prev = null;
}

function DoublyLinkedList () {
  // 列表有三个属性，头，尾和列表的大小
  this.head = null
  this.tail = null
  this.length = 0

  this.push = push
  this.pop = pop
  this.shift = shift
  this.unshift = unshift
  this.get = _get
  this.set = _set
  this.insert = insert
  this.toString = toString
}

// push 方法将值作为参数并赋值给链表尾
function push(val) {
  const 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 方法删除链表尾
function pop() {
  if (!this.head) return undefined
  const 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 方法删除链表头
function shift() {
  if (this.length === 0) return undefined
  const 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 方法将值作为参数并赋值给链表头
function unshift(val) {
  const 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 方法将索引作为参数并返回链表对应索引的值
function _get(index) {
  if (index < 0 || index >= this.length) return null
  let count, current
  if (index <= this.length / 2) {
    count = 0
    current = this.head
    while (count !== index) {
      current = current.next
      count++
    }
  } else {
    count = this.length - 1
    current = this.tail
    while (count !== index) {
      current = current.prev
      count--
    }
  }
  return current
}
// set 方法将索引和值作为参数，修改链表中索引所在的节点值为传入的参数值
function _set(index, val) {
  var foundNode = this.get(index)
  if (foundNode != null) {
    foundNode.val = val
    return true
  }
  return false
}
// insert 方法将索引和值作为参数，将值插入链表响应索引位置
function 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
}

function toString() {
  let arr = []
  let current = this.head
  do {
    arr.push(current.val)
    current = current.next
  } while (current)
  console.log(arr.join('->'))
}

const list = new DoublyLinkedList()
list.push(1)
list.push(3)
list.push(2)
list.insert(2, 'xx')
list.push(5)
list.toString()