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

这篇文章主要介绍了Python双向循环链表,结合实例形式分析了Python双向链表的定义、遍历、添加、删除、搜索等相关操作技巧,需要的朋友可以参考下

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

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

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

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

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

prev：前驱指针：用于指向当前节点前一个节点
next: 后继指针用于指向当前节点后一个节点
item：值，用于存储该节点要存的数值

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

在链表类当中，我们有一个变量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 说明到了列表的尾部

删除链表元素：remove( item )

1 开启temp临时变量初始化为head ，

2 temp不断指向自己的下一个元素，每次指向一个元素都检查当前值是不是item，如果找到item则删除它返回True，如果没找到就到尾部了就返回False

2.1 删除过程：

2.1.1 temp的前一个元素的next改为temp的后一个元素

2.1.2 temp的后一个元素的prev改为前一个元素

查询是否有元素：search()

设置一个临时变量temp从head开始，不断指向自己下一个，每次都检查一下自己的值如果和item相同返回True结束

如果temp变成None 则到尾部了都没找到返回False

上代码！

 # -*- coding:utf-8 -*- #!python3 #链表的节点 class Node(object): def __init__(self , item ): self.item = item #节点数值 self.prev = None #用于指向前一个元素 self.next = None #用于指向后一个元素 #双向循环链表 class DoubleCircleLinkList(object): def __init__(self): self.__head = None #初始化的时候头节点设为空、 #判断链表是否为空，head为None 的话则链表是空的 def is_empty(self): return self.__head is None #头部添加元素的方法 def add(self,item): node = Node(item) #新建一个节点node 里面的值是item # 如果链表是空的，则node的next和prev都指向自己(因为是双向循环)，head指向node if self.is_empty(): self.__head = node node.next = node node.prev = node # 否则链表不空 else: node.next = self.__head #node的next设为现在的head node.prev = self.__head.prev #node的prev 设为现在head的prev self.__head.prev.next = node #现在head的前一个元素的next设为node self.__head.prev = node #现在head的前驱 改为node self.__head = node #更改头部指针 #尾部添加元素方法 def append(self , item): #如果当前链表是空的 那就调用头部插入方法 if self.is_empty(): self.add(item) #否则链表不为空 else : node = Node(item) #新建一个节点node #因为是双向循环链表，所以head的prev其实就是链表的尾部 node.next = self.__head #node的下一个设为头 node.prev = self.__head.prev #node的前驱设为现在头部的前驱 self.__head.prev.next = node #头部前驱的后继设为node self.__head.prev = node #头部自己的前驱改为node #获得链表长度 节点个数 def length(self): #如果链表是空的 就返回0 if self.is_empty(): return 0 #如果不是空的 else: cur = self.__head #临时变量cur表示当前位置 初始化设为头head count = 1 #设一个计数器count，cur每指向一个节点，count就自增1 目前cur指向头，所以count初始化为1 #如果cur.next不是head，说明cur目前不是最后一个元素，那么count就1，再让cur后移一位 while cur.next is not self.__head: count += 1 cur = cur.next #跳出循环说明所有元素都被累加了一次 返回count就是一共有多少个元素 return count #遍历链表的功能 def travel(self): #如果当前自己是空的，那就不遍历 if self.is_empty(): return #链表不空 else : cur = self.__head #临时变量cur表示当前位置，初始化为链表的头部 #只要cur的后继不是头说明cur不是最后一个节点，我们就输出当前值，并让cur后移一个节点 while cur.next is not self.__head: print( cur.item,end=" " ) cur = cur.next #当cur的后继是head的时候跳出循环了，最后一个节点还没有打印值 在这里打印出来 print( cur.item ) #置顶位置插入节点 def insert(self, pos , item ): #如果位置<=0 则调用头部插入方法 if pos <= 0: self.add(item) #如果位置是最后一个或者更大 就调用尾部插入方法 elif pos > self.length() - 1 : self.append(item) #否则插入位置就是链表中间 else : index = 0 #设置计数器，用于标记我们后移了多少步 cur = self.__head #cur标记当前所在位置 #让index每次自增1 ，cur后移，当index=pos-1的时候说明cur在要插入位置的前一个元素，这时候停下 while index

运行结果：