Python双向循环链表实现方法分析

本文实例讲述了Python双向循环链表实现方法。分享给大家供大家参考，具体如下：

最近身边的朋友在研究用python来实现数据结构。遇到一个问题就是双向循环链表的实现，改指向的时候总是发蒙。

我自己尝实现了一个python的双向循环链表。附上代码，希望对大家有帮助。

如果不懂什么是双向循环链表的伙伴，需要补习一下数据结构的基础之后哦~~~

在python当中 用一个类Node 来实现链表的节点，节点数据有三个变量：

当前节点的前一个节点我们叫他前驱，后一个节点我们叫他后继。

在链表类当中，我们有一个变量head是链表的头指针

我们拿着链表的头head，就可以对他进行一些列操作：（ 由于是双向循环链表，修改指针特别容易出错，我尽量说的细致，方便大家参考）

判断空：is_empty()

如果头指针head没有指向则链表是空的 否则不是空的

在头部添加元素: add(item)

1 新建一个节点 里面的值是item。

2 放入头部：

2.1 如果链表是空的，node的next和prev都指向自己，然后head再指向node

在尾部添加元素: append(item)

1 创建一个新节点node 里面的值是item

2 放入尾部：

2.1 如果链表空，则执行头部添加add就可以

2.2 链表非空：

2.2.1 node的next指向head

2.2.2 node的prev指向head的prev

2.2.3 head的prev元素的next指向node

2.2.4 head的prev指向改为node

2.2.5 head指向node  更换了头部

指定位置添加元素： insert( pos , item )

1 新建一个节点node 里面的值是item

2 找到合适的位置插进去：

2.1 如果pos <= 0 还小，那就执行头插方法 add()

2.2 如果pos >= 链表长度, 那就执行尾部插入 append()

2.3 如果pos位置在链表的中间：

2.3.1 定义一个临时变量temp 按照传入的pos找到要插入的位置的前一个元素

2.3.2 node的prev设为temp,node的next设为temp的next

2.3.3 temp的next指向的节点的prev改为node

2.3.4 temp的next改为node

得到链表长度： length()

1 我们设置一个临时变量temp初始设为head ， 设置一个计数器count 初始为 0

2 令count自增1 然后temp改指向自己的下一个元素 一直到temp遇到None 为止，temp到了链表的最后一个元素

通过这样的方式，统计出一共有多少个节点返回

遍历链表数据： travelji()

1 设置一个临时变量temp初始化设为head

2 temp 每次输出自己指向元素的值，然后在指向自己的下一个元素，一直temp为None 说明到了列表的尾部