链表

337 字
2 分钟
链表

链表是什么?#

  • 多个元素组成的列表。
  • 元素的存储不连续,用next指针连在一起。

image-20250505172151849
image-20250505172151849

数组VS链表#

数组:增删非首尾元素往往需要移动元素。比如说在数组中间加一个元素,那么这个元素之后的元素都被向后移了一位。删除则是前移。

链表:增删非首尾元素,不需要移动元素,只需要更改next的指向就可以。

链表的优势:插入和删除非常快

时间复杂度取决于你找哪个元素,删除第一个就是O(1),而删除最后一个就是O(n)

如何实现链表#

JavaScript中可以用Object模拟链表。

遍历链表#

const a = {val: 'a'}
const b = {val: 'b'}
const c = {val: 'c'}
const d = {val: 'd'}
a.next = b
b.next = c
c.next = d
let p = a
while (p){
console.log(p.val)
p = p.next
}

在链表中插入值#

添加e

const e = {val: 'e'}
b.next = e
e.next = c

在链表中删除值#

删除e

b.next = c

自动垃圾回收。

链表与前端相关的地方#

JS的原型链是一个链表。原型链是沿着__proto__指的。

工作中可以用链表指针获取JSON的节点值。

const json = { a: { b: 'hello' }, c: [1, 2] };
const path = ['a', 'b'];
let point = json;
path.forEach(key => { point = point[key] });

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

链表
https://an2333.com/posts/basic/algorithm/linked-list/
作者
Annan
发布于
2025-05-11
许可协议
CC BY-NC-SA 4.0
Profile Image of the Author
Annan
写点前端,聊点 AI。
公告
博客已迁移到 Astro + Firefly,旧文章正在陆续搬家中。
分类
标签
站点统计
文章
50
分类
7
标签
28
总字数
84,160
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录