理解了鏈表是什麼之後，現在就要開始實現我們的數據結構了。以下是我們的LinkedList類的骨架：
function LinkedList {
let Node = function(element){ // {1}
this.element = element;
this.next = null;
};
let length = 0; // {2}
let head = null; // {3}
this.append = function(element){};
this.insert = function(position, element){};
this.removeAt = function(position){};
this.remove = function(element){};
this.indexOf = function(element){};
this.isEmpty = function {};
this.size = function {};
this.getHead = function{};
this.toString = function{};
this.print = function{};
}
LinkedList數據結構還需要一個Node輔助類（行{1}）。Node類表示要加入列表的項。它包含一個element屬性，即要添加到列表的值，以及一個next屬性，即指向列表中下一個節點項的指針。
LinkedList類也有存儲列表項的數量的length屬性（內部/私有變量）（行{2}）。
另一個重要的點是，我們還需要存儲第一個節點的引用。為此，可以把這個引用存儲在一個稱為head的變量中（行{3}）。
然後就是LinkedList類的方法。在實現這些方法之前，先來看看它們的職責。
append(element)：向列表尾部添加一個新的項。insert(position, element)：向列表的特定位置插入一個新的項。remove(element)：從列表中移除一項。indexOf(element)：返回元素在列表中的索引。如果列表中沒有該元素則返回-1。removeAt(position)：從列表的特定位置移除一項。isEmpty：如果鏈表中不包含任何元素，返回true，如果鏈表長度大於0則返回false。size：返回鏈表包含的元素個數。與數組的length屬性類似。toString：由於列表項使用了Node類，就需要重寫繼承自JavaScript對像默認的toString方法，讓其只輸出元素的值。
5.2.1 向鏈表尾部追加元素
向LinkedList對像尾部添加一個元素時，可能有兩種場景：列表為空，添加的是第一個元素，或者列表不為空，向其追加元素。
下面是我們實現的append方法：
this.append = function(element){
let node = new Node(element), //{1}
current; //{2}
if (head === null){ //列表中第一個節點 //{3}
head = node;
} else {
current = head; //{4}
//循環列表，直到找到最後一項
while(current.next){
current = current.next;
}
//找到最後一項，將其next賦為node，建立鏈接
current.next = node; //{5}
}
length++; //更新列表的長度 //{6}
};
首先需要做的是把element作為值傳入，創建Node項（行{1}）。
先來實現第一個場景：向為空的列表添加一個元素。當我們創建一個LinkedList對像時，head會指向null：
如果head元素為null（列表為空——行{3}），就意味著在向列表添加第一個元素。因此要做的就是讓head元素指向node元素。下一個node元素將會自動成為null（請看5.1節的源代碼）。
列表最後一個節點的下一個元素始終是
null。
好了，我們已經說完了第一種場景。再來看看第二個，也就是向一個不為空的列表尾部添加元素。
要向列表的尾部添加一個元素，首先需要找到最後一個元素。記住，我們只有第一個元素的引用（行{4}），因此需要循環訪問列表，直到找到最後一項。為此，我們需要一個指向列表中current項的變量（行{2}）。
循環訪問列表時，當current.next元素為null時，我們就知道已經到達列表尾部了。然後要做的就是讓當前（也就是最後一個）元素的next指針指向想要添加到列表的節點（行{5}）。下圖展示了這個行為：
而當一個Node元素被創建時，它的next指針總是null。這沒問題，因為我們知道它會是列表的最後一項。
當然，別忘了遞增列表的長度，這樣就能控制它，輕鬆地得到列表的長度（行{6}）。
我們可以通過以下代碼來使用和測試目前創建的數據結構：
let list = new LinkedList;
list.append(15);
list.append(10);
5.2.2 從鏈表中移除元素
現在，讓我們看看如何從LinkedList對像中移除元素。移除元素也有兩種場景：第一種是移除第一個元素，第二種是移除第一個以外的任一元素。我們要實現兩種remove方法：第一種是從特定位置移除一個元素，第二種是根據元素的值移除元素（稍後我們會展示第二種remove方法）。
this.removeAt = function(position){
//檢查越界值
if (position > -1 && position < length){ // {1}
let current = head, // {2}
previous, // {3}
index = 0; // {4}
//移除第一項
if (position === 0){ // {5}
head = current.next;
} else {
while (index++ < position){ // {6}
previous = current; // {7}
current = current.next; // {8}
}
//將previous與current的下一項鏈接起來：跳過current，從而移除它
previous.next = current.next; // {9}
}
length--; // {10}
return current.element;
} else {
return null; // {11}
}
};
一步一步來看這段代碼。該方法要得到需要移除的元素的位置，就需要驗證這個位置是有效的（行{1}）。從0（包括0）到列表的長度（size - 1，因為索引是從零開始的）都是有效的位置。如果不是有效的位置，就返回null（意即沒有從列表中移除元素）。
一起來為第一種場景編寫代碼：我們要從列表中移除第一個元素（position === 0——行{5}）。下圖展示了這個過程：
因此，如果想移除第一個元素，要做的就是讓head指向列表的第二個元素。我們將用current變量創建一個對列表中第一個元素的引用（行{2}——我們還會用它來迭代列表，但稍等一下再說）。這樣current變量就是對列表中第一個元素的引用。如果把head賦為current.next，就會移除第一個元素。
現在，假設我們要移除列表的最後一項或者中間某一項。為此，需要依靠一個細節來迭代列表，直到到達目標位置（行{6}——我們會使用一個用於內部控制和遞增的index變量）：current變量總是為對所循環列表的當前元素的引用（行{8}）。我們還需要一個對當前元素的前一個元素的引用（行{7}）；它被命名為previous（行{3}）。
因此，要從列表中移除當前元素，要做的就是將previous.next和current.next鏈接起來（行{9}）。這樣，當前元素就會被丟棄在計算機內存中，等著被垃圾回收器清除。
我們試著通過一些圖表來更好地理解。首先考慮移除最後一個元素：
對於最後一個元素，當我們在行{6}跳出循環時，current變量將是對列表中最後一個元素的引用（要移除的元素）。current.next的值將是null（因為它是最後一個元素）。由於還保留了對previous元素的引用（當前元素的前一個元素），previous.next就指向了current。那麼要移除current，要做的就是把previous.next的值改變為current.next。
現在來看看，對於列表中間的元素是否可以應用相同的邏輯：
current變量是對要移除元素的引用。previous變量是對要移除元素的前一個元素的引用。那麼要移除current元素，需要做的就是將previous.next與current.next鏈接起來。因此，我們的邏輯對這兩種情況都管用。
5.2.3 在任意位置插入元素
接下來，我們要實現insert方法。使用這個方法可以在任意位置插入一個元素。我們來看一看它的實現：
this.insert = function(position, element){
//檢查越界值
if (position >= 0 && position <= length){ //{1}
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){ //在第一個位置添加
node.next = current; //{2}
head = node;
} else {
while (index++ < position){ //{3}
previous = current;
current = current.next;
}
node.next = current; //{4}
previous.next = node; //{5}
}
length++; //更新列表的長度
return true;
} else {
return false; //{6}
}
};
由於我們處理的是位置，就需要檢查越界值（行{1}，跟remove方法類似）。如果越界了，就返回false值，表示沒有添加項到列表中（行{6}）。
現在我們要處理不同的場景。第一種場景，需要在列表的起點添加一個元素，也就是第一個位置。下圖展示了這種場景：
current變量是對列表中第一個元素的引用。我們需要做的是把node.next的值設為current（列表中第一個元素）。現在head和node.next都指向了current。接下來要做的就是把head的引用改為node（行{2}），這樣列表中就有了一個新元素。
現在來處理第二種場景：在列表中間或尾部添加一個元素。首先，我們需要循環訪問列表，找到目標位置（行{3}）。當跳出循環時，current變量將是對想要插入新元素的位置之後一個元素的引用，而previous將是對想要插入新元素的位置之前一個元素的引用。在這種情況下，我們要在previous和current之間添加新項。因此，首先需要把新項（node）和當前項鏈接起來（行{4}），然後需要改變previous和current之間的鏈接。我們還需要讓previous.next指向node（行{5}）。
我們通過一張圖表來看看代碼所做的事：
如果我們試圖向最後一個位置添加一個新元素，previous將是對列表最後一項的引用，而current將是null。在這種情況下，node.next將指向current，而previous.next將指向node，這樣列表中就有了一個新的項。
現在來看看如何向列表中間添加一個新元素：
在這種情況下，我們試圖將新的項（node）插入到previous和current元素之間。首先，我們需要把node.next的值指向current。然後把previous.next的值設為node。這樣列表中就有了一個新的項。
使用變量引用我們需要控制的節點非常重要，這樣就不會丟失節點之間的鏈接。我們可以只使用一個變量（
previous），但那樣會很難控制節點之間的鏈接。由於這個原因，最好是聲明一個額外的變量來幫助我們處理這些引用。
5.2.4 實現其他方法
在這一節中，我們將會學習如何實現toString、indexOf、isEmpty和size等其他LinkedList類的方法。
toString方法toString方法會把LinkedList對像轉換成一個字符串。下面是toString方法的實現：this.toString = function{ let current = head, //{1} string = \'\'; //{2} while (current) { //{3} string +=current.element +(current.next ? \'n\' : \'\');//{4} current = current.next; //{5} } return string; //{6} };首先，要循環訪問列表中的所有元素，就需要有一個起點，也就是
head。我們會把current變量當作索引（行{1}），控制循環訪問列表。我們還需要初始化用於拼接元素值的變量（行{2}）。接下來就是循環訪問列表中的每個元素（行
{3}）。我們要用current來檢查元素是否存在（如果列表為空，或是到達列表中最後一個元素的下一位（null），while循環中的代碼就不會執行）。然後我們就得到了元素的內容，將其拼接到字符串中（行{4}）。最後，繼續迭代下一個元素（行{5}）。最後，返回列表內容的字符串（行{6}）。indexOf方法indexOf是我們下一個要實現的方法。indexOf方法接收一個元素的值，如果在列表中找到它，就返回元素的位置，否則返回-1。來看看它的實現：
this.indexOf = function(element){ let current = head, //{1} index = -1; while (current) { //{2} if (element === current.element) { return index; //{3} } index++; //{4} current = current.next; //{5} } return -1; };一如既往，我們需要一個變量來幫助我們循環訪問列表，這個變量是
current，它的初始值是head（列表的第一個元素——我們還需要一個index變量來計算位置數（行{1}））。然後循環訪問元素（行{2}），檢查當前元素是否是我們要找的。如果是，就返回它的位置（行{3}）；如果不是，就繼續計數（行{4}），檢查列表中下一個節點（行{5}）。如果列表為空，或是到達列表的尾部（
current = current.next將是null），循環就不會執行。如果沒有找到值，就返回-1。實現了這個方法，我們就可以實現
remove等其他的方法：this.remove = function(element){ let index = this.indexOf(element); return this.removeAt(index); };我們已經有一個移除給定位置的一個元素的
removeAt方法了。現在有了indexOf方法，如果傳入元素的值，就能找到它的位置，然後調用removeAt方法並傳入找到的位置。這樣非常簡單，如果需要更改removeAt方法的代碼，這樣也更容易——兩個方法都會被更改（這就是重用代碼的妙處）。這樣，我們就不需要維護兩個從列表中移除一項的方法，只需要一個！同時，removeAt方法將會檢查邊界約束。isEmpty、size和getHead方法isEmpty和size方法跟我們在上一章實現的一模一樣。但我們還是來看一下：this.isEmpty = function { return length === 0; };如果列表中沒有元素，
isEmpty方法就返回true，否則返回false。this.size = function { return length; };size方法返回列表的length。和我們之前幾章實現的類有所不同，列表的length是內部控制的，因為LinkedList是從頭構建的。最後還有
getHead方法：this.getHead = function{ return head; };head變量是LinkedList類的私有變量（這意味著它不能在LinkedList實例外部被訪問和更改，只有通過LinkedList實例才可以）。但是，如果我們需要在類的實現外部循環訪問列表，就需要提供一種獲取類的第一個元素的方法。