链表是一种线性结构，由一个一个的节点连接而成，具体结构如下：
    链表 - 图1
    可以看出，每个节点保存了两个值，一个值是节点自身的数据，另一个值是一个指针，指向下一个节点。通过next指针就可以将所有节点连接起来。节点的数据结构如下：

    1. class LinkNode {
    2.   constructor (e = null, next = null) {
    3.     this.e = e
    4.     this.next = next
    5.   }
    7.   toString () { // 方便打印
    8.     return this.e.toString()
    9.   }
    10. }

    根据上述说明，可以写出链表的数据结构：

    1. class LinkedList {
    2.   constructor () {
    3.     this.dummyHead = new LinkNode() // 为了方便操作使用了一个虚拟头结点，这个节点的next指针指向头结点
    4.     this.size = 0
    5.   }
    7.   getSize () {
    8.     return this.size
    9.   }
    11.   isEmpty () {
    12.     return this.size === 0
    13.   }
    15.   add (index, e) {
    16.     if (index < 0 && index >= this.size) throw new RangeError('Add failed. Inlegal index')
    18.     let prev = this.dummyHead
    19.     for (let i = 0; i < index; i ++) {
    20.       prev = prev.next
    21.     }
    22.     // const Node = new LinkNode(e)
    23.     // Node.next = prev.next
    24.     // prev.next = Node
    25.     // 上面三行代码等价于下面这句
    26.     prev.next = new LinkNode(e, prev.next)
    27.     this.size ++
    28.   }
    30.   addFirst (e) {
    31.     this.add(0, e)
    32.   }
    34.   addLast (e) {
    35.     this.add(this.size, e)
    36.   }
    38.   get (index) {
    39.     if (index < 0 || index >= this.size) throw new RangeError('Add failed. Inlegal index')
    41.     let cur = this.dummyHead.next
    42.     for (let i = 0; i < index; i ++) {
    43.       cur = cur.next
    44.     }
    45.     return cur.e
    46.   }
    48.   getFirst () {
    49.     return this.get(0)
    50.   }
    52.   getLast () {
    53.     return this.get(this.size - 1)
    54.   }
    56.   set (index, e) {
    57.     if (index < 0 || index >= this.size) throw new RangeError('Add failed. Inlegal index')
    59.     let cur = this.dummyHead.next
    60.     for (let i = 0; i < index; i ++) {
    61.       cur = cur.next
    62.     }
    63.     cur.e = e
    64.   }
    66.   contains (e) {
    67.     let cur = this.dummyHead.next
    68.     while (cur !== null) {
    69.       if (cur.e === e) return true
    70.       cur = cur.next
    71.     }
    72.     return false
    73.   }
    75.   remove (index) {
    76.     let prev = this.dummyHead
    77.     for (let i = 0; i < index; i ++) {
    78.       prev = prev.next
    79.     }
    80.     const node = prev.next
    81.     prev.next = prev.next.next
    82.     node.next = null
    83.     this.size --
    84.   }
    86.   removeFirst () {
    87.     this.remove(0)
    88.   }
    90.   removeLast () {
    91.     this.remove(this.size - 1)
    92.   }
    94.   removeElement (e) {
    95.     let cur = this.dummyHead
    96.     while (cur.next) {
    97.       if (cur.next.e === e) cur.next = cur.next.next
    98.       else cur = cur.next
    99.     }
    100.   }
    102.   toString () {
    103.     let ret = ''
    104.     let cur = this.dummyHead.next
    105.     for (; cur !== null; cur = cur.next) {
    106.       ret += cur.toString() + ' => '
    107.     }
    108.     ret += 'NULL'
    109.     return ret
    110.   }
    111. }
    113. module.exports = LinkedList

    也可以使用递归的方式：

    1. /**
    2.  * 使用递归的方式
    3.  */
    4. class LinkedList {
    5.   constructor () {
    6.     this.head = null
    7.     this.size = 0
    8.   }
    10.   isEmpty () {
    11.     return this.size === 0
    12.   }
    14.   getSize () {
    15.     return this.size
    16.   }
    18.   get (index) {
    19.     if (index < 0 || index > this.size) throw new RangeError('Get failed. Illegal index.')
    21.     return this._get(index, this.head)
    22.   }
    24.   _get (index, node) {
    25.     if (index === 0) return node.el
    27.     return this._get(index - 1, node.next)
    28.   }
    30.   getFirst () {
    31.     return this.get(0)
    32.   }
    34.   getLast () {
    35.     return this.get(this.size)
    36.   }
    38.   set (index, el) {
    39.     if (index < 0 || index >= this.size) throw new RangeError('Add failed. Illegal index.')
    41.     this._set(index, el, this.head)
    42.   }
    44.   _set (index, el, node) {
    45.     if (index === 0) {
    46.       node.el = el
    47.       return
    48.     }
    50.     this._set(index - 1, el, node.next)
    51.   }
    53.   setFirst (el) {
    54.     this.set(0, el)
    55.   }
    57.   setLast (el) {
    58.     this.set(this.size, el)
    59.   }
    61.   contains (el) {
    62.     return this._contains(el, this.head)
    63.   }
    65.   _contains (el, node) {
    66.     if (node === null) return false
    68.     if (node.el === el) return true
    70.     return this._contains(el, node.next)
    71.   }
    73.   add (el, index) {
    74.     if (index < 0 || index > this.size) throw new RangeError('Add failed. Illegal index.')
    76.     this.head = this._add(this.head, el, index)
    77.     this.size ++
    78.   }
    80.   _add (node, el, index) {
    81.     if (index === 0) return new LinkNode(el, node)
    82.     node.next = this._add(node.next, el, index - 1)
    83.     return node
    84.   }
    86.   addFirst (el) {
    87.     this.add(el, 0)
    88.   }
    90.   addLast (el) {
    91.     this.add(el, this.size)
    92.   }
    94.   remove (index) {
    95.     if (index < 0 || index >= this.size) throw new RangeError('Add failed. Illegal index.')
    97.     const ret = this._remove(index, this.head)
    98.     this.head = ret.keys().next().value
    99.     this.size --
    100.     return ret.get(this.head)
    101.   }
    103.   _remove (index, node) {
    104.     // 这里注意，由于需要返回被删除的节点的值，所以使用map进行保存
    105.     if (index === 0) return new Map([[node.next, node.el]])
    106.     const ret = this._remove(index - 1, node.next)
    107.     node.next = ret.keys().next().value // 利用迭代器的特性取出key值
    108.     return new Map([[node, ret.values().next().value]])
    109.   }
    111.   removeFirst () {
    112.     return this.remove(0)
    113.   }
    115.   removeLast () {
    116.     return this.remove(this.size - 1)
    117.   }
    119.   removeElement (el) {
    120.     this.head = this._removeElement(el, this.head)
    121.   }
    123.   _removeElement (el, node) {
    124.     if (node === null) return null
    125.     node.next = this._removeElement(el, node.next) // 注意要先执行这一步求出移除el后子链表的头结点
    126.     if (node.el === el) {
    127.       this.size --
    128.       return node.next
    129.     }
    130.     return node
    131.   }
    133.   toString () {
    134.     let ret = '[LinkedList]: '
    135.     let cur = this.head
    136.     while (cur !== null) {
    137.       ret += cur.toString() + ' => '
    138.       cur = cur.next
    139.     }
    140.     ret += 'NULL'
    141.     return ret
    142.   }
    143. }
    145. module.exports = LinkedList

    需要注意的是，递归的方式是将链表分为头结点和子链表，以add为例，_add内部将链表拆分后，子链表的头结点即是head.next，而相对应的第index个节点子链表中则是第index - 1个节点。
    使用链表也可以实现栈和队列，且因为链表是动态的线性结构，因此不需要考虑内存的问题：
    实现栈：

    1. const LinkedList = require('./LinkedList')
    3. class Stack {
    4.   constructor () {
    5.     this.data = new LinkedList()
    6.   }
    8.   push (e) {
    9.     this.data.addFirst(e)
    10.   }
    12.   pop () {
    13.     return this.data.removeFirst()
    14.   }
    16.   peek () {
    17.     return this.data.getFirst()
    18.   }
    20.   toString () {
    21.     return `[Stack]: top ${this.data.toString()}`
    22.   }
    23. }
    25. module.exports = Stack

    实现队列：

    1. class LinkNode {
    2.   constructor (e = null, next = null) {
    3.     this.e = e
    4.     this.next = next
    5.   }
    7.   toString () {
    8.     return this.e.toString()
    9.   }
    10. }
    12. class Queue {
    13.   constructor () {
    14.     this.head = null
    15.     this.tail = null
    16.     this.size = 0
    17.   }
    19.   isEmpty () {
    20.     return this.size === 0
    21.   }
    23.   enqueue (e) {
    24.     if (this.size === 0) {
    25.       this.head = this.tail = new LinkNode(e)
    26.     } else {
    27.       this.tail.next = new LinkNode(e)
    28.       this.tail = this.tail.next
    29.     }
    30.     this.size ++
    31.   }
    33.   dequeue () {
    34.     if (this.size === 0) throw new RangeError('cannot dequeue element from empty queue.')
    36.     const ret = this.head
    37.     this.head = this.head.next
    38.     if (this.head === null) this.tail = null
    39.     this.size --
    40.     return ret
    41.   }
    43.   getFront () {
    44.     return this.head
    45.   }
    47.   toString () {
    48.     let ret = '[Queue]: front '
    49.     let cur = this.head
    50.     for (; cur !== null; cur = cur.next) {
    51.       ret += cur.toString() + ' => '
    52.     }
    53.     ret += 'NULL tail'
    54.     return ret
    55.   }
    56. }
    58. module.exports = Queue