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

上代码！

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

									# -*- 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 < pos - 1 :

									    index += 1

									    cur = cur.next

									   #跳出循环，cur在要插入位置的前一个元素，将node插入到cur的后面

									   node = Node(item) #新建一个节点

									   node.next = cur.next #node的后继设为cur的后继

									   node.prev = cur #node的前驱设为cur

									   cur.next.prev = node #cur后继的前驱改为node

									   cur.next = node #cur后继改为node

									 #删除节点操作

									 def remove(self,item):

									  #如果链表为空 直接不操作

									  if self.is_empty():

									   return

									  #链表不为空

									  else:

									   cur = self.__head #临时变量标记位置，从头开始

									   #如果头结点就是 要删除的元素

									   if cur.item == item:

									    #如果只有一个节点 链表就空了 head设为None

									    if self.length() == 1:

									     self.__head = None

									    #如果多个元素

									    else:

									     self.__head = cur.next #头指针指向cur的下一个

									     cur.next.prev= cur.prev #cur后继的前驱改为cur的前驱

									     cur.prev.next = cur.next #cur前驱的后继改为cur的后继

									   #否则 头节点不是要删除的节点 我们要向下遍历

									   else:

									    cur = cur.next #把cur后移一个节点

									    #循环让cur后移一直到链表尾元素位置，期间如果找得到就删除节点，找不到就跳出循环，

									    while cur is not self.__head:

									     #找到了元素cur就是要删除的

									     if cur.item == item:

									      cur.prev.next = cur.next #cur的前驱的后继改为cur的后继

									      cur.next.prev = cur.prev #cur的后继的前驱改为cur的前驱

									     cur = cur.next

									 #搜索节点是否存在

									 def search(self , item):

									  #如果链表是空的一定不存在

									  if self.is_empty():

									   return False

									  #否则链表不空

									  else:

									   cur = self.__head #设置临时cur从头开始

									   # cur不断后移，一直到尾节点为止

									   while cur.next is not self.__head:

									    #如果期间找到了就返回一个True 结束运行

									    if cur.item == item:

									     return True

									    cur = cur.next

									   # 从循环跳出来cur就指向了尾元素 看一下为元素是不是要找的 是就返回True

									   if cur.item ==item:

									    return True

									   #所有元素都不是 就返回False 没找到

									   return False

									if __name__ == "__main__":

									 dlcl = DoubleCircleLinkList()

									 print(dlcl.search(7))

									 dlcl.travel()

									 dlcl.remove(1)

									 print(dlcl.length())

									 print(dlcl.is_empty())

									 dlcl.append(55)

									 print(dlcl.search(55))

									 dlcl.travel()

									 dlcl.remove(55)

									 dlcl.travel()

									 print(dlcl.length())

									 dlcl.add(3)

									 print(dlcl.is_empty())

									 dlcl.travel()

									 dlcl.add(4)

									 dlcl.add(5)

									 dlcl.append(6)

									 dlcl.insert(-10,1)

									 dlcl.travel()

									 print(dlcl.length())

									 dlcl.remove(6)

									 dlcl.travel()

									 print(dlcl.search(7) )

									 dlcl.append(55)

									 dlcl.travel()