JS数据结构与算法入门(四) - 数据结构之“链表”

╰半夏微凉° 2022-11-30 01:35 227阅读 0赞

## 1. 链表是什么? ##

多个元素组成的列表  
元素存储不连续, 用next指针连在一起  
![链表][20200822170816693.png_pic_center]  
数组: 增删非首尾元素时往往需要移动元素  
链表: 增删非首尾元素, 不需要移动元素, 只需要改动next的指向即可  
JS中没有链表, 但是可以用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;
    // 遍历链表
    // 声明一个指针p 叫做a
    let p = a
    //while循环当p有值时, 不断的把p移动到next下一个位置, 然后可以访问链表每一个元素的值
    while(p) { 
    	console.log(p.val)
    	p = p.next
    }
    
    // 算法: 第一步先声明一个指针p, 指向链表头部, 然后不停的在while循环里执行p.next

第二个操作
    // 链表中插入值
    const e = {  val: e };
    c.next = e;
    e.next = d;

第三个操作
    // 链表中删除
    c.next = d;

## 2. 算法题演示 ##

**题号237. 删除链表中的节点**

思路;  
无法直接获取被删除节点的上个节点. 所以将被删除节点转移到下一节点(既然删除不了该节点, 那就删除下一个节点, 但是在删除之前把下一节点的值转移到现在节点上)

它没有任何循环, 所以时间复杂度为O(1)  
函数里没有任何数组或矩阵, 空间复杂度为O(1)

--------------------

**题号206. 反转链表**

思路:  
反转两个节点: 将N+1的next指向n  
如:  
输入: … -> n -> n + 1 -> …  
输出: … -> n + 1 -> n -> …

反转多个节点: 双指针遍历链表, 重复上述操作

步骤:  
双指针一前一后遍历链表.  
反转双指针

文字版:  
//新建两个指针  
//while在p1有值的情况下不断让p2 = p1 ; p1=p1.next  
//

var reverseList = function(head) { 
     let p1 = head;
     let p2 = null;
     while(p1) { 
         const temp = p1.next;
         p1.next = p2;
         p2 = p1;
         p1 = temp;
     }
     return p2;
    };
    // 有一个while循环体, 时间复杂度是O(n)
    // 临时变量是单个值, 空间复杂度是O(1)

--------------------

**题号2. 两数相加**

思路:  
模拟相加操作  
遍历链表

步骤:

1.  新建一个空链表
2.  遍历被相加的两个链表, 模拟相加操作, 将个位数追加到新链表上, 将十位数留到下一位去相加

文字版:  
新建空链表, 随便放一个值进去, 目前新链表只有一个节点, 这个节点无意义, 以后在后面追加. 然后开始遍历两个链表(用指针),

省略

--------------------

**题号83. 删除排序链表中的重复元素**

思路:  
因为链表是有序的, 所以重复元素一定相邻  
遍历链表, 如果发现当前元素和下个元素相邻, 就删除下个元素值  
遍历结束后, 返回原链表的头部

--------------------

**题号141. 环形链表**

--------------------

## 3. JS中的原型链 ##

原型链的本质是链表  
原型链上的节点是各种原型对象, 比如 Function.prototype, Object.prototype…  
所谓原型对象就是这些类的proptotype属性值  
原型链通过\_\_proto\_\_属性连接各种原型对象 (与链表不同, 链表是通过next连接属性值的)

**对于对象来说:**  
obj -> Object.prototype -> null obj上有一个proto属性值指向了object的原型对象, 而object的原型对象上面也有一个proto属性值指向了一个null  
**对于函数来说:**  
func -> Function.prototype -> Object.prototype -> null  
他的原型链上包含了function的原型对象和Object的原型对象 , func代表一个函数的实例, 首先它通过proto属性指向了Function的原型对象, 而Function的原型对象上面也有一个proto属性指向了Object的原型对象, 而object的原型对象上也有一个proto属性指向null  
**对于数组来说:**  
arr -> Array.prototype -> Object.prototype -> null  
它的原型链上包含了Array的原型对象和Object的原型对象, 数组上有一个proto属性指向arr的原型对象, 而arr的原型对象上也有一个proto属性指向object的原型对象, object的原型对象也有一个proto属性指向null

const obj = { };
    const func = () => { };
    const arr = [];
    
    obj.__proto__ === Object.prototype
    Object.prototype.__proto__ === null
    obj instanceof Object  //因为obj的原型链上能找到Object的原型对象
    
    fun instanceof Object
    fun instanceof Function
    fun.__proto__.__proto__ === Object.prototype
    
    arr instanceof Array
    fun instanceof Object

如果A沿着原型链能找到B.prototype, 那么A instanceof B为true  
如果在A对象上没有找到x属性, 那么会沿着原型链找x属性  
代码演示:

const obj = { }
    obj.x // undefined
    Object.prototype.x = "x"
    console.log(obj.x) //"x"

## 4. 面试题 ##

一. instanceof的原理, 并用代码实现  
分析:  
知识点如果A沿着原型链能找到B.prototype, 那么A instanceof B为true  
解法:  
遍历A的原型链, 如果找到B.prototype, 返回true ,否则返回false

二. 如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center]

## 5. 前端与链表: 使用链表指针获取JSON的节点值 ##

[20200822170816693.png_pic_center]: /images/20221124/4ad6b68b2fc841dc84c3a5f63807ffe4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/81814b13700044fc9aa144a0d5e1543a.png