Python双向链表、循环链表、栈

一、双向链表

1.作用

双向链表也叫双面链表。

对于单向链表而言。只能通过头节点或者第一个节点出发，单向的访问后继节点，每个节点只能记录其后继节点的信息（位置），不能向前遍历。

所以引入双向链表，双向链表可以保持单向链表特点的基础上，让每个节点，既能向后访问后继节点，也可以向前访问前驱节点。

2.节点和链表类的定义

双向链表的链接域有prior记录前驱节点，next记录后继节点

#定义节点类的类型
class Node:#显性定义出构造函数def __init__(self,data):self.data = data #普通节点的数据域self.next = None #保存下一个节点的链接域self.prior = None #保存前一个节点饿链接域#定义双向链表的类的类型
class DoubleLink:#定义构造函数def __init__(self,node = None):self.head = node #头结点的head初始化为Noneself.size = 0 #链表的初始长度为0

3.双向链表的相关操作（判空、头插、遍历、插入、删除、查找） 

#定义节点类的类型
class Node:#显性定义出构造函数def __init__(self,data):self.data = data #普通节点的数据域self.next = None #保存下一个节点的链接域self.prior = None #保存前一个节点饿链接域#定义双向链表的类的类型
class DoubleLink:#定义构造函数def __init__(self,node = None):self.head = node #头结点的head初始化为Noneself.size = 0 #链表的初始长度为0#判空def is_empty(self):return self.head == None# return self.size == 0#头插def add_head(self,data):#创建出一个新的节点node = Node(data)#判断链表是否为空 分为空和非空情况if self.is_empty():self.head = nodeelse:node.next = self.headself.head.prior = node #node.next.prior = nodeself.head = node#插入成功 链表长度自增self.size += 1#遍历def show(self):#判空if self.is_empty():print("链表为空 遍历失败")else:q = self.headwhile q:print("%d "%(q.data),end = " ")q = q.nextprint()#任意位置插入def add_index(self,idex,data):#判断插入的位置是否合理if idex<1 or idex>self.size+1:print("插入失败")else:#判断插入的位置是否是第一个位置if idex == 1:self.add_head(data)else:#创建新的节点node = Node(data)#找到要插入位置的前一个节点q = self.headi=1while i<idex-1:q = q.nexti+=1# 判断插入的位置是否是最后一个节点if q.next == None:  # 如果为真 则插入的是最后一个位置q.next = nodenode.prior = qelse:  # 说明插入不是最后一个node.next = q.nextnode.prior = qq.next.prior = nodeq.next = node#插入成功 链表长度自增self.size += 1#任意位置删除def del_idex(self,idex):#判空  判断位置是否合理：if self.is_empty() or idex<1 or idex>self.size:print("删除失败")else:#判断删除的是否是第一个节点if idex == 1:self.head = self.head.nextself.head.prior = Noneelse:#判断删除的是否是最后一节节点q = self.headi = 1while i<idex:q = q.nexti+=1if q.next:#删除的不是最后一个节点q.prior.next = q.nextq.next.prior = q.priorelse:#删除的是最后一个q.prior.next = None#删除成功 链表长度自减self.size -= 1#查找节点是否存在 按值def find_node(self,data):#判空if self.is_empty():print("查询失败")else:p = self.headwhile p:if p.data == data:return Truep=p.nextreturn False#测试
if __name__ == "__main__":#创建一个双向链表doubleLink = DoubleLink()#头插doubleLink.add_head(10)doubleLink.add_head(20)doubleLink.add_head(30)doubleLink.add_head(40)doubleLink.add_head(50)#遍历doubleLink.show()#任意位置插入doubleLink.add_index(1,33)doubleLink.show()doubleLink.add_index(3, 999)doubleLink.show()doubleLink.add_index(8, 1111)doubleLink.show()#任意位置删除doubleLink.del_idex(1)doubleLink.show()doubleLink.del_idex(4)doubleLink.show()doubleLink.del_idex(6)doubleLink.show()if(doubleLink.find_node(40)):print("存在")

二、循环链表

1.概念

循环链表：就是首尾相连的链表，通过任意一个节点，都能将整个链表遍历一遍

分类：单向循环链表、双向循环链表

2.单向循环链表

单向循环链表也就是单向链表的最后一个节点的next域不再为None,而是第一个节点

3.单向循环链表的操作（创建、判空、尾插、遍历、删除）

#封装节点的类
class Node:def __init__(self,data):self.data = dataself.next = None#封装单向循环链表类
class LinkList:def __init__(self,node = None):self.size = 0self.head = node#判空def is_empty(self):return self.size == 0#return self.head == None#尾插def add_tail(self,data):#创建一个新的节点node = Node(data)#判空if self.is_empty():self.head = nodenode.next = nodeelse:#找到最后一个节点q = self.headwhile q.next != self.head:q = q.nextq.next = nodenode.next = self.head#链表长度自增self.size += 1#遍历def show(self):#判空if self.is_empty():print("失败")else:#两种： 长度遍历   位置遍历（循环结束 多打印一次）q = self.headwhile q.next != self.head:print("%d"%(q.data),end=" ")q = q.nextprint("%d"%(q.data),end=" ")print()#尾删def del_tail(self):#判空if self.is_empty():print("删除失败")else:#判断长度是否为1  是否只有一个节点if self.size == 1:self.head = Noneelse:q = self.headi=1while i<self.size-1:q = q.nexti+=1q.next = self.head#删除成功 链表长度自减self.size -=1
#测试
if __name__ == "__main__":#创建一个单向循环链表linkList = LinkList()#尾插linkList.add_tail(1)linkList.add_tail(2)linkList.add_tail(3)linkList.add_tail(4)linkList.add_tail(5)#显示linkList.show()#尾删linkList.del_tail()linkList.show()linkList.del_tail()linkList.show()linkList.del_tail()linkList.show()linkList.del_tail()linkList.show()linkList.del_tail()linkList.show()

三、栈

1.概念

栈的概念：操作受限的线性表，对数据的插入和删除操作只能在同一端操作

栈的特点：先进后出（FILO ---->First In Last Out） 、后进先出（LIFO ---->Last In First Out）

栈顶：能够被操作的一端称为栈顶

栈底：不能被操作的一端，称为栈底

种类：顺序栈、链式栈

基本操作：创建栈、判空、入栈、出栈、获取栈顶元素、求栈的大小、遍历栈

2.顺序栈

顺序存储的栈 叫顺序栈

3.顺序栈的操作

#封装一个栈的类
class Stack:def __init__(self):self.data = [] #使用列表来完成顺序栈#判空def is_empty(self):return self.data == []#增加数据def push(self,value):self.data.insert(0,value)#遍历def show(self):for i in self.data:print(i, end=" ")print()#弹出元素 删除def pop(self):#self.data.remove(self.data[0])#self.data.pop(0)del self.data[0]#获取栈顶元素def first_value(self):return self.data[0]#返回栈的大小def size(self):return len(self.data)#测试
if __name__ == "__main__":#创建一个栈stack = Stack()#增加元素stack.push("hello")stack.push("world")stack.push("hello")stack.push("meimei")#遍历stack.show()#删除stack.pop()# 遍历stack.show()num = stack.first_value()print(num)size = stack.size()print(size)

四、自行拓展双向循环链表和链式栈

1.双向循环链表

class Node:def __init__(self,data):self.data=dataself.next=Noneself.prior = Noneclass DoubleCirculateLinklist:def __init__(self):self.size = 0self.head = None# 判空def is_empty(self):return self.size==0# 尾插def add_tail(self, value):node = Node(value)  # 创建新节点if self.is_empty():self.head = node  # 如果链表为空，头结点指向新节点node.next = node  # 新节点指向自己，形成循环node.prior = node  # 新节点的前驱指向自己else:tail = self.head.prior  # 找到当前尾节点tail.next = node  # 当前尾节点的下一个指向新节点node.prior = tail  # 新节点的前驱指向当前尾节点node.next = self.head  # 新节点的后继指向头结点self.head.prior = node  # 头结点的前驱指向新节点self.size += 1  # 链表长度自增#遍历def show(self):if self.is_empty():returnelse:q=self.headwhile True:print(f"{q.data}",end=" ")q=q.nextif q==self.head:breakprint()#尾删def del_tail(self):if self.is_empty():returnelif self.size==1:self.head = Noneelse:tail = self.head.prior  # 找到当前尾节点tail.prior.next = self.head  # 当前尾节点的前一个节点的后继指向头结点self.head.prior = tail.prior  # 头结点的前驱指向当前尾节点的前一个节点self.size -= 1  # 链表长度自减if __name__=='__main__':ls=DoubleCirculateLinklist()ls.add_tail(1)ls.add_tail(2)ls.add_tail(3)ls.show()ls.del_tail()ls.del_tail()ls.show()

2.链式栈

class Node:def __init__(self, data):self.data = data  # 节点的数据域self.next = None  # 指向下一个节点的指针class LinkedStack:def __init__(self):self.top = None  # 栈顶指针self.size = 0    # 栈的大小def is_empty(self):return self.size == 0def push(self, value):new_node = Node(value)  # 创建新节点new_node.next = self.top  # 新节点指向当前栈顶self.top = new_node  # 更新栈顶为新节点self.size += 1  # 栈的大小自增def pop(self):if self.is_empty():print("栈为空，无法出栈")return Nonetop_value = self.top.data  # 获取栈顶元素self.top = self.top.next  # 更新栈顶为下一个节点self.size -= 1  # 栈的大小自减return top_value  # 返回出栈的元素def find_top(self):if self.is_empty():print("栈为空，无法查看栈顶元素")return Nonereturn self.top.data  # 返回栈顶元素def show(self):if self.is_empty():print("栈为空")returnq = self.topwhile q:print(q.data, end=" ")q = q.nextprint()  # 换行# 示例代码
if __name__ == "__main__":stack = LinkedStack()stack.push(10)stack.push(20)stack.push(30)stack.show()  print("栈顶元素:", stack.find_top())  print("出栈元素:", stack.pop())  stack.show()