資料結構之“連結清單”
- 連結清單是什麼？
- 數組 vs 連結清單
- JS中的連結清單
- LeetCode：237.删除連結清單中的節點
- LeetCode：206.反轉連結清單
- LeetCode：2.兩數相加
- LeetCode：83.删除排序連結清單中的重複元素
- LeetCode：141.環形連結清單
- 前端與連結清單（JS中的原型鍊）
-
- 一、instanceof的使用，并用代碼實作
- 二
- 前端連結清單：使用連結清單指針擷取JSON的節點值
- 總結
- 思考題
連結清單是什麼？
多個元素組成的清單
元素存儲不連續，用next指針連在一起
數組 vs 連結清單
數組：增删非首尾元素是往往需要移動元素
連結清單：增删非首尾元素，不需要移動元素，隻需要更改next的指向即可
JS中的連結清單
JavaScript中沒有連結清單
可以用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;
// 周遊連結清單
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;
LeetCode：237.删除連結清單中的節點
解題思路
無法直接擷取被删除節點的上個節點
将被删除節點轉移到下個節點
解題步驟
将被删節點的值改為下個節點的值
删除下個節點
時間複雜度O(1)，空間複雜度O(1)
LeetCode：206.反轉連結清單
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
解題思路
反轉兩個節點：将n + 1的next指向n
反轉多個節點：雙指針周遊連結清單，重複上述操作
解題步驟
雙指針一前一後周遊連結清單
反轉雙指針
時間複雜度O(n)，空間複雜度O(1)
LeetCode：2.兩數相加
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
解題思路
國小數學題，模拟相加操作
需要周遊連結清單
解題步驟
建立一個空連結清單
周遊被相加的兩個連結清單，模拟相加操作，将個位數追加到新連結清單上，将十位數留到下一位去相加
時間複雜度O(n)，空間複雜度O(n)
LeetCode：83.删除排序連結清單中的重複元素
輸入：1 -> 1 -> 2
輸出：1 -> 2
解題思路
因為連結清單是有序的，是以重複元素一定相鄰
周遊連結清單，如果發現目前元素和下個元素值相同，就删除下個元素值
解題步驟
周遊連結清單，如果發現目前元素和下個元素值相同，就删除下個元素值
周遊結束後，傳回原連結清單的頭部
時間複雜度O(n)，空間複雜度O(1)
LeetCode：141.環形連結清單
解題思路
兩個人在圓形操場上的起點同時起跑，速度快的人一定會超過速度慢的人一圈
用一快一慢兩個指針周遊連結清單，如果指針能夠相逢，那麼連結清單就有圈
解題步驟
用一快一慢兩個指針周遊連結清單，如果指針能夠相逢，就傳回true
周遊結束後，還沒有相逢就傳回false
時間複雜度O(n)，空間複雜度O(1)
前端與連結清單（JS中的原型鍊）
原型鍊簡介
原型鍊的本質是連結清單
原型鍊上的節點是各種原型對象，比如Function.prototype、Object.prototype…
原型鍊通過__proto__屬性連結各種原型對象
原型鍊長啥樣
obj -> Object.prototype -> null
func -> Function.prototype -> Object.prototype -> null
arr -> Array.prototype -> Object.prototype -> null
原型鍊知識點
如果A沿着原型鍊能找到B的原型對象（B.prototype），那麼A instanceof B為true
如果在A對象上沒有找到x屬性，那麼會沿着原型鍊找x屬性
const obj = {}
const func = () => {}
const arr = []
//原型鍊通過__proto__屬性連結各種原型對象
console.log(obj .__proto__ === Object.prototype) //true
console.log(func.__proto__ === Function.prototype) //true
console.log(func.__proto__.__proto__ === Object.prototype) //true
console.log(arr.__proto__ === Array.prototype) //true
console.log(arr.__proto__.__proto__ === Object.prototype) //true
//如果A沿着原型鍊能找到B的原型對象（B.prototype），那麼A instanceof B為true
console.log(func instanceof Function) //true
console.log(func instanceof Object) //true
//fuc的proto屬性指向Function的原型對象，
//func即是object的執行個體，也是function的執行個體
//如果在A對象上沒有找到x屬性，那麼會沿着原型鍊找x屬性
const obj = {};
Object.prototype.x = 'x'
const func = () => {};
Function.prototype.y = 'y'
console.log(obj.x) //x
console.log(obj.y) //undefined
console.log(func.x) //x
console.log(func.y) //y
一、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;
}
二
var foo = {},F = Function(){};
Object.prototype.a = 'value a';
Function.prototype.b = 'value b'
console.log(foo.a)
console.log(foo.b)
console.log(F.a)
console.log(F.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];
})
總結
連結清單裡的元素存儲不是連續的，之間通過next連接配接
JavaScript中沒有連結清單，但可以用Object模拟連結清單
連結清單常用操作：修改next、周遊連結清單
JS中的原型鍊也是一個連結清單
使用連結清單指針可以擷取JSON的節點值
思考題
1、編寫一個 instanceOf 方法，可以判斷一個變量是否是另一個變量的執行個體
2、請判斷一個連結清單是否為回文連結清單。題目連結：https://leetcode-cn.com/problems/palindrome-linked-list/