前端之数据结构（二）

直接书接上回。

数据结构

数据结构：计算机存储、组织数据的方式，就像锅碗瓢盆。

链表

• 多个元素组成的列表。

• 元素存储不连续，用 next 指针连载一起。

那为啥不用数组呢？

• 数组：增删非首尾元素往往需要移动元素。

• 链表：增删非首尾元素，不需要移动元素，只需要更改 next的指针即可。

• 在 JavaScript中是没有链表的，但是可以用 Object模拟链表。

通过如下代码，我们就可以建造一个简易的链表：

const a = {val: 1}const b = {val: 2}const c = {val: 3}const d = {val: 4}
a.next = bb.next = cc.next = d

结构如下：

那怎么遍历链表呢？

let p = a;while (p) {    console.log(p.val);    p = p.next}
// 1// 2// 3// 4

那插入链表呢？

很简单。

const e = { val: '5'}c.next = ee.next = d

这时候我们就能看到插入的数据了。

还有删除呢？

更简单了。

c.next = d

看，已经删除完了。

原型链与链表

• 原型链的本质就是链表。

• 原型链 上的结点是各种原型对象，比如 Object.prototype, FUnction.prototype。

• 原型链通过 __proto__属性链接各种原型对象，而链表通过 next 链接。

那原型链长啥样呢？

我们可以发现，func和arr 是指向自己的原型链对象，在指向 Obj 的原型链对象。

我们可以通过如下代码，验证一下原型链：

const arr = new Array()const fun = () => {}const Obj = new Object()

• 如果 A 沿着原型链能找到 B.prototype, 那么 A instanceOf B 为 true。

• 同上，遍历原型链和遍历链表一样，

const instanceOf = (A, B) => {    let p = A    while (p) {        if (p === B.prototype) {            return true        }        p = p.prototype    }    return false}

end~~~