链表

多个元素组成的列表，元素之间存储不连续，通过next指针连在一起

链表的结构：

• js中没有链表，但我们可以用对象进行模拟 ```javascript // 链表：多个元素通过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;

- 链表的遍历
```javascript
// 1.创建一个指针指向第一个元素
let point = a;
while (point) {
    console.log(point.val);
    // 2.通过这个元素的next属性不断指向下一个元素
    point = point.next;
}

• 链表的插入

  const e = { val: "e" };
  c.next = e;
  e.next = d;
  

• 链表的删除

c.next = d;

js中的原型链：

• 首先我们要知道js的原型链本质上是一个链表，是一个通过proto作为指针连接起来的链表，例如以下

const obj = {};
const fn = function () {

}
const arr = [];
// 表示沿着原型链查找
obj --> Object.prototype --> null;
fn --> Function.prototype --> Object.prototype --> null;
arr --> Array.prototype --> Object.prototype --> null;

实例对象可以沿着原型链找到构造函数的原型对象，最后Object.prototype沿着原型链只能找到null。

• 其次我们要知道原型链上属性的查找机制：
  • 如果我们要在一个实例对象上查找一个属性，我们们首先会在这个对象身上查找，其次我们会沿着其原型链查找，也就是找到其构造函数的prototype，最后找到Object.prototype如果还没有就返回null。

// 如果在A对象上没有找到x属性那么会沿着原型链寻找x属性
let arr = [];
Object.prototype.x = "x";
console.log(arr.x); // 输出：'x'

• 最后是我们的instancesOf方法
  • 如果A沿着原型链可以找到B.prototype那么A instancesOf B便为true
  • 我们可以手动实现一下instancesOf方法

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

链表的两个基本题：

• L237.删除链表中的节点

var deleteNode = function(node) {
    // 让当前节点的值为下一个节点的值
    node.val = node.next.val;
    // 让当前节点的next属性指向下下个节点
    node.next = node.next.next;
};

• 15.反转链表

function ReverseList(pHead)
{
    // write code here
    let p1 = null;
    let p2 = pHead;
    while(p2) {
        let tmp = p2.next;
        p2.next = p1;
        p1 = p2;
        p2 = tmp;
    }
    // 此时p2已经指向了null，所以我们输出p1便好
    return p1;
}