要存储多个元素，数组可能是最常用的数据结构。这种数据结构非常方便，提供了便利的语法来访问它的元素。然而，这种数据结构有一个缺点：（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。虽然 JavaScript 的 Array 类方法可以帮我们做这些事，但背后的情况同样是这样。

    链表存储有序的元素集合，但不同于数组，链表的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也成为指针或链接）组成。

    下图展示了一个链表的结构：

    单链表的实现 - 图1

    相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其它元素。然后，链表需要使用指针，因此实现链表时需要额外注意。

    数组的另一个细节是可以直接访问任何位置的任何元素，想要访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。

    先规划一下链表将实现什么方法：

    • append：向列表尾部添加元素
    • insert：向列表任意位置添加元素
    • removeAt：从列表特定位置移除元素
    • remove：从列表中删除第一个与给定元素相匹配的元素
    • indexOf：返回给定元素在列表中的索引
    • isEmpty：查看列表是否为空
    • size：查看列表中的元素个数
    • getHead：获取列表中第一个元素
    • toString：以字符串的形式输出列表中的所有元素
    1. class Node {
    2.   constructor(element) {
    3.     // 要添加到列表中的值
    4.     this.element = element
    5.     // 指向列表中下一个节点项的指针
    6.     this.next = null
    7.   }
    8. }
    10. class LinkedList {
    11.   constructor() {
    12.     this.length = 0 // 列表元素的数量
    13.     this.head = null // 第一个节点的引用
    14.   }
    16.   /**
    17.    * 向列表尾部添加元素
    18.    * @param {any} element 
    19.    */
    20.   append(element) {
    21.     let node = new Node(element) // 创建一个 Node
    23.     if (this.head === null) {
    24.       // 如果列表为空，则将添加的元素设置为列表的第一个元素
    25.       this.head = node
    26.     } else {
    27.       // 向不为空的列表添加元素
    29.       // 要向列表的尾部添加一个元素，首先需要找到最后一个元素
    30.       let current = this.head // 用于存储列表的最后一个元素
    31.       while (current.next) {
    32.         // 循环列表，直到找到最后一项
    33.         // 最后一个元素的 next 为 null，因此找到最后一个元素之后将不会再进入循环
    34.         current = current.next
    35.       }
    37.       // 找到最后一项，将其 next 赋为 node，建立链接
    38.       current.next = node
    39.     }
    41.     // 列表的长度+1
    42.     this.length++
    43.   }
    45.   /**
    46.    * 向列表的特定位置插入一个新元素
    47.    * @param {number} position 
    48.    * @param {any} element 
    49.    */
    50.   insert(position, element) {
    51.     // 插入的有效位置为 0 至 this.length 
    52.     if (position < 0 || position > this.length) {
    53.       return false // 表示插入失败
    54.     }
    56.     let node = new Node(element)
    58.     if (position === 0) {
    59.       // 在第一个位置添加元素
    60.       node.next = this.head
    61.       this.head = node
    62.     } else {
    63.       let previous = null // 用于存储位置为 position 前一位的元素
    64.       let current = this.head // 用于存储位置为 position 的元素
    66.       for (let i = 1; i <= position; i++) {
    67.         previous = current
    68.         current = current.next
    69.       }
    71.       previous.next = node
    72.       node.next = current
    73.     }
    75.     this.length++
    76.     return true
    77.   }
    79.   /**
    80.    * 从列表的特定位置移除一项
    81.    * @param {number} position 
    82.    */
    83.   removeAt(position) {
    84.     // 检查越界值，当 position 在 0 到 this.length - 1 才是有效位置
    85.     if (position < 0 || position >= this.length) {
    86.       return null // 表示没有移除元素
    87.     }
    89.     let removedElement // 用于存储被移除的元素
    91.     if (position === 0) {
    92.       removedElement = this.head // 记录被移除的元素
    94.       // 如果删除的是列表的第一个元素，只需要将 this.head 指向第二个元素即可
    95.       this.head = this.head.next
    96.     } else {
    97.       let current = this.head // 用于存储 position 所指的元素
    98.       let previous = null // 用于存储 position 前一位元素
    100.       // 找出 position 所指的元素，以及 position 的前一个元素
    101.       // 当跳出循环之后，current 为 position 所对应的元素
    102.       for (let i = 1; i <= position; i++) {
    103.         previous = current
    104.         current = current.next
    105.       }
    107.       removedElement = current // 记录被移除的元素
    109.       // 将 prevous 与 current 的下一项链接起来：跳过 current，从而移除它
    110.       previous.next = current.next
    111.     }
    113.     this.length--
    115.     return removedElement
    116.   }
    118.   /**
    119.    * 从列表中删除第一个与给定元素相匹配的元素
    120.    * @param {any} element 
    121.    */
    122.   remove(element) {
    123.     let result = false
    125.     if (this.head.element === element) {
    126.       // 移除的项为第一个元素
    127.       this.head = this.head.next
    128.       result = true // 表示删除元素成功
    129.     } else {
    130.       // 移除的项并非第一个元素
    132.       let previous = this.head
    133.       let current = this.head.next
    135.       while (current) {
    136.         if (current.element === element) {
    137.           previous.next = current.next
    138.           result = true // 表示删除元素成功
    139.         }
    140.         previous = current
    141.         current = current.next
    142.       }
    143.     }
    145.     return result
    146.   }
    148.   /**
    149.    * 返回元素在列表的索引
    150.    * @param {any} element
    151.    */
    152.   indexOf(element) {
    153.     let current = this.head
    154.     let index = 0
    156.     while (current) {
    157.       if (element === current.element) {
    158.         return index
    159.       }
    160.       index++
    161.       current = current.next
    162.     }
    164.     return -1
    165.   }
    167.   /**
    168.    * 如果链表中不包含任何元素，返回 true，否则返回 false
    169.    */
    170.   isEmpty() {
    171.     return this.length === 0
    172.   }
    174.   /**
    175.    * 返回链表包含的元素个数
    176.    */
    177.   size() {
    178.     return this.length
    179.   }
    181.   /**
    182.    * 获取第一个元素
    183.    */
    184.   getHead() {
    185.     return this.head
    186.   }
    188.   /**
    189.    * 由于列表项使用了 Node 类，需要重写继承自 JavaScript 对象默认的 toString 方法，
    190.    * 让其只输出元素的值。
    191.    */
    192.   toString() {
    193.     let current = this.head
    194.     let string = ''
    196.     while (current) {
    197.       string += current.element + (current.next ? ',' : '')
    198.       current = current.next
    199.     }
    201.     return string
    202.   }
    203. }