JavaScript 的数据结构和算法 - 链表篇

链表

链表 相比于数组是稍复杂的数据结构。

链表的特点：

• 线性表
• 不连续的空间存储

链表作为和数组相似的数据结构，其都是线性表。但是有个很大的不同，那就是在于存储空间的不连续性。可能你会觉得这个没啥，我们稍微详细的解释一下，你就会明白了。

链表 是通过在单个节点上标注下一个节点的位置来把所有的元素链接在一起。所以，存储上并不需要连续的空间，这样就不会出现数组需要 1G 空间，明明剩余 1.2G，却提示空间不足的情况。不过从表述也能看出，它会把单个节点变大，毕竟还要存储下一个节点的位置（双向链表还要存上一个节点位置）。

链表的拥有很多种结构，这儿就挑一些一一展开介绍。

单链表：最简单的链表，也是最常用的链表。链表的插入与删除操作都是 O(1)。 找到需要插入的位置就需要进行遍历，平均时间复杂度为 O(1)。

循环链表：循环链表就是在普通单链表的基础上，对收尾进行相连，让尾节点的 next 指向头节点。这儿提供一个 可以用循环链表来解决问题的例子，Josephus problem。

双向链表：双向链表意味着删除一个节点，就可以直接获取前序节点，操作时间复杂度就是 O(1)。

原文链接 传送门

本作品采用《CC 协议》，转载必须注明作者和本文链接