我們要存儲(chǔ)一個(gè)有序的對(duì)象列表，正常的選擇會(huì)是一個(gè)數(shù)組：

let arr = [obj 1, obj 2, obj 3]

但是用數(shù)據(jù)有個(gè)問題。"刪除元素"和"插入元素"的操作代價(jià)很大，arr.unshift(obj)操作必須對(duì)所有元素重新編號(hào)以便為新的元素ojb出空間，如果數(shù)組很大，會(huì)耗費(fèi)大量時(shí)間。此時(shí)我們可以選擇另一種叫做鏈表的數(shù)據(jù)結(jié)構(gòu)。

鏈表元素?是一個(gè)使用以下元素通過遞歸定義的對(duì)象：

let list = {

? ? value: 1,

? ? next: {

? ? ? ? value: 2,

? ? ? ? next: {

? ? ? ? ? ? value: 3

? ? ? ? ? ? next: null

????????}

????}

}

注：value為當(dāng)前鏈表元素的值，next屬性引用下一個(gè)鏈表元素或者代表末尾的null。

一段用來創(chuàng)建鏈表的代碼：

let list = { value: 1 };

list.next = { value: 2 };

list.next.next = { value: 3 };

list.next.next.next = null;

從上面的代碼我們可以清楚地看到，這里有很多個(gè)對(duì)象，每一個(gè)都有value和指向鄰居的next。變量list是鏈表中的第一個(gè)對(duì)象，因此順著next指針，我們可以抵達(dá)任何元素。

比如，將新值添加到鏈表頭部

list = { value: "new item", next: list }

要從中間刪除一個(gè)值，可以修改前一個(gè)元素的next：

list.next = list.next.next

我們讓?list.next?從?1?跳到值?2?，F(xiàn)在值?1?就被從鏈表中移除了。如果它沒有被存儲(chǔ)在其它任何地方，那么它會(huì)被自動(dòng)從內(nèi)存中刪除。

鏈表和數(shù)組對(duì)比

與數(shù)組不同，鏈表沒有大規(guī)模重排，我們可以很容易地重新排列元素。鏈表主要的缺點(diǎn)就是我們無法很容易地通過元素的編號(hào)獲取元素。但在數(shù)組中卻很容易：arr[n]?是一個(gè)直接引用。而在鏈表中，我們需要從起點(diǎn)元素開始，順著?next?找?N?次才能獲取到第 N 個(gè)元素。