链表
337 字
2 分钟
链表
链表是什么?
- 多个元素组成的列表。
- 元素的存储不连续,用next指针连在一起。

数组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 = bb.next = cc.next = d
let p = awhile (p){ console.log(p.val) p = p.next}在链表中插入值
添加e
const e = {val: 'e'}b.next = ee.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] });文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!














