用Python实现一个 LinkedList双向链表

提到 LinkedList，我相信大部分 Java 开发者是知道的。但 Pythonner 也许并不知道。

在分享之前，我先说说为什么写这篇文章。

大部分读者知道我是一名 Android 开发者，而我最熟悉的语言也正是 Java 。集合其实在 Java 是一个很重要的概念，而 LinkedList 也只是集合中的一个实现类而已。当然 LinkedList 并不是 Java 中唯一的集合，但它却是 Java 中使用双向链表的一个代表类。

很多 Java 开发者也许知道双向链表的结构以及好处什么，毕竟 JDK 里面已经提供好了 LinkedList 这个类。

这次我也借着 JDK 中 LinkedList 的实现原理，用 Python 来实现一个这样的数据结构。这篇文章也将会使你更加深入的了解这个数据结构。

Ok，正文...

至于“集合”是什么就不用细说，可以理解为一组元素的合集。

其实提到 LinkedList ，会有一个相对的集合 ArrayList。这两个都是 Collection (集合) 的实现类。当然这两个也是有区别的，ArrayList 内部是由数组实现的，而 LinkedList 则是由链表（双向）实现的。

为什么会有这种数据结构的集合？

在讨论这个之前，我先科普下这两个数据结构。

数组大家应该都知道，可以理解为一组线性、连续存储的数据结构。而链表则是由指针（指向）关系起来的一个数据结构。

比如：

双向链表的意思则是既有一个 prev(前驱指针) ，又有一个 next(后驱指针)来构成的一种数据结构。这两个则是为了构建出节点之间的关系。

再回到之前的问题，为什么存在这两种数据结构的集合？

大家可以想一下，如果我们要做 get 、set、 remove 操作那么针对 ArrayList 其实只需要花费常数时间，因为数组的索引大大提高了效率。

然而如果进行插入新值或者删除操作时，效率则会很低。因为如果插入的是中间位置、或者最前端的位置，则需要对当前操作位置后面的数据都要向后或者向前移动。

这个不难理解。

就像一个队伍，如果你想插入到第一个位置，那么从第二个开始之后的每个人都需要向后移动一个位置。

因此这时候就需要链表这样的数据结构。每个节点都存在一个前驱和后驱，我们只要修改指针指向的节点就可以完成插入或者删除操作。

再拿一个队伍举例子：

在这个队伍中每一个人都知道了自己前面是谁、后面是谁。那么当你插入到第一个位置的时候，你只需要告诉队伍的第一个人你在他前面即可，而后面的人也不需要关注自己的位置在哪，他们只需要关注自己前面和后面的人是谁。

不过这里需要注意一点，像这样的双向链表会出现最前端没有前驱指针，后端没有后驱指针。因此双向链表会在前面追加一个 头节点、后端增加一个 尾节点。也可以称之为 “标记节点”。

当我们对链表进行 get 或者 set 操作的时候，其实也是需要花费常数时间。但链表的 get 其实效率比数组的低，因为链表的缺点就是不容易做索引，它不像数组可以有索引来查找。

不过链表的查找为了提高效率，也可以做相应的优化。比如双向链表的一个特点就是两端都可以作为遍历的起点。

这样做的好处就是，如果 查找 的位置是链表靠后的位置那么就可以直接从尾部开始向前查找。

当然这点并不是链表唯一的一个优点，另一个优点则是对 remove 和 insert 的操作只需要花费常数时间。因为链表的删除和插入只需要查找到对应位置，然后修改指针即可。

所以综上，我们如果对一个集合的查找频率比较高那么最好用数组作为数据结构，但如果对插入、删除频率比较高，那么选用链表则是一个高效率的决定。

扯了这么多，其实这两种集合在 JDK 中已经有提供。

那么 Python 能否也实现这样的集合呢？答案是肯定的。

不过这篇文章只会去实现 LinkedList （双向链表）的集合，另一种 ArrayList（数组）不做实现。

在实现 LinkedList 的过程中，我会用到 ”抽象类“ 的概念。这是为了让代码结构更清晰，我将 LinkedList 对外提供的方法抽象出来，然后在子类中具体实现即可。

Ok~

编码

1、在我们开始编写 LinkedList 之前先考虑下需要定义哪些抽象方法。

首先我这边先创建一个 Collection 的抽象类，而这个抽象类中提供了如下方法：

心细的朋友可能会注意到有个 iterator 的抽象方法。这个方法将会返回一个迭代器，用于我们对 LinkedList 的迭代，后面会讲到。

不过这里我可以提一下，其实 Python 源码中有一个抽象类 Iterator ，它的抽象方法是 next 。

2、接下来，我们就可以这样来定义 LinkedList 类：

class LinkedList(Collection):

让 LinedList 继承自 Collection ，来实现我们的具体方法。

3、到这里我们的集合类已经准备好，但还缺个东西就是数据类。也可以理解为元素类，不过在链表中的元素也可以叫做节点。

如上是一个节点类，节点类中包括了当前节点的数据、当前节点的前驱和当前节点的后驱。

4、在 Collection 中有个抽象方法 iterator 。这里我们还需要定义一个类，这个类则是自定义的迭代器。我们在 iterator 的方法中返回这个实例就行。

如上，继承自 Iterator 的 子类。我们在构造器中增加了 outter 这个入参，是因为我们在 LinkedListItertor 中需要使用到 LinkedList 中的参数，因此我们在构造器中增加 outter 传入 LinkedList 的实例

5、开始实现 LinkedList

上面几步已经提供了我们编写 LinkedList 需要的基础类，那么接下来我们就可以具体来实现逻辑了。

在实现逻辑之前需要再次提一下：前面的内容有提到两个”标记节点“，一个头节点、一个尾节点。

因此我们需要在构造器中就增加这两个标记节点。

A、构造器

之所以把这段逻辑单独抽离到 doClear 中，是因为这段逻辑也是一个清空数据的逻辑。

B、addIndex(self,index,data)

接下来就实现 ”在指定位置插入数据“。在链表中我们要插入一个数据，就必须先拿到链表中当前位置的节点。然后对其前驱进行指向即可。（回忆 前面的一个队伍的例子）

所以我们需要先提供一个

getNodeWithIndex(index)

方法来获取对应位置的节点（Node）

上面这段代码可以看到，我将逻辑实现放到了

getNodeWithIndexLowerUpper(index,lower,upper) 中。

这么做的原因也是上面提到的，既然这是一个双向链表，那么我们当然可以选择性的从两端开始遍历。

即 ：如果当前 index 靠后 ，则从尾部开始向前遍历。靠前的话 则从头部向后遍历。

既然 getNodeWithIndex 我们已经写好了，那么接下来就可以完善 add 方法了。首先思考下，add 到指定 index 中的含义其实是需要先拿到当前 index 的 Node，然后将需要添加的 Node 插入到这个位置即可。

如上：

首先我们创建一个前驱指向当前位置节点的前驱，后驱指向当前节点的 Node.

然后通过变换当前节点前驱的指针和当前位置的前驱就实现了插入的操作。

C、addData(self,data)

接下来我们来实现在尾部插入一个 Node。 其实就是在链表的尾部添加数据即可，就相当于在 size() 的位置插入数据。调用 addIndex(size(),data) 就行。

D、size(self)

size 方法其实就很简单了，因为我们每次 add 的时候会对 thisSize 进行自增。因此 thisSize 必然就是这个链表的长度。

E、isEmpty(self)

直接判断 thisSize 即可。

F、remove(self,index)

理解了 add 的逻辑，那么 remove 则比较简单。我们拿到需要 remove 的 Node 然后修改前驱和后驱即可。

OK~ 以上就将所有基础的抽象方法已经实现。接下来，就可以实现一个迭代器，用来迭代我们编写的 LinkedList。

H、iterator(self)

在这里我们需要自定义一个迭代器。

其实自定义一个 Python 的迭代器也是很简单的。

我们只需要继承 Iterator，然后在抽象方法 next 中将数据遍历即可。

当然迭代器作用无疑是迭代操作，因此我们需要增加中断迭代的条件。

其中 current 表示当前节点的位置（指针），outter 是外部类（LinkedList）的引用。

在构造器中我们将当前指针初始到 beginMarker 的Next 节点，也就是第一个数据。

然后重写 Iterator 的 next 方法，一直遍历到指针指向 endMarker 。也就是指针到达尾节点的时候就中断迭代。

这时候，我们只需要实现 next 这个方法即可。

返回一个自定义迭代器的实例即可，入参是当前 LinkedList 实例。

最后我们来测试一下这个 LinkedList

打印结果如下：