提到 LinkedList，我相信大部分 Java 開(kāi)發(fā)者是知道的。但 Pythonner 也許并不知道。

在分享之前，我先說(shuō)說(shuō)為什么寫這篇文章。

大部分讀者知道我是一名 Android 開(kāi)發(fā)者，而我最熟悉的語(yǔ)言也正是 Java 。集合其實(shí)在 Java 是一個(gè)很重要的概念，而 LinkedList 也只是集合中的一個(gè)實(shí)現(xiàn)類而已。當(dāng)然 LinkedList 并不是 Java 中唯一的集合，但它卻是 Java 中使用雙向鏈表的一個(gè)代表類。

很多 Java 開(kāi)發(fā)者也許知道雙向鏈表的結(jié)構(gòu)以及好處什么，畢竟 JDK 里面已經(jīng)提供好了 LinkedList 這個(gè)類。

這次我也借著 JDK 中 LinkedList 的實(shí)現(xiàn)原理，用 Python 來(lái)實(shí)現(xiàn)一個(gè)這樣的數(shù)據(jù)結(jié)構(gòu)。這篇文章也將會(huì)使你更加深入的了解這個(gè)數(shù)據(jù)結(jié)構(gòu)。

Ok，正文...

至于“集合”是什么就不用細(xì)說(shuō)，可以理解為一組元素的合集。

其實(shí)提到 LinkedList ，會(huì)有一個(gè)相對(duì)的集合 ArrayList。這兩個(gè)都是 Collection (集合) 的實(shí)現(xiàn)類。當(dāng)然這兩個(gè)也是有區(qū)別的，ArrayList 內(nèi)部是由數(shù)組實(shí)現(xiàn)的，而 LinkedList 則是由鏈表（雙向）實(shí)現(xiàn)的。

為什么會(huì)有這種數(shù)據(jù)結(jié)構(gòu)的集合？

在討論這個(gè)之前，我先科普下這兩個(gè)數(shù)據(jù)結(jié)構(gòu)。

數(shù)組大家應(yīng)該都知道，可以理解為一組線性、連續(xù)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)。而鏈表則是由指針（指向）關(guān)系起來(lái)的一個(gè)數(shù)據(jù)結(jié)構(gòu)。

比如：

雙向鏈表的意思則是既有一個(gè) prev(前驅(qū)指針) ，又有一個(gè) next(后驅(qū)指針)來(lái)構(gòu)成的一種數(shù)據(jù)結(jié)構(gòu)。這兩個(gè)則是為了構(gòu)建出節(jié)點(diǎn)之間的關(guān)系。

再回到之前的問(wèn)題，為什么存在這兩種數(shù)據(jù)結(jié)構(gòu)的集合？

大家可以想一下，如果我們要做 get 、set、 remove 操作那么針對(duì) ArrayList 其實(shí)只需要花費(fèi)常數(shù)時(shí)間，因?yàn)閿?shù)組的索引大大提高了效率。

然而如果進(jìn)行插入新值或者刪除操作時(shí)，效率則會(huì)很低。因?yàn)槿绻迦氲氖侵虚g位置、或者最前端的位置，則需要對(duì)當(dāng)前操作位置后面的數(shù)據(jù)都要向后或者向前移動(dòng)。

這個(gè)不難理解。

就像一個(gè)隊(duì)伍，如果你想插入到第一個(gè)位置，那么從第二個(gè)開(kāi)始之后的每個(gè)人都需要向后移動(dòng)一個(gè)位置。

因此這時(shí)候就需要鏈表這樣的數(shù)據(jù)結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)都存在一個(gè)前驅(qū)和后驅(qū)，我們只要修改指針指向的節(jié)點(diǎn)就可以完成插入或者刪除操作。

再拿一個(gè)隊(duì)伍舉例子：

在這個(gè)隊(duì)伍中每一個(gè)人都知道了自己前面是誰(shuí)、后面是誰(shuí)。那么當(dāng)你插入到第一個(gè)位置的時(shí)候，你只需要告訴隊(duì)伍的第一個(gè)人你在他前面即可，而后面的人也不需要關(guān)注自己的位置在哪，他們只需要關(guān)注自己前面和后面的人是誰(shuí)。

不過(guò)這里需要注意一點(diǎn)，像這樣的雙向鏈表會(huì)出現(xiàn)最前端沒(méi)有前驅(qū)指針，后端沒(méi)有后驅(qū)指針。因此雙向鏈表會(huì)在前面追加一個(gè) 頭節(jié)點(diǎn)、后端增加一個(gè) 尾節(jié)點(diǎn)。也可以稱之為 “標(biāo)記節(jié)點(diǎn)”。

當(dāng)我們對(duì)鏈表進(jìn)行 get 或者 set 操作的時(shí)候，其實(shí)也是需要花費(fèi)常數(shù)時(shí)間。但鏈表的 get 其實(shí)效率比數(shù)組的低，因?yàn)殒湵淼娜秉c(diǎn)就是不容易做索引，它不像數(shù)組可以有索引來(lái)查找。

不過(guò)鏈表的查找為了提高效率，也可以做相應(yīng)的優(yōu)化。比如雙向鏈表的一個(gè)特點(diǎn)就是兩端都可以作為遍歷的起點(diǎn)。

這樣做的好處就是，如果 查找 的位置是鏈表靠后的位置那么就可以直接從尾部開(kāi)始向前查找。

當(dāng)然這點(diǎn)并不是鏈表唯一的一個(gè)優(yōu)點(diǎn)，另一個(gè)優(yōu)點(diǎn)則是對(duì) remove 和 insert 的操作只需要花費(fèi)常數(shù)時(shí)間。因?yàn)殒湵淼膭h除和插入只需要查找到對(duì)應(yīng)位置，然后修改指針即可。

所以綜上，我們?nèi)绻麑?duì)一個(gè)集合的查找頻率比較高那么最好用數(shù)組作為數(shù)據(jù)結(jié)構(gòu)，但如果對(duì)插入、刪除頻率比較高，那么選用鏈表則是一個(gè)高效率的決定。

扯了這么多，其實(shí)這兩種集合在 JDK 中已經(jīng)有提供。

那么 Python 能否也實(shí)現(xiàn)這樣的集合呢？答案是肯定的。

不過(guò)這篇文章只會(huì)去實(shí)現(xiàn) LinkedList （雙向鏈表）的集合，另一種 ArrayList（數(shù)組）不做實(shí)現(xiàn)。

在實(shí)現(xiàn) LinkedList 的過(guò)程中，我會(huì)用到 ”抽象類“ 的概念。這是為了讓代碼結(jié)構(gòu)更清晰，我將 LinkedList 對(duì)外提供的方法抽象出來(lái)，然后在子類中具體實(shí)現(xiàn)即可。

Ok~

編碼

1、在我們開(kāi)始編寫 LinkedList 之前先考慮下需要定義哪些抽象方法。

首先我這邊先創(chuàng)建一個(gè) Collection 的抽象類，而這個(gè)抽象類中提供了如下方法：

心細(xì)的朋友可能會(huì)注意到有個(gè) iterator 的抽象方法。這個(gè)方法將會(huì)返回一個(gè)迭代器，用于我們對(duì) LinkedList 的迭代，后面會(huì)講到。

不過(guò)這里我可以提一下，其實(shí) Python 源碼中有一個(gè)抽象類 Iterator ，它的抽象方法是 next 。

2、接下來(lái)，我們就可以這樣來(lái)定義 LinkedList 類：

class LinkedList(Collection):

讓 LinedList 繼承自 Collection ，來(lái)實(shí)現(xiàn)我們的具體方法。

3、到這里我們的集合類已經(jīng)準(zhǔn)備好，但還缺個(gè)東西就是數(shù)據(jù)類。也可以理解為元素類，不過(guò)在鏈表中的元素也可以叫做節(jié)點(diǎn)。

如上是一個(gè)節(jié)點(diǎn)類，節(jié)點(diǎn)類中包括了當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)、當(dāng)前節(jié)點(diǎn)的前驅(qū)和當(dāng)前節(jié)點(diǎn)的后驅(qū)。

4、在 Collection 中有個(gè)抽象方法 iterator 。這里我們還需要定義一個(gè)類，這個(gè)類則是自定義的迭代器。我們?cè)?iterator 的方法中返回這個(gè)實(shí)例就行。

如上，繼承自 Iterator 的 子類。我們?cè)跇?gòu)造器中增加了 outter 這個(gè)入?yún)ⅲ且驗(yàn)槲覀冊(cè)?LinkedListItertor 中需要使用到 LinkedList 中的參數(shù)，因此我們?cè)跇?gòu)造器中增加 outter 傳入 LinkedList 的實(shí)例

5、開(kāi)始實(shí)現(xiàn) LinkedList

上面幾步已經(jīng)提供了我們編寫 LinkedList 需要的基礎(chǔ)類，那么接下來(lái)我們就可以具體來(lái)實(shí)現(xiàn)邏輯了。

在實(shí)現(xiàn)邏輯之前需要再次提一下：前面的內(nèi)容有提到兩個(gè)”標(biāo)記節(jié)點(diǎn)“，一個(gè)頭節(jié)點(diǎn)、一個(gè)尾節(jié)點(diǎn)。

因此我們需要在構(gòu)造器中就增加這兩個(gè)標(biāo)記節(jié)點(diǎn)。

A、構(gòu)造器

之所以把這段邏輯單獨(dú)抽離到 doClear 中，是因?yàn)檫@段邏輯也是一個(gè)清空數(shù)據(jù)的邏輯。

B、addIndex(self,index,data)

接下來(lái)就實(shí)現(xiàn) ”在指定位置插入數(shù)據(jù)“。在鏈表中我們要插入一個(gè)數(shù)據(jù)，就必須先拿到鏈表中當(dāng)前位置的節(jié)點(diǎn)。然后對(duì)其前驅(qū)進(jìn)行指向即可。（回憶 前面的一個(gè)隊(duì)伍的例子）

所以我們需要先提供一個(gè)

getNodeWithIndex(index)

方法來(lái)獲取對(duì)應(yīng)位置的節(jié)點(diǎn)（Node）

上面這段代碼可以看到，我將邏輯實(shí)現(xiàn)放到了

getNodeWithIndexLowerUpper(index,lower,upper) 中。

這么做的原因也是上面提到的，既然這是一個(gè)雙向鏈表，那么我們當(dāng)然可以選擇性的從兩端開(kāi)始遍歷。

即 ：如果當(dāng)前 index 靠后 ，則從尾部開(kāi)始向前遍歷?？壳暗脑?則從頭部向后遍歷。

既然 getNodeWithIndex 我們已經(jīng)寫好了，那么接下來(lái)就可以完善 add 方法了。首先思考下，add 到指定 index 中的含義其實(shí)是需要先拿到當(dāng)前 index 的 Node，然后將需要添加的 Node 插入到這個(gè)位置即可。

如上：

首先我們創(chuàng)建一個(gè)前驅(qū)指向當(dāng)前位置節(jié)點(diǎn)的前驅(qū)，后驅(qū)指向當(dāng)前節(jié)點(diǎn)的 Node.

然后通過(guò)變換當(dāng)前節(jié)點(diǎn)前驅(qū)的指針和當(dāng)前位置的前驅(qū)就實(shí)現(xiàn)了插入的操作。

C、addData(self,data)

接下來(lái)我們來(lái)實(shí)現(xiàn)在尾部插入一個(gè) Node。 其實(shí)就是在鏈表的尾部添加數(shù)據(jù)即可，就相當(dāng)于在 size() 的位置插入數(shù)據(jù)。調(diào)用 addIndex(size(),data) 就行。

D、size(self)

size 方法其實(shí)就很簡(jiǎn)單了，因?yàn)槲覀兠看?add 的時(shí)候會(huì)對(duì) thisSize 進(jìn)行自增。因此 thisSize 必然就是這個(gè)鏈表的長(zhǎng)度。

E、isEmpty(self)

直接判斷 thisSize 即可。

F、remove(self,index)

理解了 add 的邏輯，那么 remove 則比較簡(jiǎn)單。我們拿到需要 remove 的 Node 然后修改前驅(qū)和后驅(qū)即可。

OK~ 以上就將所有基礎(chǔ)的抽象方法已經(jīng)實(shí)現(xiàn)。接下來(lái)，就可以實(shí)現(xiàn)一個(gè)迭代器，用來(lái)迭代我們編寫的 LinkedList。

H、iterator(self)

在這里我們需要自定義一個(gè)迭代器。

其實(shí)自定義一個(gè) Python 的迭代器也是很簡(jiǎn)單的。

我們只需要繼承 Iterator，然后在抽象方法 next 中將數(shù)據(jù)遍歷即可。

當(dāng)然迭代器作用無(wú)疑是迭代操作，因此我們需要增加中斷迭代的條件。

其中 current 表示當(dāng)前節(jié)點(diǎn)的位置（指針），outter 是外部類（LinkedList）的引用。

在構(gòu)造器中我們將當(dāng)前指針初始到 beginMarker 的Next 節(jié)點(diǎn)，也就是第一個(gè)數(shù)據(jù)。

然后重寫 Iterator 的 next 方法，一直遍歷到指針指向 endMarker 。也就是指針到達(dá)尾節(jié)點(diǎn)的時(shí)候就中斷迭代。

這時(shí)候，我們只需要實(shí)現(xiàn) next 這個(gè)方法即可。

返回一個(gè)自定義迭代器的實(shí)例即可，入?yún)⑹钱?dāng)前 LinkedList 實(shí)例。

最后我們來(lái)測(cè)試一下這個(gè) LinkedList

打印結(jié)果如下：