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

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

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

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

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

Ok，正文...

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

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

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

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

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

比如：

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

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

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

然而如果進行插入新值或者刪除操作時，效率則會很低。因為如果插入的是中間位置、或者最前端的位置，則需要對當(dāng)前操作位置后面的數(shù)據(jù)都要向后或者向前移動。

這個不難理解。

就像一個隊伍，如果你想插入到第一個位置，那么從第二個開始之后的每個人都需要向后移動一個位置。

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

再拿一個隊伍舉例子：

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

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

當(dāng)我們對鏈表進行 get 或者 set 操作的時候，其實也是需要花費常數(shù)時間。但鏈表的 get 其實效率比數(shù)組的低，因為鏈表的缺點就是不容易做索引，它不像數(shù)組可以有索引來查找。

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

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

當(dāng)然這點并不是鏈表唯一的一個優(yōu)點，另一個優(yōu)點則是對 remove 和 insert 的操作只需要花費常數(shù)時間。因為鏈表的刪除和插入只需要查找到對應(yīng)位置，然后修改指針即可。

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

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

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

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

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

Ok~

編碼

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

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

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

不過這里我可以提一下，其實 Python 源碼中有一個抽象類 Iterator ，它的抽象方法是 next 。

2、接下來，我們就可以這樣來定義 LinkedList 類：

class LinkedList(Collection):

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

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

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

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

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

5、開始實現(xiàn) LinkedList

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

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

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

A、構(gòu)造器

之所以把這段邏輯單獨抽離到 doClear 中，是因為這段邏輯也是一個清空數(shù)據(jù)的邏輯。

B、addIndex(self,index,data)

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

所以我們需要先提供一個

getNodeWithIndex(index)

方法來獲取對應(yīng)位置的節(jié)點（Node）

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

getNodeWithIndexLowerUpper(index,lower,upper) 中。

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

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

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

如上：

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

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

C、addData(self,data)

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

D、size(self)

size 方法其實就很簡單了，因為我們每次 add 的時候會對 thisSize 進行自增。因此 thisSize 必然就是這個鏈表的長度。

E、isEmpty(self)

直接判斷 thisSize 即可。

F、remove(self,index)

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

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

H、iterator(self)

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

其實自定義一個 Python 的迭代器也是很簡單的。

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

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

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

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

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

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

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

最后我們來測試一下這個 LinkedList

打印結(jié)果如下：