每種編程語(yǔ)言都實(shí)現(xiàn)了數(shù)組武鲁，但在大多數(shù)語(yǔ)言中灭翔，數(shù)組大小是固定的（創(chuàng)建時(shí)指定）嵌言，從數(shù)組起點(diǎn)或中間插入或移除元素的成本很高嗅回，因?yàn)楹竺娴脑囟夹枰€(gè)挪位置。
1. 鏈表數(shù)據(jù)結(jié)構(gòu)
鏈表是一種動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)摧茴，用于存儲(chǔ)有序的元素集合绵载，可以從中任意添加或移除元素，不需要移動(dòng)其他元素苛白，可按需擴(kuò)容（如眾人手拉手娃豹，加個(gè)人和減個(gè)人都很簡(jiǎn)單），鏈表中的元素并不是連續(xù)放置的购裙，每個(gè)元素由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)懂版，和一個(gè)指向下一個(gè)元素的引用（也稱指針或鏈接）組成：
image.png
image.png
數(shù)組可以直接訪問(wèn)任何位置的元素（可以理解為是物理電路，訪問(wèn)任意位置的元素都一樣快）躏率，而想要訪問(wèn)鏈表中間的元素躯畴，就需要從表頭開(kāi)始迭代鏈表中的節(jié)點(diǎn)民鼓，挨個(gè)尋找，就像藏寶游戲蓬抄，不斷地根據(jù)線索尋找摹察。
各自優(yōu)勢(shì)：
- 鏈表：增、刪
- 數(shù)組：改倡鲸、查
1.1 創(chuàng)建鏈表
- append(element)：向列表尾部添加一個(gè)新的項(xiàng)供嚎。
- insert(position, element)：向列表的特定位置插入一個(gè)新的項(xiàng)。
- remove(element)：從列表中移除一項(xiàng)峭状。
- indexOf(element)：返回元素在列表中的索引克滴。如果列表中沒(méi)有該元素則返回-1。
- removeAt(position)：從列表的特定位置移除一項(xiàng)优床。
- isEmpty()：如果鏈表中不包含任何元素劝赔，返回true，如果鏈表長(zhǎng)度大于0則返回false胆敞。
- size()：返回鏈表包含的元素個(gè)數(shù)着帽。與數(shù)組的length屬性類似。
- toString()：由于列表項(xiàng)使用了Node類移层，就需要重寫繼承自JavaScript對(duì)象默認(rèn)的toString方法仍翰，讓其只輸出元素的值。
function LinkedList() {
// 單個(gè)節(jié)點(diǎn)類观话，表示要加入到鏈表中的項(xiàng)
let Node = function (element) {
this.element = element;
this.next = null;
};
let length = 0; // 內(nèi)部私有變量予借，記錄鏈表長(zhǎng)度
let head = null; // 頭指針
/**
* 向鏈表尾部添加一個(gè)新的項(xiàng)
* 兩種場(chǎng)景：鏈表為空，添加的是第一個(gè)元素频蛔；鏈表不為空灵迫，向其追加元素。
*
* @param element
*/
this.append = function (element) {
let node = new Node(element), current;
if (head === null) {
head = node;
} else {
current = head;
// 從表頭開(kāi)始循環(huán)找到最后一項(xiàng)
while (current.next !== null) {
current = current.next;
}
// 把節(jié)點(diǎn)鏈接到最后一項(xiàng)的 next 上
current.next = node;
}
length++; // 更新鏈表長(zhǎng)度
};
/**
* 從任意位置移除元素并返回被移除的元素
* 兩種場(chǎng)景：移除第一個(gè)元素晦溪；移除第一個(gè)以外的任一元素瀑粥。
* 被移除的元素被丟棄在計(jì)算機(jī)內(nèi)存中，等待被垃圾回收器清理三圆。
*
* @param {number} position
* @returns {element|null}
*/
this.removeAt = function (position) {
// 檢查是否越界
if (position >= 0 && position < length) {
let current = head,
previous,
index = 0;
// 分兩種情況：表頭和非表頭
if (position === 0) {
head = current.next;
} else {
// position 的前一個(gè)位置時(shí)終止循環(huán)
while (index++ < position) {
previous = current;
current = current.next;
}
// 上下節(jié)點(diǎn)進(jìn)行鏈接狞换，跳過(guò)中間將被移除的 current 節(jié)點(diǎn)
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
/**
* 在任意位置插入元素
*
* @param {number} position
* @param element
* @returns {boolean}
*/
this.insert = function (position = 0, element) {
// 檢查是否越界,注意這里包含了空鏈表時(shí)的情形
if (position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0) {
node.next = current;
head = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current; // 即新節(jié)點(diǎn)插入到目標(biāo)位置的前面，這里current可能是null
previous.next = node;
}
length++;
return true;
} else {
return false;
}
};
/**
* 把 LinkedList 對(duì)象轉(zhuǎn)換成字符串
*
* @returns {string}
*/
this.toString = function () {
let current = head,
string = '',
index = 0;
while (current) {
string += index++ + ': ' + current.element + (current.next ? '\n' : '');
current = current.next;
}
return string;
};
/**
* 查找給定元素的索引,找不到則返回 -1
*
* @param element
* @returns {number}
*/
this.indexOf = function (element) {
let current = head,
index = -1;
while (current) {
index++;
if (element === current.element) {
return index;
}
current = current.next;
}
return -1;
};
/**
* 移除給定的元素
*
* @param element
* @returns {element|null}
*/
this.remove = function (element) {
const index = this.indexOf(element);
return this.removeAt(index);
};
/**
* 鏈表是否為空
* @returns {boolean}
*/
this.isEmpty = function () {
return length === 0;
};
/**
* 鏈表大小
* @returns {number}
*/
this.size = function () {
return length;
};
/**
* 獲取表頭
* 方便實(shí)例外部訪問(wèn)和迭代鏈表
*
* @returns {element|null}
*/
this.getHead = function () {
return head;
};
}
1.2 雙向鏈表
image.png
function DoublyLinkedList() {
let Node = function (element) {
this.element = element;
this.next = null;
this.prev = null;
};
let length = 0;
let head = null;
let tail = null;
/**
* 從任意位置移除元素
*
* @param position
* @returns {element|null}
*/
this.removeAt = function (position) {
if (position >= 0 && position < length) {
let current = head,
previous,
index = 0;
if (position === 0) { // 第一項(xiàng)
head = current.next;
// 如果只有一項(xiàng)嫌术，需要更新tail
if (length === 1) {
tail = null;
} else {
head.prev = null;
}
} else if (position === length - 1) { // 最后一項(xiàng)
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
} else {
return null;
}
};
/**
* 從任意位置添加節(jié)點(diǎn)
*
* @param {number} position
* @param element
* @returns {boolean}
*/
this.insert = function (position, element) {
if (position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0) { // 在第一個(gè)位置添加
if (!head) { // 當(dāng)前鏈表為空
head = node;
tail = node;
} else {
node.next = current;
current.prev = node;
head = node;
}
} else if (position === length) { // 最后一項(xiàng)
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
current.prev = node;
node.prev = previous;
}
length++;
return true;
} else {
return false;
}
};
// 其他方法和單向鏈表類似
}
1.3 循環(huán)鏈表
循環(huán)鏈表 CircularLinkedList 可以只有單向引用哀澈，也可以像雙向鏈表一樣有雙向引用。
單向循環(huán)鏈表中：循環(huán)鏈表中 tail.next 指向 head度气。
image.png
雙向循環(huán)鏈表中：tail.next 指向 head割按，head.prev 指向 tail。
image.png
2. 鏈表相關(guān)問(wèn)題
2.1 判斷鏈表是否存在環(huán)形
// https://leetcode.com/problems/linked-list-cycle/
// 1. 暴力解法(brute force): 迭代節(jié)點(diǎn), 存儲(chǔ)或進(jìn)行標(biāo)記, 如果遇見(jiàn)已經(jīng)存在的記錄, 則說(shuō)明存在環(huán)形
// 2. 快慢雙指針(龜兔賽跑):
// slow速度為1, fast為2, 若fast遇見(jiàn)了slow(地球是圓的), 則說(shuō)明存在環(huán)形
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* 判斷鏈表是否存在環(huán)形
*
* @param {ListNode} head
* @return {boolean}
*/
const hasCycle = function (head) {
let slow = head,
fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true;
}
}
return false;
};
2.2 求兩個(gè)鏈表交集時(shí)的節(jié)點(diǎn)
// https://leetcode.com/problems/intersection-of-two-linked-lists/
// 1. 暴力解法(brute force): 使用數(shù)組或者set存儲(chǔ)一條鏈表所有節(jié)點(diǎn),然后迭代第二條鏈表進(jìn)行查找是否存在(略)
// 2. 雙指針 two pointers
// 兩個(gè)鏈表指針同時(shí)從各自表頭移動(dòng), 速度一致, 當(dāng)較短的鏈表(A)跑到頭后, 較長(zhǎng)的鏈表(B)就開(kāi)始順便重定向頭部指針,
// 此后B的前后兩個(gè)指針之差始終等于A的總長(zhǎng)度,
// 然后等到B的后指針也跑到頭后, 再同時(shí)從A和B的左側(cè)指針開(kāi)始迭代比較是否相等,找出交點(diǎn).
// Time complexity : O(m+n)O(m+n).
// Space complexity : O(1)O(1).
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* 求兩個(gè)鏈表交集時(shí)的節(jié)點(diǎn)
*
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode|null}
*/
const getIntersectionNode = function (headA, headB) {
let a = headA,
b = headB;
while (a !== null || b !== null) {
if (a !== null) {
a = a.next;
} else {
headB = headB.next;
}
if (b !== null) {
b = b.next;
} else {
headA = headA.next;
}
}
while (headA !== headB) {
headA = headA.next;
headB = headB.next;
}
return headA;
};
