JavaScript 数据结构：单链表

简介

这是有关 JavaScript 中的数据结构的新系列。

我会先给你一些关于数据结构的细节，然后我们会用 JavaScript 来实现它。这部分会比较短，因为大多数人需要熟悉它背后的逻辑步骤和概念。

如果你不熟悉大 O 符号，请阅读简易 Wiki中的文章。不要纠结于细节，只需掌握概念即可。

简单的例子：如果我有一张带纸和笔的待办事项清单，我想在清单末尾添加一项新的待办事项，就是这样O(1)。为什么？无论清单实际上有多长，在清单末尾添加一项新的待办事项总是需要相同量的工作。

今天我们从一个简单的开始：单链表。

单链表

• 现实生活中的简单例子：寻宝，你有一个起点，必须按照特定的顺序寻找地点并解决谜语；当前地点知道下一个地点，但当前地点不知道前一个地点

什么是单链表？

• 由节点组成
• 每个节点都有一个值和一个指向下一个节点的指针（或在列表末尾为空）
• 有头（=开始）、尾（=结束）和长度
• 没有像数组那样的索引
• “单独”是因为只有一个连接到另一个节点（下一个）
• 访问必须从头开始（O(N)）
• 插入成本低廉（O(1)）
• 删除可能很便宜（O(1)（头）或O(N)（尾））

什么是数组？

• 每个元素都有一个索引
• 访问成本低廉（O(1)）（每个元素都有一个索引）
• 插入和删除可能很昂贵（O(N)）（索引必须移动）

单链表的大O

• 使用权：O(N)
• 插入：O(1)
• 删除：（O(1)头部）或O(N)（尾部）
• 搜索：O(N)

何时使用单链表而不是数组？

• 如果你经常插入数据（SLL O(1)：）
• 如果你经常删除头部的数据（SLL O(1)：）

何时不应使用单链表而应使用数组？

• 如果您经常访问数据（数组O(1)：）

下一部分

我们将用 JavaScript 实现单链表的第一部分。如果您想收到通知，请订阅:)

问题

• 你在项目中用过单链表吗？为什么？
• 您是否有一些关于单链表的现实生活好例子？