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

2023-09-09 17:19:05 59

本文实例讲述了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.1node的next指向head

2.2.2node的prev指向head的prev

2.2.3head的prev元素的next指向node

2.2.4head的prev指向改为node

2.2.5head指向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.2node的prev设为temp,node的next设为temp的next

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

2.3.4temp的next改为node

得到链表长度：length()

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

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

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

遍历链表数据：travelji()

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

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

删除链表元素：remove(item)

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

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

2.1删除过程：

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

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

查询是否有元素：search()

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

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

上代码！

#-*-coding:utf-8-*-
#!python3
#链表的节点
classNode(object):
def__init__(self,item):
self.item=item#节点数值
self.prev=None#用于指向前一个元素
self.next=None#用于指向后一个元素
#双向循环链表
classDoubleCircleLinkList(object):
def__init__(self):
self.__head=None#初始化的时候头节点设为空、
#判断链表是否为空，head为None的话则链表是空的
defis_empty(self):
returnself.__headisNone
#头部添加元素的方法
defadd(self,item):
node=Node(item)#新建一个节点node里面的值是item
#如果链表是空的，则node的next和prev都指向自己(因为是双向循环)，head指向node
ifself.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#更改头部指针
#尾部添加元素方法
defappend(self,item):
#如果当前链表是空的那就调用头部插入方法
ifself.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
#获得链表长度节点个数
deflength(self):
#如果链表是空的就返回0
ifself.is_empty():
return0
#如果不是空的
else:
cur=self.__head#临时变量cur表示当前位置初始化设为头head
count=1#设一个计数器count，cur每指向一个节点，count就自增1目前cur指向头，所以count初始化为1
#如果cur.next不是head，说明cur目前不是最后一个元素，那么count就1，再让cur后移一位
whilecur.nextisnotself.__head:
count+=1
cur=cur.next
#跳出循环说明所有元素都被累加了一次返回count就是一共有多少个元素
returncount
#遍历链表的功能
deftravel(self):
#如果当前自己是空的，那就不遍历
ifself.is_empty():
return
#链表不空
else:
cur=self.__head#临时变量cur表示当前位置，初始化为链表的头部
#只要cur的后继不是头说明cur不是最后一个节点，我们就输出当前值，并让cur后移一个节点
whilecur.nextisnotself.__head:
print(cur.item,end="")
cur=cur.next
#当cur的后继是head的时候跳出循环了，最后一个节点还没有打印值在这里打印出来
print(cur.item)
#置顶位置插入节点
definsert(self,pos,item):
#如果位置<=0则调用头部插入方法
ifpos<=0:
self.add(item)
#如果位置是最后一个或者更大就调用尾部插入方法
elifpos>self.length()-1:
self.append(item)
#否则插入位置就是链表中间
else:
index=0#设置计数器，用于标记我们后移了多少步
cur=self.__head#cur标记当前所在位置
#让index每次自增1，cur后移，当index=pos-1的时候说明cur在要插入位置的前一个元素，这时候停下
whileindex
运行结果：

False

0

True

True

55

0

False

3

15436

5

1543

False

154355

各种数据结构主要是思想，不同的人实现方式都不一定一样，同一个人多次实现也不一定一样。所以以上代码仅供参考~
如果有更简洁的方式，欢迎大家批评指正哦~
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。

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

热门推荐

随机推荐