數據結構淺析：鏈表
你有修建過戈德堡機械嗎承璃？如果沒有，也許應該修建過精心構建的多米諾骨牌線蚌本？
好的盔粹，也許你的童年應該不像我一樣書呆子。就這樣吧程癌，對于玩過上述兩者中任意一樣的人玻佩，你已經掌握了今天數據結構的本質：鏈表！
鏈表是怎么工作的
鏈表的最簡單實現形式—單鏈表--是一系列的節(jié)點席楚，每一個單獨的節(jié)點都包含一個值和一個指向鏈表中下一個節(jié)點的指針咬崔。
添加（Add）通過在表的尾部添加一個項目增加列表的大小。
移除（Remove）通常移除鏈表中指定位置的元素烦秩。
搜索（Contains）將在列表中搜索一個指定的值垮斯。
使用例子：
哈希表中為了防止出現沖突，將 values 存儲在一個列表中
-
重拍極速前進（The Amazing Race）
?
為了讓這篇文章保持輕松友好一些只祠，我們一起來創(chuàng)建一個 CBS 可用于計劃其下一季“極速前進”真人秀拍攝的工具兜蠕。
在閱讀本文時，我希望你能夠一直問自己：“鏈表和數組有什么區(qū)別抛寝？它們有什么相似之處熊杨？”
我們開始吧。
首先盗舰，你需要創(chuàng)建一個鏈表：
class LinkedList{
constructor(){
this._head = null;
this._tail = null;
this._length = 0;
}
size(){
return this._length;
}
}
為了跟蹤比賽的起點和終點晶府，需要創(chuàng)建 head 和 tail 屬性。
然后钻趋，為了保證賽程不要太長或者太短川陆，需要創(chuàng)建 length 屬性和 size 方法。這樣你就總是可以精確的掌握賽程的長度蛮位。
現在你有了一種存儲數據的方法较沪，你應該創(chuàng)建一個往列表添加數據的方法。問題是失仁，你要添加什么數據呢尸曼？
記住，鏈表是一系列的節(jié)點萄焦，每一個節(jié)點都有一個值和指向列表中下一個節(jié)點的指針控轿。了解了這一點，你會意識到節(jié)點就是一個存儲有 value 和 next 兩個屬性的對象。
由于每一次往列表添加數據都需要創(chuàng)建一個新的節(jié)點解幽，你決定創(chuàng)建一個構造函數，這樣每次往列表添加數據時創(chuàng)建節(jié)點會更簡單一些烘苹。
class Node{
constructor(value){
this.value = value;
this.next = null;
}
}
有了構造函數躲株，就可以創(chuàng)建 add 方法。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value); //we create our node
if(!this._head && !this._tail){ //If it's the first node
this._head = node; //1st node is head & tail
this._tail = node;
}else{
this._tail.next = node; //add node to the back
this._tail = this._tail.next; //reset tail to last node
}
this._length++;
}
size() {
return this._length;
}
}
const AmazingRace = new LinkedList();
AmazingRace.add("Colombo, Sri Lanka");
AmazingRace.add("Lagos, Nigeria");
AmazingRace.add("Surat, India");
AmazingRace.add("Suzhou, China");
現在你已經添加了這個方法镣衡，你可以往 “AmazingRace” 列表中添加一堆比賽地點霜定。看起來像這樣廊鸥。注意為了更容易理解我添加了一些額外的空格望浩。
{ _head:
{ value: 'Colombo, Sri Lanka',
next: { value: 'Lagos, Nigeria',
next: { value: 'Surat, India',
next: { value: 'Suzhou, China',
next: null
}
}
}
},
_tail: { value: 'Suzhou, China', next: null },
_length: 4
}
好啦，現在已經創(chuàng)建了列表以及添加內容的方法惰说，你意識到往列表中添加地點還需要一些方法磨德。
你決定將這個鏈表共享給合作者，Kent吆视，要求他往里面添加更多的比賽地點典挑。唯一的問題是，當你將列表給他時啦吧，沒有告訴他你已經添加了哪些地點您觉。不幸的是你也忘記了。
當然他可以通過運行 console.log(AmazingRace) 然后逐一檢查其輸出授滓。但是 Kent 是一個懶人琳水，他需要一種方式來確認某些值是否已經存在列表中，從而避免重復添加般堆≡谛ⅲ考慮到這一點，你創(chuàng)建了 contains 方法來檢查是否包含某些值淮摔。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value);
if(!this._head && !this._tail){
this._head = node;
this._tail = this._head;
}else{
this._tail.next = node;
this._tail = this._tail.next;
}
this._length++;
}
contains(value){
let node = this._head;
while(node){
if(node.value === value){
return true;
}
node = node.next;
}
return false;
}
size() {
return this._length;
}
}
const AmazingRace = new LinkedList();
AmazingRace.add("Colombo, Sri Lanka");
AmazingRace.add("Lagos, Nigeria");
AmazingRace.add("Surat, India");
AmazingRace.add("Suzhou, China");
//Kent's check
AmazingRace.contains('Suzhou, China'); //true
AmazingRace.contains('Hanoi, Vietnam'); //false
AmazingRace.add('Hanoi, Vietnam');
AmazingRace.contains('Seattle, Washington'); //false
AmazingRace.add('Seattle, Washington');
AmazingRace.contains('North Pole'); // false
AmazingRace.add('North Pole');
很棒浑玛，現在 Kent 為了避免重復，他可以在添加之前檢查一下是否已經存在噩咪。
另一方面顾彰，你可能會想為什么不在添加之前進行檢查從而避免重復呢？當你在實現一個鏈表—或者任意的數據結構時— 理論上你可以添加任何額外你想要的功能胃碾。
你甚至可以改變已有數據結構中原來的方法涨享。在 REPL 中試一下以下代碼：
Array.prototype.push = () => {
return 'cat';
}
let arr = [];
arr.push('eggs'); // returns 'cat';
我們沒有做這些事情的原因是因為約定的標準∑桶伲基本上厕隧，開發(fā)者對特定的方法應該如何工作是有預期的。
盡管我們的鏈表不是 JavaScript 的原生庫，我們在實現它時擁有更多的自由吁讨，但是這些數據結構如何運作我們仍有基本的期望髓迎。鏈表本身并不保證存儲的值唯一。但是它們確實可以提供 contains 這樣的方法允許我們進行預檢建丧，從而維護我們列表中的值不重復排龄。
Kent 將他修改后的列表再發(fā)給你，但是其中一些可能有問題翎朱。比如北極可能不是“極速前進”最好的終點橄维。
所以你決定創(chuàng)建一個可以移除某些節(jié)點的方法。一定要記住的是拴曲，一旦你刪除了某一個節(jié)點争舞，你就打斷了列表，你需要將被刪除節(jié)點的前后兩個節(jié)點重新連接起來澈灼。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value);
if(!this._head && !this._tail){
this._head = node;
this._tail = this._head;
}else{
this._tail.next = node;
this._tail = this._tail.next;
}
this._length++;
}
remove(value) {
if(this.contains(value)){ // see if our value exists
let current = this._head; // begin at start of list
let previous = this._head;
while(current){ // check each node
if(current.value === value){
if(this._head === current){ // if it's the head
this._head = this._head.next; // reset the head
this._length--; // update the length
return; // break out of the loop
}
if(this._tail === current){ // if it's the tail node
this._tail = previous; // make sure to reset it
}
previous.next = current.next; // unlink (see img below)
this._length--; // update the length
return; // break out of
}
previous = current; // look at the next node
current = current.next; // ^^
}
}
}
contains(value){
let node = this._head;
while(node){
if(node.value === value){
return true;
}
node = node.next;
}
return false;
}
size() {
return this._length;
}
}
const AmazingRace = new LinkedList();
AmazingRace.add("Colombo, Sri Lanka");
AmazingRace.add("Lagos, Nigeria");
AmazingRace.add("Surat, India");
AmazingRace.add("Suzhou, China");
AmazingRace.add('Hanoi, Vietnam');
AmazingRace.add('Seattle, Washington');
AmazingRace.add('North Pole');
//Kent's check
AmazingRace.remove('North Pole');
remove 方法的代碼比較長竞川。本質上它按照如下步驟運行：
1、檢查待刪除的值是否存在叁熔。流译。。
2者疤、遍歷列表福澡，并且需要跟蹤當前節(jié)點和上一個節(jié)點
3、然后驹马，如果當前節(jié)點就是要刪除的點—>
4A革砸、當前節(jié)點是鏈表的頭
- 將鏈表的頭重置為列表中的下一個節(jié)點
- 更新鏈表長度
- 跳出循環(huán)
4B、當前節(jié)點是鏈表的尾 - 將鏈表的尾設置為鏈表中的上一個節(jié)點
- 按照下圖的方式重新連接節(jié)點
-
4C糯累、如果不是要刪除的節(jié)點—>繼續(xù)迭代
- 將下一個節(jié)點設置為當前節(jié)點
- 將當前節(jié)點設置為上一個節(jié)點
最后要說說明的一件事：你可能已經注意到你并沒有真正的刪除那個節(jié)點算利。你只是移除了對它的引用。對泳姐，這樣就可以了效拭，因為一旦對一個對象的所有引用都被移除以后，垃圾回收器會幫助我們將它從內存中移除的胖秒。更多關于垃圾回收的信息參考這里
有了你剛才實現的 remove 方法缎患，你只需下面這一行就可以保證參賽者不會凍死、或者打擾在正在準備新年慶典的圣誕老人阎肝。
AmazingRace.remove('North Pole');
好了挤渔，你已經完成了一個單鏈表的簡單實現。你可通過添加元素來擴充列表风题，也可以通過移除元素來壓縮列表判导。
如果你想在鏈表的首部嫉父、尾部或者任意節(jié)點后插入元素。你需要自己實現這些方法眼刃。這些方法的名稱和參數應該類似這樣：
addHead(value) {
}
insertAfter(target, value){
}
時間復雜度分析
再來看一下完整的代碼
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value);
if(!this._head && !this._tail){
this._head = node;
this._tail = this._head;
}else{
this._tail.next = node;
this._tail = this._tail.next;
}
this._length++;
}
remove(value) {
if(this.contains(value)){
let current = this._head;
let previous = this._head;
while(current){
if(current.value === value){
if(this._head === current){
this._head = this._head.next;
this._length--;
return;
}
if(this._tail === current){
this._tail = previous;
}
previous.next = current.next;
this._length--;
return;
}
previous = current;
current = current.next;
}
}
}
contains(value){
let node = this._head;
while(node){
if(node.value === value){
return true;
}
node = node.next;
}
return false;
}
size() {
return this._length;
}
// To Be Implemented
addHead(value) {
}
insertAfter(target, value){
}
Add 的復雜度是O(1)：因為有 tail 屬性跟蹤隊列的尾部绕辖，所以你不必遍歷整個列表。
Remove 的復雜度是 O(n)： 最壞的情況下擂红，你需要遍歷完整個列表才能找到你需要移除的節(jié)點仪际。盡管真正的移除節(jié)點的操作是 O(1)（因為你只需要重置一下指針就可以）。
Contains 的復雜度是 O(n)：為了確認列表中是否包含指定的值篮条，你必須遍歷整個列表。
addHead 的復雜度是 O(1)：和我們的 add 方法相似吩抓，我們總是知道列表的頭部涉茧，所以不需要遍歷。
insertAfter 的復雜度是 O(n)：和上面討論的 Remove 方法一樣疹娶，你需要遍歷整個列表找到你需要插入的位置伴栓。同樣的，實際的插入操作復雜度為 O(1) 雨饺。
鏈表 VS 數組
為什么要使用鏈表而不是數組钳垮？技術上數組可以運行所有鏈表操作，如 添加额港、插入饺窿、刪除。此外移斩， JavaScript 中數組已經具備這些方法肚医。
最大的差別來自插入和刪除。因為數組是基于索引向瓷，當你在數組的中間插入或者刪除元素時肠套，你需要將其后面所有的元素重置到新的索引位置。
想象一下猖任，在一個有 100,000 個元素的頭部或者中間插入一個元素你稚！像這樣的插入和刪除操作是非常耗費資源的。因為這一點朱躺，鏈表通常用于常常被移動的大型數據集刁赖。
另一方面，數組在查找方面非常出色长搀，因為它是基于索引的痒给。如果你知道元素的位置，你可以通過 array[position] 在 O(1) 時間內查找到該元素戚篙。
鏈表通常需要順序遍歷列表撒汉〗文疲基于這一原因，數組常常用于小一些的數據集或者不常移動的數據集病苗。
小節(jié)
鏈表：
- 1疗垛、有 tail 和 head 屬性用于跟蹤鏈表的兩端
- 2、有 add硫朦， addHead贷腕，insertAfter 和 remove 方法用于管理列表內容
- 3、有 length 屬性用過跟蹤列表長度
本文譯自 ：A Gentle Introduction to Data Structures: How Linked Lists Work
