我們要存儲(chǔ)一個(gè)有序的對象列表，正常的選擇會(huì)是一個(gè)數(shù)組：
let arr = [obj 1, obj 2, obj 3]
但是用數(shù)據(jù)有個(gè)問題擎宝。"刪除元素"和"插入元素"的操作代價(jià)很大郁妈，arr.unshift(obj)操作必須對所有元素重新編號以便為新的元素ojb出空間，如果數(shù)組很大绍申，會(huì)耗費(fèi)大量時(shí)間噩咪。此時(shí)我們可以選擇另一種叫做鏈表的數(shù)據(jù)結(jié)構(gòu)。
鏈表元素?是一個(gè)使用以下元素通過遞歸定義的對象：
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è)對象筋搏，每一個(gè)都有value和指向鄰居的next仆百。變量list是鏈表中的第一個(gè)對象，因此順著next指針拆又，我們可以抵達(dá)任何元素儒旬。
比如，將新值添加到鏈表頭部
list = { value: "new item", next: list }
要從中間刪除一個(gè)值帖族，可以修改前一個(gè)元素的next：
list.next = list.next.next
我們讓?list.next?從?1?跳到值?2≌辉矗現(xiàn)在值?1?就被從鏈表中移除了。如果它沒有被存儲(chǔ)在其它任何地方竖般，那么它會(huì)被自動(dòng)從內(nèi)存中刪除甚垦。
鏈表和數(shù)組對比
與數(shù)組不同，鏈表沒有大規(guī)模重排，我們可以很容易地重新排列元素艰亮。鏈表主要的缺點(diǎn)就是我們無法很容易地通過元素的編號獲取元素闭翩。但在數(shù)組中卻很容易：arr[n]?是一個(gè)直接引用。而在鏈表中迄埃，我們需要從起點(diǎn)元素開始疗韵，順著?next?找?N?次才能獲取到第 N 個(gè)元素。
