接下来，将看到类似图的结构如何提升数据的有序列表的性能。 链表是一种非常常见的数据结构，经常用于实现其他数据结构，它能够高效地将项目添加到表的开头、中间和结尾。 链表的基本思想类似于图，具有指向其他结点的结点，看起来像这样： 其 JSON 形式如下： { value: "A", next: { value: "B", next: { value: "C", next: {...} } } } 实现链表数据结构可以提供以下一些运算： 一个生成空链表的构造函数； 获取链表指定位置的值； 将一个值插入到链表的指定位置； 删除链表指定位置的值； 下面我们将依次介绍其实现。 一个生成空链表的构造函数 与图不同，链表具有从整个链开始的单个结点。 这被称为链表的头结点。 我们还将记录链表的长度。 constructor() { this.head = null; this.length = 0; } 获取链表指定位置的值 首先，我们需要一种方法来检索给定位置的值。这与普通列表的方式不同，我们不能直接跳转到正确的位置，而是需要遍历各个节点。 get(position) { // 如果 position 大于 LinkedList 的长度，则抛出 Position outside of list range 错误 // 从链表的头结点开始。 // 使用 node.next 遍历所有项目，直到到达指定位置。 // 返回我们找到的节点。 return current; } 将一个值插入到链表的指定位置 接下来我们需要一种向指定位置添加结点的方法。我们需要一个通用的 add 方法，它接受一个 value 和一个 position。 add(value, position) { // 首先创建一个结点来保存 value。 let node = { value, next: null }; // 有一个特例，就是在头部插入结点。直接将“next”字段设置为当前头部，然后用新创建的结点替换头结点。 if (position === 0) { // 如果在其他位置添加一个结点，则需要将它拼接在当前节点和前一个节点之间。 } else { // 首先，找到上一个结点和当前结点。 // 然后通过新建的结点的 next 字段设置为当前结点并将前一个节点的 next 字段更新为新建结点来在它们之间插入新结点 } // 最后增加长度 } 删除链表指定位置的值 最后一个方法是 remove 方法。要通过它的 position 查找到结点并将它从链表中剔除。 remove(position) { // 如果链表为空，则抛出 Removing from empty list 错误 // 如果要删除第一个结点，只需要将头结点设置为链表中的头结点的下一个结点 // 对于其他位置，需要查找上一个结点并将其 next 设置为当前位置之后的结点 // 别忘了长度减一 }