JavaScript 中的計算機科學：鍊錶
這個帖子已經過時了。閱讀更新後的帖子。
當我開始編寫 Professional JavaScript 的第一版時 ，我的工作標題是 JavaScript for Web Applications 它包含了很多沒有進入最終剪輯版的內容。實際上，我的電腦上有幾章內容。其中幾章討論了在 JavaScript 中實現常見的計算機科學模式和算法。當時，我認為這會成為本書的一個很好的補充，但最終因為它們不符合本書的最終願景而最終阻止了他們。我決定開始在這個博客上分享，而不是讓這些內容放在我的電腦上。
您在計算機科學中學習的第一個數據結構是鍊錶。作為快速復習，這裡是鍊錶的 Wikipedia 描述：
鍊錶通常用於計算機科學程序中，以幫助引入指針的概念。列表本身只是一個指向頭節點的指針，頭節點又指向下一個節點，依此類推。每個節點由兩個字段組成：一個 data 包含列表中該位置的值和 next 的字段 包含指向列表中下一個節點的指針的字段（如果是最後一項，則為空指針）。
要開始 JavaScript 實現，請從創建單個節點開始。這可以通過使用對象字面量最輕鬆地完成：
var firstNode = {
data: 12,
next: null
};
當你想創建一個列表時，創建一個新節點並將它分配給這個節點的next 屬性：
//attach to first node to create list
firstNode.next = {
data: 99,
next: null
};
一旦有了列表，就可以按照next進行遍歷 每個節點上的屬性以到達列表中的特定點。當然，手動完成所有這些工作很煩人且容易出錯，因此最好創建自定義類型。開始吧：
function LinkedList() {
this._length = 0;
this._head = null;
}
LinkedList 構造函數創建一個具有“私有”屬性的對象：_length ，其中包含列表中的項目數，以及 _head ，它指向列表中的第一項。最初，_head 設置為 null 因為列表是空的。
將項目添加到鍊錶中需要遍歷結構以找到正確的位置，創建新節點並將其插入到位。一種特殊情況是列表為空時，在這種情況下，您只需創建一個新節點並將其分配給 _head ：
LinkedList.prototype = {
add: function (data){
//create a new node, place data in
var node = {
data: data,
next: null
},
//used to traverse the structure
current;
//special case: no items in the list yet
if (this._head === null){
this._head = node;
} else {
current = this._head;
while(current.next){
current = current.next;
}
current.next = node;
}
//don't forget to update the count
this._length++;
},
//more methods here
};
這種方法最複雜的部分是遍歷一個已經存在的列表來找到插入新節點的正確位置。傳統算法使用兩個指針，一個 current 指向被檢查的項目和一個 previous 指向 current 之前的節點 .當 current 是 null ，這意味著 previous 指向列表中的最後一項。我已經在 JavaScript 中重新創建了這個算法，儘管出於傳統考慮還有其他幾種（可以說更好）的替代方案。
從列表中檢索值涉及相同類型的遍歷：
LinkedList.prototype = {
//more methods
item: function(index){
//check for out-of-bounds values
if (index > -1 && index < this._length){
var current = this._head,
i = 0;
while(i++ < index){
current = current.next;
}
return current.data;
} else {
return null;
}
},
//more methods here
};
item() 方法檢查以確保在遍歷列表之前指定的索引在有效範圍內。 while 循環用於在列表中找出正確的停止位置以查找正在請求的數據。
從鍊錶中刪除一個節點有點棘手。你需要找到要移除的節點然後設置前一個節點的next 屬性到適當的下一個節點。這種對適當節點的“跳過”會導致它從列表中刪除。
鍊錶節點移除的典型實現是有兩個指針，一個current 指示正在檢查的節點的指針和 previous 指向 current 之前節點的指針 .當 current 是要移除的節點，然後是 previous.next 必須設置為 current.next 執行刪除。代碼：
LinkedList.prototype = {
//more methods
remove: function(index){
//check for out-of-bounds values
if (index > -1 && index < this._length){
var current = this._head,
previous,
i = 0;
//special case: removing first item
if (index === 0){
this._head = current.next;
} else {
//find the right location
while(i++ < index){
previous = current;
current = current.next;
}
//skip over the item to remove
previous.next = current.next;
}
//decrement the length
this._length--;
//return the value
return current.data;
} else {
return null;
}
},
//more methods here
};
請注意，一個特殊情況是刪除第一項。在這種情況下，您需要設置 _head 等於 _head.next ，將列表開頭的指針移動到下一項。
完成後，您可以像這樣使用鍊錶實現：
var list = new LinkedList();
list.add("red");
list.add("orange");
list.add("yellow");
alert(list.item(1)); //"orange"
list.remove(1);
alert(list.item(1)); //"yellow"
鍊錶的這個基本實現可以用 size() 返回列表長度和 toArray() 的方法 方法轉換為常規數組。完整的源代碼可在 GitHub 上我的 JavaScript 中的計算機科學項目中找到。我將在每篇博客文章中更新該項目，並希望建立一個很好的實現集合以供參考。需要明確的是，我不提倡在生產代碼中使用它；原生 Array object 很好地滿足了我們的所有需求。這純粹是一個學術練習，應該這樣對待。
