为什么不直接使用数组
- 向后插入元素
const arr = [] console.time('perfTest') for (let i = 0; i < 100000; i++) { arr.push(i) } console.timeEnd('perfTest') // perfTest: 2.828ms - 向数组的头添加元素
const arr = [] console.time('perfTest') for (let i = 0; i < 100000; i++) { arr.unshift(i) // 添加、移除会导致后续元素位移，性能开销大，时间复杂度为 0(n) } console.timeEnd('perfTest') // perfTest: 792.193ms
链表
-
概念：链表是有序的数据结构，链表中的每个部分称为节点；链表可以从首、尾、中间进行数据存取；链表的元素在内存中不必是连续的空间；
-
链表的优缺点：
- 优点：添加与删除不会导致其余元素位移；
- 缺点：无法根据索引快速定位元素；
单链表
-
链表是有序的数据结构，链表中的每个部分称为节点；链表可以从首、尾、中间进行数据存取；
![]( "单链表的存储结构")
-
示例代码：
// 节点类 class LinkedNode { constructor(value) { this.value = value // 用于存储下一个节点的引用 this.next = null } } // 链表类 class LinkedList { constructor() { this.count = 0 // 单链表的长度 this.head = null } // 添加节点 (尾） addAtTail(value) { // 创建新节点 const node = new LinkedNode(value) // 检测链表是否存在数据 if (this.count === 0) { this.head = node } else { // 找到链表尾部节点，将最后一个节点的 next 设置为 node let cur = this.head while (cur.next != null) { cur = cur.next } cur.next = node } this.count++ } // 添加节点（首） addAtHead(value) { const node = new LinkedNode(value) if (this.count === 0) { this.head = node } else { // 将 node 添加到 head 的前面 node.next = this.head this.head = node } this.count++ } // 获取节点（根据索引） get(index) { if (this.count === 0 || index < 0 || index >= this.count) { return } // 迭代链表，找到对应节点 let current = this.head for (let i = 0; i < index; i++) { current = current.next } return current } // 添加节点（根据索引） addAtIndex(value, index) { if (this.count === 0 || index >= this.count) { return } // 如果 index <= 0，都添加到头部即可 if (index <= 0) { return this.addAtHead(value) } // 后面为正常区间处理 const prev = this.get(index - 1) const next = prev.next const node = new LinkedNode(value) prev.next = node node.next = next this.count++ } // 删除（根据索引） removeAtIndex(index) { if (this.count === 0 || index < 0 || index >= this.count) { return } if (index === 0) { this.head = this.head.next } else { const prev = this.get(index - 1) prev.next = prev.next.next } this.count-- } } // 测试代码 const l = new LinkedList() l.addAtTail('a') l.addAtTail('b') l.addAtTail('c')
双端链表
-
双向链表指的是在普通链表的基础上，增加一个用于记录上一个节点的属性 prev ，可进行双向访问；
-
图示：
![]( "双向链表")
环形链表
-
链表的最后一个节点的 next 指向第一个节点，形成首尾相连的循环结构，称为循环链表；在实际中，环的结束可以为链表的任意节点；
-
图示：
![]( "循环链表")
如何给链表加速
-
跳表（升维、空间换时间）
- 跳表，又叫做跳跃表、跳跃列表，在有序链表的基础上增加了“跳跃”的功能；
- 跳表在原来的有序链表上加上了多级索引，通过索引来快速查找；可以支持快速的删除、插入和查找操作；
- 跳表实际上是一种增加了前向指针的链表，是一种随机化的数据结构；
-
跳表的数据结构图型：
- 如何提高链表的线性查找的效率？
![]( "如何提高链表的线性查找的效率？")
- 如何进一步提高链表的线性查找的效率？
![]( "如何进一步提高链表的线性查找的效率？")
- 增加多级索引：索引级数为 log2n ；
![]( "增加多级索引")
- 如何提高链表的线性查找的效率？
-
现实中跳表的形态：
- 由于跳表的增删操作，索引不是那么连续规律的；
![]( "现实中跳表的形态")
- 维护成本较高，增加删除要更新一遍索引；
- 由于跳表的增删操作，索引不是那么连续规律的；
时间复杂度
-
索引个数统计
索引 节点个数 1 n/2 2 n/4 3 n/8 … … k n/(2^k) -
计算跳表的高度：假设索引有 h 级，最高级索引有 2 个节点，即n/2^h = 2 ，h = log2^n - 1，包含原始链表这一层，整个跳表的高度就是 log2^n； -
计算跳表的时间复杂度：- 假设在跳表中查询某个数据的时候，如果每一层都遍历 m 个节点，那在跳表中查询一个数据的时间复杂度就是 O(m*logn)
- 那这个 m 是多少呢？如下图所示，假设要查找的数据是 x ，在第 k 级索引中，遍历到 y 节点之后，发现
x > y，小于后面的节点 z ，所以通过 y 的 down 指针，从第 k 级下降到第 k-1 级索引；
![]( "时间复杂度")
- 在第 k-1 级索引中，y 和 z 之间只有 3 个节点（包含 y 和 z），所以，在 k-1 级索引中最多只需要遍历 3 个节点，以此类推，每一级索引都最多只需要遍历 3 个节点；
- 所以
m=3(与间距有关)，因此在跳表中查询某个数据的时间复杂度就是 O(logn)；
空间复杂度
-
原始链表大小为 n ，每 2 个节点抽一个
索引 节点个数 1 n/2 2 n/4 3 n/8 … … k-2 n/2^(k-2) k-1 n/2^(k-1) k n/2^k -
计算索引的节点总数：如果链表有 n 个节点，每 2 个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2等比数列 log2^n 项，根据等比数列公式Sn = a * (1 - r^n) / (1-r)求和为 n-1 ，所以跳表的空间复杂度为 O(n) -
如何优化时间复杂度：如果链表有 n 个节点，每 3 或 5 个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以 3 为例）：
n/3，n/9，n/27，…，27，9，3，1等比数列求和 n/2 ，所以跳表的空间复杂度为O(n)，和每 2 个节点抽取一次相比，时间复杂度要低不少呢；
跳表 VS 二分法
二分查找针对的有序数据，二分查找强依赖顺序结构；
数据量太小不适合二分查找，如果数据太小，完全没必要用二分查找，进行逐个遍历就可以了；
数据量太大也不适合二分查找，二分查找底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求也比较苛刻；
参考资料
算法基础🔮 数组
上一篇
