145-data_structure-5-linkedlist~链表简介
概述
多个元素组成的列表
元素存储不连续，用next指针链接在一起。
与数组对比
数组：增删非首尾元素的时候往往需要移动元素。
链表：增删非首尾元素，不需要移动元素，只需要更改 next 指向即可。
使用对象模拟
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;
}
// 插入
const e = { val: 'e' };
c.next = e;
e.next = d;
// 删除
c.next = d;
总结
- 链表里的元素存储不是连续的，节点之间通过next 连接
- JavaScript 中没有链表这种数据结构，但可以用 Object 模拟链表
- 链表常用操作：修改next（增删节点），遍历链表（修改指针，让指针沿着链表走）
与前端相关
-
js 中的原型链也是一个链表（沿着
__proto__属性走） -
使用链表指针可以获取 JSON 的节点值 -- 使用链表指针，模拟遍历链表的算法，获取某个json节点的值
前端与链表
js原型链
概述
-
原型链的本质是链表
-
原型上的节点是各种原型对象，eg：Function.prototype, Object.prototype ...
-
原型链通过
__proto__属性连接各种原型对象
obj -> Object.prototype -> null
func -> Function.prototype -> Object.prototype -> null
arr -> Array.prototype -> Object.prototype -> null
知识点
- 如果 A 沿着原型链能找到 B.prototype，那么 A instanceof B 为 true
- 如果在 A 对象上没有找到 x 属性，那么会沿着原型链找 x 属性
应用
- instanceof 的原理，并用代码实现
知识点：如果 A 沿着原型链能找到 B.prototype，那么 A instanceof B 为 true
解法：遍历A的原型链，如果找到B.prototype，返回true，否则返回false。
const instanceOf = (A, B) => {
let p = A
while (p) {
if (p === B.prototype) {
return true
}
p = p.__proto__
}
return false
}
2、
var foo = {}
var F = function(){}
Object.prototype.a = 'value a'
Function.prototype.b = 'value b'
console.log(foo.a) // 'value a'
console.log(foo.b) // undefined
console.log(F.a) // 'value a'
console.log(F.b) // 'value b'
知识点：如果在 A 对象上没有找到 x 属性，那么会沿着原型链找 x 属性
解法：明确 foo 和 F 变量的原型链，沿着原型链找 a 属性和 b 属性
使用链表指针获取 JSON 的节点值
概述
链表在前端的实际应用
代码
const json = {
a: { b: { c: 1 } },
d: { e: 2 },
};
const path = ['a', 'b', 'c'];
let p = json;
path.forEach((k) => {
p=p[k];
});