链表list(链式存储结构实现)_数据结构知否知否系列之 — 线性表的顺序与链式存储篇（8000 多字长文）...
線性表是由 n 個(gè)數(shù)據(jù)元素組成的有限序列，也是最基本、最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。
作者簡(jiǎn)介：五月君，Nodejs Developer，熱愛(ài)技術(shù)、喜歡分享的 90 后青年，公眾號(hào)「Nodejs技術(shù)棧」，Github 開(kāi)源項(xiàng)目 https://www.nodejs.red
前言
本篇文章歷時(shí)一周多，差不多花費(fèi)了兩個(gè)周末的時(shí)間，在書(shū)寫的過(guò)程中更多的還是在思考每一種線性表的算法實(shí)現(xiàn)，鏈表的指針域部分對(duì)于不理解指針或者對(duì)象引用的童鞋，在閱讀代碼的時(shí)候可能會(huì)蒙蒙的，本篇文章代碼部分采用的 JavaScript 編程語(yǔ)言，但是實(shí)現(xiàn)思想是相通的，如果你用 Java、Python 等也可做參考，如文章有理解錯(cuò)誤之處歡迎在下方評(píng)論區(qū)指正。
認(rèn)識(shí)線性表
根據(jù)線性表的定義，可得出幾個(gè)關(guān)鍵詞：n 個(gè)數(shù)據(jù)元素、有限序列，也就是說(shuō)它是有長(zhǎng)度限制的且元素之間是有序的，在多個(gè)元素之間，第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼，中間元素有且只有一個(gè)前驅(qū)和后繼。
舉一個(gè)與大家都息息相關(guān)的十二生肖例子，以“子（鼠）” 開(kāi)頭，“亥（豬）”結(jié)尾，其中間的每個(gè)生肖也都有其前驅(qū)和后繼，圖例如下所示：
下面再介紹一個(gè)復(fù)雜的線性表，其一個(gè)元素由多個(gè)數(shù)據(jù)項(xiàng)構(gòu)成，例如，我們的班級(jí)名單，含學(xué)生的學(xué)號(hào)、姓名、年齡、性別等信息，圖例如下所示：
線性表兩種存儲(chǔ)結(jié)構(gòu)
線性表有兩種存儲(chǔ)結(jié)構(gòu)，一種為順序結(jié)構(gòu)存儲(chǔ)，稱為順序表；另一種為鏈?zhǔn)叫问酱鎯?chǔ)，稱為鏈表，鏈表根據(jù)指針域的不同，鏈表分為單向鏈表、雙向鏈表、循環(huán)鏈表等。詳細(xì)的內(nèi)容會(huì)在后面展開(kāi)講解。
順序表
順序表是在計(jì)算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)。
在線性表里順序表相對(duì)更容易些，因此也先從順序表講起，通過(guò)實(shí)現(xiàn)編碼的方式帶著大家從零開(kāi)始實(shí)現(xiàn)一個(gè)順序表，網(wǎng)上很多教程大多都是以 C 語(yǔ)言為例子，其實(shí)現(xiàn)思想都是相通的，這里采用 JavaScript 編碼實(shí)現(xiàn)。
實(shí)現(xiàn)步驟
初始化順序表空間
在構(gòu)造函數(shù)的 constructor 里進(jìn)行聲明，傳入 capacity 初始化順序表空間同時(shí)初始化順序表的元素長(zhǎng)度（length）為 0。
/**順序表是否為空檢查
定義 isEmpty() 方法返回順序表是否為空，根據(jù) length 順序表元素進(jìn)行判斷。
isEmpty順序表是否溢出檢查
定義 isOverflow() 方法返回順序表空間是否溢出，根據(jù)順序表元素長(zhǎng)度和初始化的空間容量進(jìn)行判斷。
isOverflow查找指定位置元素
返回順序表中第 i 個(gè)數(shù)據(jù)元素的值
getElement查找元素的第一個(gè)位置索引
返回順序表中第 1 個(gè)與 e 滿足關(guān)系的元素，存在則返回其索引值；不存在，則返回值為 -1
locateElement在順序表中返回指定元素的前驅(qū)
這里就用到了上面定義的 locateElement 函數(shù)，先找到元素對(duì)應(yīng)的索引位置，如果前驅(qū)就取前一個(gè)位置，后繼就取后一個(gè)位置，在這之前先校驗(yàn)當(dāng)前元素的索引位置是否存在合法。
priorElement在順序表中返回指定元素的后繼
nextElement插入元素
在順序表中第 i 個(gè)位置之前插入新的數(shù)據(jù)元素 e，在插入之前先進(jìn)行元素位置后移，插入之后順序表元素的長(zhǎng)度要加 1。
舉個(gè)例子，我們?nèi)セ疖囌救∑?#xff0c;恰逢人多大家都在排隊(duì)，突然來(lái)一個(gè)美女或者帥哥對(duì)你說(shuō)我的車次馬上要開(kāi)車了，你可能同意了，此時(shí)你的位置及你后面的童鞋就要后移一位了，也許你會(huì)聽(tīng)到一些聲音，怎么回事呀？怎么插隊(duì)了呀，其實(shí)后面的人有的也不清楚什么原因 “233”，看一個(gè)圖
算法實(shí)現(xiàn)如下：
listInsert刪除元素
刪除順序表的第 i 個(gè)數(shù)據(jù)元素，并返回其值，與插入相反，需要將刪除位置之后的元素進(jìn)行前移，最后將順序表元素長(zhǎng)度減 1。
同樣以火車站取票的例子說(shuō)明，如果大家都正在排隊(duì)取票，突然你前面一個(gè)妹子有急事臨時(shí)走了，那么你及你后面的童鞋就要前進(jìn)一步，圖例如下所示：
算法實(shí)現(xiàn)如下：
listDelete清除順序表元素
這里有幾種實(shí)現(xiàn)，你也可以把順序表的空間進(jìn)行初始化，或者把 length 棧位置設(shè)為 0 也可。
clear順序表銷毀
在一些高級(jí)語(yǔ)言中都會(huì)有垃圾回收機(jī)制，例如 JS 中只要當(dāng)前對(duì)象不再持有引用，下次垃圾回收來(lái)臨時(shí)將會(huì)被回收。不清楚的可以看看我之前寫的 Node.js 內(nèi)存管理和 V8 垃圾回收機(jī)制
destroy順序表元素遍歷
定義 traversing() 方法對(duì)順序表的元素進(jìn)行遍歷輸出。
traversing做一些測(cè)試
做下測(cè)試分別看下插入、刪除、遍歷等操作，其它的功能大家在練習(xí)的過(guò)程中可自行實(shí)踐。
const順序表的運(yùn)行機(jī)制源碼地址如下：
https://github.com/Q-Angelo/project-training/tree/master/algorithm/sequence-table.js順序表優(yōu)缺點(diǎn)總結(jié)
插入、刪除元素如果是在最后一個(gè)位置時(shí)間復(fù)雜度為 O(1)，如果是在第一個(gè)（或其它非最后一個(gè)）位置，此時(shí)時(shí)間復(fù)雜度為 O(1)，就要移動(dòng)所有的元素向后或向前，時(shí)間復(fù)雜度為 O(n)，當(dāng)順序表的長(zhǎng)度越大，插入和刪除操作可能就需要大量的移動(dòng)操作。
對(duì)于存取操作，可以快速存取順序表中任意位置元素，時(shí)間復(fù)雜度為 O(1)。
鏈表
鏈表（Linked list）是一種常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是鏈表查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。
使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了節(jié)的指針域，空間開(kāi)銷比較大。
單向鏈表
鏈表中最簡(jiǎn)單的一種是單向鏈表，它包含兩個(gè)域，一個(gè)信息域和一個(gè)指針域。這個(gè)鏈接指向列表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)則指向一個(gè)空值，圖例如下：
除了單向鏈表之外還有雙向鏈表、循環(huán)鏈表，在學(xué)習(xí)這些之前先從單向鏈表開(kāi)始，因此，這里會(huì)完整講解單向鏈表的實(shí)現(xiàn)，其它的幾種后續(xù)都會(huì)在這個(gè)基礎(chǔ)之上進(jìn)行改造。
單向鏈表實(shí)現(xiàn)步驟
初始化鏈表
在構(gòu)造函數(shù)的 constructor 里進(jìn)行聲明，無(wú)需傳入?yún)?shù)，分別對(duì)以下幾個(gè)屬性和方法做了聲明：
- node: 定義 node 方法，它包含一個(gè) element 屬性，即添加到列表的值，及另一個(gè) next 屬性，指向列表中下一個(gè)節(jié)點(diǎn)項(xiàng)的指針
- length: 鏈表元素長(zhǎng)度
- head: 在 head 變量中存儲(chǔ)第一個(gè)節(jié)點(diǎn)的引用
當(dāng)我們實(shí)例化一個(gè) SingleList 對(duì)象時(shí) head 指向?yàn)?null 及 length 默認(rèn)等于 0，代碼示例如下：
class鏈表是否為空檢查
定義 isEmpty() 方法返回鏈表是否為空，根據(jù)鏈表的 length 進(jìn)行判斷。
isEmpty返回鏈表長(zhǎng)度
同樣使用鏈表的 length 即可
length鏈表尾部插入元素
鏈表 SingleList 尾部增加元素，需要考慮兩種情況：一種是鏈表（head）為空，直接賦值添加第一個(gè)元素，另一種情況就是鏈表不為空，找到鏈表最后一個(gè)節(jié)點(diǎn)在其尾部增加新的節(jié)點(diǎn)（node）即可。
第一種情況，假設(shè)我們插入一個(gè)元素 1，此時(shí)由于鏈表為空，就會(huì)走到（行 {2}）代碼處，示意圖如下：
第二種情況，假設(shè)我們?cè)俨迦胍粋€(gè)元素 2，此時(shí)鏈表頭部 head 指向不為空，走到（行 {3}）代碼處，通過(guò) while 循環(huán)直到找到最后一個(gè)節(jié)點(diǎn)，也就是當(dāng) current.next = null 時(shí)說(shuō)明已經(jīng)達(dá)到鏈表尾部了，接下來(lái)我們要做的就是將 current.next 指向想要添加到鏈表的節(jié)點(diǎn)，示意圖如下：
算法實(shí)現(xiàn)如下：
insertTail鏈表指定位置插入元素
實(shí)現(xiàn)鏈表的 insert 方法，在任意位置插入數(shù)據(jù)，同樣分為兩種情況，以下一一進(jìn)行介紹。
如果是鏈表的第一個(gè)位置，很簡(jiǎn)單看代碼塊（行 {1}）處，將 node.next 設(shè)置為 current（鏈表中的第一個(gè)元素），此時(shí)的 node 就是我們想要的值，接下來(lái)將 node 的引用改為 head（node、head 這兩個(gè)變量此時(shí)在堆內(nèi)存中的地址是相同的），示意圖如下所示：
如果要插入的元素不是鏈表第一個(gè)位置，通過(guò) for 循環(huán)，從鏈表的第一個(gè)位置開(kāi)始循環(huán)，定位到要插入的目標(biāo)位置，for 循環(huán)中的變量 previous（行 {3}）是對(duì)想要插入新元素位置之前的一個(gè)對(duì)象引用，current（行 {4}）是對(duì)想要插入新元素位置之后的一個(gè)對(duì)象引用，清楚這個(gè)關(guān)系之后開(kāi)始鏈接，我們本次要插入的節(jié)點(diǎn) node.next 與 current（行 {5}）進(jìn)行鏈接，之后 previous.next 指向 node（行 {6}）。
算法實(shí)現(xiàn)如下：
/**移除指定位置的元素
定義 delete(i) 方法實(shí)現(xiàn)移除任意位置的元素，同樣也有兩種情況，第一種就是移除第一個(gè)元素（行 {1}）處，第二種就是移除第一個(gè)元素以外的任一元素，通過(guò) for 循環(huán)，從鏈表的第一個(gè)位置開(kāi)始循環(huán)，定位到要?jiǎng)h除的目標(biāo)位置，for 循環(huán)中的變量 previous（行 {2}）是對(duì)想要?jiǎng)h除元素位置之前的一個(gè)對(duì)象引用，current（行 {3}）是對(duì)想要?jiǎng)h除元素位置之后的一個(gè)對(duì)象引用，要從列表中移除元素，需要做的就是將 previous.next 與 current.next 進(jìn)行鏈接，那么當(dāng)前元素會(huì)被丟棄于計(jì)算機(jī)內(nèi)存中，等待垃圾回收器回收處理。
關(guān)于內(nèi)存管理和垃圾回收機(jī)制的知識(shí)可參考文章 Node.js 內(nèi)存管理和 V8 垃圾回收機(jī)制通過(guò)一張圖，來(lái)看下刪除一個(gè)元素的過(guò)程：
算法實(shí)現(xiàn)如下：
delete獲取指定位置元素
定義 getElement(i) 方法獲取指定位置元素，類似于 delete 方法可做參考，在鎖定位置目標(biāo)后，返回當(dāng)前的元素即可 previous.element。
getElement查找元素的第一個(gè)位置索引
返回鏈表中第 1 個(gè)與 e 滿足關(guān)系的元素，存在則返回其索引值；不存在，則返回值為 -1
locateElement在鏈表中返回指定元素的前驅(qū)
如果是第一個(gè)元素，是沒(méi)有前驅(qū)的直接返回 false，否則的話，需要遍歷鏈表，定位到目標(biāo)元素返回其前驅(qū)即當(dāng)前元素的上一個(gè)元素，如果在鏈表中沒(méi)有找到，則返回 false。
priorElement在鏈表中返回指定元素的后繼
nextElement鏈表元素遍歷
定義 traversing() 方法對(duì)鏈表的元素進(jìn)行遍歷輸出，主要是將 elment 轉(zhuǎn)為字符串拼接輸出。
traversing單向鏈表與順序表優(yōu)缺點(diǎn)比較 查找：單向鏈表時(shí)間復(fù)雜度為 O(n)；順序表時(shí)間復(fù)雜度為 O(1) 插入與刪除：單向鏈表時(shí)間復(fù)雜度為 O(1)；順序表需要移動(dòng)元素時(shí)間復(fù)雜度為 O(n) * 空間性能：單向鏈表無(wú)需預(yù)先分配存儲(chǔ)空間；順序表需要預(yù)先分配內(nèi)存空間，大了浪費(fèi)，小了易溢出
單向鏈表源碼地址如下：
https://github.com/Q-Angelo/project-training/tree/master/algorithm/single-list.js雙向鏈表
雙向鏈表也叫雙鏈表。與單向鏈表的區(qū)別是雙向鏈表中不僅有指向后一個(gè)節(jié)點(diǎn)的指針，還有指向前一個(gè)節(jié)點(diǎn)的指針。這樣可以從任何一個(gè)節(jié)點(diǎn)訪問(wèn)前一個(gè)節(jié)點(diǎn)，當(dāng)然也可以訪問(wèn)后一個(gè)節(jié)點(diǎn)，以至整個(gè)鏈表。
雙向鏈表是基于單向鏈表的擴(kuò)展，很多操作與單向鏈表還是相同的，在構(gòu)造函數(shù)中我們要增加 prev 指向前一個(gè)元素的指針和 tail 用來(lái)保存最后一個(gè)元素的引用，可以從尾到頭反向查找，重點(diǎn)修改插入、刪除方法。
修改初始化鏈表
constructor修改鏈表指定位置插入元素
在雙向鏈表中我們需要控制 prev 和 next 兩個(gè)指針，比單向鏈表要復(fù)雜些，這里可能會(huì)出現(xiàn)三種情況：
情況一：鏈表頭部添加
如果是在鏈表的第一個(gè)位置插入元素，當(dāng) head 頭部指針為 null 時(shí)，將 head 和 tail 都指向 node 節(jié)點(diǎn)即可，如果 head 頭部節(jié)點(diǎn)不為空，將 node.next 的下一個(gè)元素為 current，那么同樣 current 的上個(gè)元素就為 node（current.prev = node），node 就為第一個(gè)元素且 prev（node.prev = null）為空，最后我們將 head 指向 node。
假設(shè)我們當(dāng)前鏈表僅有一個(gè)元素 b，我們要在第一個(gè)位置插入元素 a，圖例如下：
情況二：鏈表尾部添加
這又是一種特殊的情況鏈表尾部添加，這時(shí)候我們要改變 current 的指向?yàn)?tail（引用最后一個(gè)元素），開(kāi)始鏈接把 current 的 next 指向我們要添加的節(jié)點(diǎn) node，同樣 node 的上個(gè)節(jié)點(diǎn) prev 就為 current，最后我們將 tail 指向 node。
繼續(xù)上面的例子，我們?cè)阪湵砦膊吭谠黾右粋€(gè)元素 d
情況三：非鏈表頭部、尾部的任意位置添加
這個(gè)和單向鏈表插入那塊是一樣的思路，不清楚的，在回頭去看下，只不過(guò)增加了節(jié)點(diǎn)的向前一個(gè)元素的引用，current.prev 指向 node，node.prev 指向 previous。
繼續(xù)上面的例子，在元素 d 的位置插入元素 c，那么 d 就會(huì)變成 c 的下一個(gè)元素，圖例如下：
算法實(shí)現(xiàn)如下：
insert移除鏈表元素
雙向鏈表中移除元素同插入一樣，需要考慮三種情況，下面分別看下各自實(shí)現(xiàn)：
情況一：鏈表頭部移除
current 是鏈表中第一個(gè)元素的引用，對(duì)于移除第一個(gè)元素，我們讓 head = current 的下一個(gè)元素，即 current.next，這在單向鏈表中就已經(jīng)完成了，但是雙向鏈表我們還要修改節(jié)點(diǎn)的上一個(gè)指針域，再次判斷當(dāng)前鏈表長(zhǎng)度是否等于 1，如果僅有一個(gè)元素，刪除之后鏈表就為空了，那么 tail 也要置為 null，如果不是一個(gè)元素，將 head 的 prev 設(shè)置為 null，圖例如下所示：
情況二：鏈表尾部移除
改變 current 的指向?yàn)?tail（引用最后一個(gè)元素），在這是 tail 的引用為 current 的上個(gè)元素，即最后一個(gè)元素的前一個(gè)元素，最后再將 tail 的下一個(gè)元素 next 設(shè)置為 null，圖例如下所示：
情況三：鏈表尾部移除
這個(gè)和單向鏈表刪除那塊是一樣的思路，不清楚的，在回頭去看下，只增加了 current.next.prev = previous 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的 prev 指針域等于當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn) previous，圖例如下所示：
算法實(shí)現(xiàn)如下：
delete雙向鏈表源碼地址如下：
https://github.com/Q-Angelo/project-training/tree/master/algorithm/doubly-linked-list.js循環(huán)鏈表
在單向鏈表和雙向鏈表中，如果一個(gè)節(jié)點(diǎn)沒(méi)有前驅(qū)或后繼該節(jié)點(diǎn)的指針域就指向?yàn)?null，循環(huán)鏈表中最后一個(gè)節(jié)點(diǎn) tail.next 不會(huì)指向 null 而是指向第一個(gè)節(jié)點(diǎn) head，同樣雙向引用中 head.prev 也會(huì)指向 tail 元素，如下圖所示：
可以看出循環(huán)鏈表可以將整個(gè)鏈表形成一個(gè)環(huán)，既可以向單向鏈表那樣只有單向引用，也可以向雙向鏈表那樣擁有雙向引用。
以下基于單向鏈表一節(jié)的代碼進(jìn)行改造
尾部插入元素
對(duì)于環(huán)形鏈表的節(jié)點(diǎn)插入與單向鏈表的方式不同，如果當(dāng)前節(jié)點(diǎn)為空，當(dāng)前節(jié)點(diǎn)的 next 值不指向?yàn)?null，指向 head。如果頭部節(jié)點(diǎn)不為空，遍歷到尾部節(jié)點(diǎn)，注意這里不能在用 current.next 為空進(jìn)行判斷了，否則會(huì)進(jìn)入死循環(huán)，我們需要判斷當(dāng)前節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)是否等于頭部節(jié)點(diǎn)，算法實(shí)現(xiàn)如下所示：
insertTail鏈表任意位置插入元素
實(shí)現(xiàn)同鏈表尾部插入相似，注意：將新節(jié)點(diǎn)插入在原鏈表頭部之前，首先，要將新節(jié)點(diǎn)的指針指向原鏈表頭節(jié)點(diǎn)，并遍歷整個(gè)鏈表找到鏈表尾部，將鏈表尾部指針指向新增節(jié)點(diǎn)，圖例如下：
算法實(shí)現(xiàn)如下所示：
insert移除指定位置元素
與之前不同的是，如果刪除第一個(gè)節(jié)點(diǎn)，先判斷鏈表在僅有一個(gè)節(jié)點(diǎn)的情況下直接將 head 置為 null，否則不僅僅只有一個(gè)節(jié)點(diǎn)的情況下，首先將鏈表頭指針移動(dòng)到下一個(gè)節(jié)點(diǎn)，同時(shí)將最后一個(gè)節(jié)點(diǎn)的指針指向新的鏈表頭部
算法實(shí)現(xiàn)如下所示：
delete最后在遍歷的時(shí)候也要注意，不能在根據(jù) current.next 是否為空來(lái)判斷鏈表是否結(jié)束，可以根據(jù)鏈表元素長(zhǎng)度或者 current.next 是否等于頭節(jié)點(diǎn)來(lái)判斷，本節(jié)源碼實(shí)現(xiàn)鏈接如下所示：
https://github.com/Q-Angelo/project-training/tree/master/algorithm/circular-linked-list.js總結(jié)
本節(jié)主要講解的是線性表，從順序表->單向鏈表->雙向鏈表->循環(huán)鏈表，這個(gè)過(guò)程也是循序漸進(jìn)的，前兩個(gè)講的很詳細(xì)，雙向鏈表與循環(huán)鏈表通過(guò)與前兩個(gè)不同的地方進(jìn)行比較針對(duì)性的進(jìn)行了講解，另外學(xué)習(xí)線性表也是學(xué)習(xí)其它數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)特別是涉及到一些實(shí)現(xiàn)算法的時(shí)候，有時(shí)候并不是看一遍就能理解的，總之多實(shí)踐、多思考。
Reference
- https://zh.wikipedia.org/wiki/線性表
- 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（第2版）
- 大話數(shù)據(jù)結(jié)構(gòu)
總結(jié)
以上是生活随笔為你收集整理的链表list(链式存储结构实现)_数据结构知否知否系列之 — 线性表的顺序与链式存储篇（8000 多字长文）...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： gitee合并分支_使用Gitee进行协
- 下一篇： double类型怎么取余_数据类型和运算