第5章 数据结构之“链表”

链表简介

1.多个元素组成的列表。
2.元素的存储不连续，用next指针连在一起。

数组 vs 列表

1. 数组：增删非手尾元素时往往需要移动元素。如果要在数组中增加一个元素，数组后面的所有元素需要往后面移动一位。如果在数组中删除一个元素，后面的元素都要往前移动一位。
2. 链表：增删非首尾元素，不需要移动元素，只需要更改next指针。
3. javascript中是没有链表数据结构，但是可以使用Object模拟一个链表。

模拟链表数据结构(其实就是一个嵌套的Object)

const a = {value: 'a'}
const b = {value: 'b'}
const c = {value: 'c'}
const d = {value: 'd'}a.next = b
b.next = c
c.next = d

链表的操作：

// 构建链表
const a = {value: 'a'}
const b = {value: 'b'}
const c = {value: 'c'}
const d = {value: 'd'}a.next = b
b.next = c
c.next = d// 遍历链表
// 声明一个指针p（point），然后在循环里面更改p=p.next,然后在这个位置就可以访问链表里面的元素了。
let p = a
while(p) {console.log(p.value)p = p.next
}// 插入(在c，d中间插入一个e元素)：
const e = { value: 'e' }
c.next = e
e.next = d// 删除e（改变next指针）
c.next = d

leetCode： 237.删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。

var deleteNode = function (node) {// 将被删除节点的值改为下一个节点的值。node.value = node.next.val// 删除下个节点。node.next = node.next.next
}时间复杂度：O(1)
空间复杂度：O(1)

leetCode：206.反转链表

反转一个单链表。

什么双指针遍历链表？一个指针指向2，一个指向1，，下一次，指向2的指向3，指向1的指向2

var reverseList = function (head) {// p1指向头部，p2指向nulllet p1 = head;let p2 = null;while(p1) {console.log(p1.val, p2 && p2.val)// 临时保存p1, const temp = p1.nextp1.next = p2p2 = p1p1 = temp}return p2
}时间复杂度：O(n)
空间复杂度：O(1)（因为循环过程中只有单个值，既不是数组，也不是矩阵）

leetCode： 2.两数相加?

题目：

var addTwoNumbers = function (l1, l2) {const l3 = new ListNode(0)let p1 = l1;let p2 = l2;let p3 = l3;let carry = 0while(p1 || p2) {const v1 = p1 ? p1.val : 0;const v2 = p2 ? p2.val : 0const val = v1 + v2 + carrycarry = Math.floor(val / 10)p3.next = new ListNode(val % 10)if (p1) p1 = p1.nextif (p2) p2 = p2.nextp3 = p3.next}if (carry) {p3.next = new ListNode(carry)}return l3.next
}时间复杂度： O(n)，n是两个链表的较大者，
空间复杂度： O(n)，没有数组，矩阵，但是存在链表，所以也是O(n)，n是两个链表的较大者，

leetCode： 83.删除有序链表中重复的元素

const deleteNode = function (head) {let p = head;while(p && p.next) {if(p.val === p.next.val) {p.next = p.next.next} else {p = p.next}}return head
}

leetCode： 141.环形链表

如何判断链表有环？

var hasCycle = function (head) {let p1 = head;let p2 = head;while(p1 && p2 && p2.next) {p1 = p1.nextp2 = p2.next.nextif (p1 === p2) {return true}}return false
}

js中的原型链

1. 原型链本质上是一个链表
2. 原型链上的节点是各种原型对象，例如：Function.prototype, Object.prototype, …
3. 原型链通过__proto__属性连接各种原型对象。

原型链长什么样？

obj --> Object.prototype --> null

func --> Function.prototype --> Object.prototype --> null

arr --> Array.prototype --> Object.prototype --> null

num --> Number.prototype --> Object.prototype --> null

str --> String.prototype --> Object.prototype --> null

func：代表函数实例
obj：代码对象实例
arr: 代码数组实例
num: 代码数字实例
str: 代码字符串实例

// 查看下面的原型链长什么样？
const obj = {}
obj.__proto__== Object.prototype
obj.__proto__: Object.prototype --> nullconst func = () => {}
obj.__proto__ ==  Function.prototype
obj.__proto__: Function.prototype --> Object.prototype --> nullconst arr = []
obj.__proto__ = Array.prototype
obj.__proto__ : Array.prototype --> Object.prototype --> null

原型链知识点：

1. 如果A沿着原型链能找到B.prototype，那么A instanceof B 为true。
2. 如果在A对象上没有找到x属性，那么就会沿着A的原型链找x属性。
3. 简述instanceof的原理：遍历A的原型链，如果找到B.prototype,返回true，否则返回false

const instaceof = function (A, B) {var p = A;// 遍历原型链while(p) {if (p === B.prototype) {return true}p = p.__proto__}return false
}

value a
undefined
value a
value b

var foo = {}
var F = function () {};
Object.prototype.a = 'value a'
Function.prototype.a = 'value a'
console.log(foo.a)
console.log(foo.b)
console.log(F.a)
console.log(F.b)

使用链表指针获取json的节点值

const json ={a: {b: {c: 1}},d: {e: 2},
}
// 求根据path组成的路径的惊悚的值。
const path = ['a', 'b', 'c']// 解答：
let p = json
path.forEach((k) => {p = p[k]
})
console.log('p', p) // 1

总结

1.链表元素的存储不连续，用next指针连在一起。
2.javascript中是没有链表数据结构，但是可以使用Object模拟一个链表。
3.链表的常用操作：修改next，遍历链表。

技术要点：
1.js中的原型链也是一个链表，他是根据prototype指针走的。
2.使用链表指针可以获取json的节点值。