Python----数据结构（双向链表：节点，是否为空，长度，遍历，添加，删除，查找，循环链表）

一、双向链表

1.1、概念

双向链表是一种链表数据结构，每个节点除了包含指向下一个节点的指针外，还包含指向前一个节点的指针。这种特性使得在双向链表中，可以从任意一个节点开始，向前或向后遍历链表。

1.2、特点

• 既可以从头遍历到尾, 又可以从尾遍历到头，也就是链表相连的过程是双向的。

• 一个节点既有向前连接的引用, 也有一个向后连接的引用。

• 双向链表可以有效的解决单向链表中提到的问题。

1.3、双向链表的基本操作

1.3.1、节点的创建

class Node:def __init__(self, data):# 初始化节点，包含数据和指向下一个节点和前一个节点的指针self.data = data  # 节点存储的数据self.next = None  # 指向下一个节点的指针self.prev = None  # 指向前一个节点的指针

1.3.2、初始化双向链表

    def __init__(self, node=None):# 初始化链表，头指针指向第一个节点（默认为None）self.__head = node  # 链表的头节点

1.3.3、is_empty()链表是否为空

    def is_empty(self):# 检查链表是否为空return self.__head is None  # 如果头节点为None，则链表为空

1.3.4、length()链表长度

    def length(self):# 计算链表的长度current = self.__head  # 从头节点开始count = 0  # 初始化计数器while current is not None:  # 遍历链表count += 1  # 计数器加一current = current.next  # 移动到下一个节点return count  # 返回链表的长度

1.3.5、travel()遍历整个链表

    def travel(self):# 遍历链表并打印每个节点的数据current = self.__head  # 从头节点开始while current is not None:  # 遍历链表print(current.data)  # 打印当前节点的数据current = current.next  # 移动到下一个节点

1.3.6、add(data)链表头部添加元素

    def add(self, data):# 在链表头部添加新节点new_node = Node(data)  # 创建新节点if self.is_empty():  # 如果链表为空self.__head = new_node  # 头节点指向新节点else:new_node.next = self.__head  # 新节点的下一个指向当前头节点self.__head.prev = new_node  # 当前头节点的前一个指向新节点self.__head = new_node  # 更新头节点为新节点

1.3.7、append(data)链表尾部添加元素

    def append(self, data):# 在链表尾部添加新节点new_node = Node(data)  # 创建新节点if self.is_empty():  # 如果链表为空self.__head = new_node  # 头节点指向新节点else:current = self.__head  # 从头节点开始while current.next is not None:  # 遍历到链表的最后一个节点current = current.nextcurrent.next = new_node  # 最后一个节点的下一个指向新节点new_node.prev = current  # 新节点的前一个指向最后一个节点

1.3.8、insert(pos, data)指定位置添加元素

    def insert(self, pos, data):# 在指定位置插入新节点if pos >= self.length():  # 如果位置超出范围self.append(data)  # 添加到尾部elif pos <= 0:  # 如果位置小于等于0self.add(data)  # 添加到头部else:new_node = Node(data)  # 创建新节点current = self.__head  # 从头节点开始count = 0# 遍历到插入新节点的位置while count < pos:current = current.next  # 移动到下一个节点count += 1# 在正确的位置插入新节点new_node.prev = current.prev  # 新节点的前一个指向当前节点的前一个new_node.next = current  # 新节点的下一个指向当前节点if current.prev:  # 确保 current.prev 不是 Nonecurrent.prev.next = new_node  # 前一个节点的下一个指向新节点current.prev = new_node  # 当前节点的前一个指向新节点

1.3.9、remove(data)删除节点

    def remove(self, data):# 移除链表中指定数据的节点current = self.__head  # 从头节点开始pre = None  # 用于跟踪当前节点的前一个节点while current is not None:  # 遍历链表if current.data == data:  # 找到要删除的节点if current == self.__head:  # 如果是头节点self.__head = current.next  # 更新头指针if self.__head:  # 如果新的头节点不为空self.__head.prev = None  # 更新新头节点的前一个指针else:pre.next = current.next  # 将前一个节点的next指向当前节点的nextif current.next:  # 如果当前节点的下一个节点不为空current.next.prev = pre  # 更新下一个节点的前一个指针break  # 找到并删除后退出循环else:pre = current  # 移动前一个节点指针current = current.next  # 移动到下一个节点

1.3.10、search(data) 查找节点是否存在

    def search(self, data):# 查找链表中是否存在指定数据current = self.__head  # 从头节点开始while current is not None:  # 遍历链表if current.data == data:  # 找到数据return True  # 找到数据，返回Truecurrent = current.next  # 移动到下一个节点return False  # 遍历完成未找到数据，返回False

完整代码

class Node:def __init__(self, data):# 初始化节点，包含数据和指向下一个节点和前一个节点的指针self.data = data  # 节点存储的数据self.next = None  # 指向下一个节点的指针self.prev = None  # 指向前一个节点的指针class LinkList:def __init__(self, node=None):# 初始化链表，头指针指向第一个节点（默认为None）self.__head = node  # 链表的头节点def is_empty(self):# 检查链表是否为空return self.__head is None  # 如果头节点为None，则链表为空def length(self):# 计算链表的长度current = self.__head  # 从头节点开始count = 0  # 初始化计数器while current is not None:  # 遍历链表count += 1  # 计数器加一current = current.next  # 移动到下一个节点return count  # 返回链表的长度def travel(self):# 遍历链表并打印每个节点的数据current = self.__head  # 从头节点开始while current is not None:  # 遍历链表print(current.data)  # 打印当前节点的数据current = current.next  # 移动到下一个节点def add(self, data):# 在链表头部添加新节点new_node = Node(data)  # 创建新节点if self.is_empty():  # 如果链表为空self.__head = new_node  # 头节点指向新节点else:new_node.next = self.__head  # 新节点的下一个指向当前头节点self.__head.prev = new_node  # 当前头节点的前一个指向新节点self.__head = new_node  # 更新头节点为新节点def append(self, data):# 在链表尾部添加新节点new_node = Node(data)  # 创建新节点if self.is_empty():  # 如果链表为空self.__head = new_node  # 头节点指向新节点else:current = self.__head  # 从头节点开始while current.next is not None:  # 遍历到链表的最后一个节点current = current.nextcurrent.next = new_node  # 最后一个节点的下一个指向新节点new_node.prev = current  # 新节点的前一个指向最后一个节点def insert(self, pos, data):# 在指定位置插入新节点if pos >= self.length():  # 如果位置超出范围self.append(data)  # 添加到尾部elif pos <= 0:  # 如果位置小于等于0self.add(data)  # 添加到头部else:new_node = Node(data)  # 创建新节点current = self.__head  # 从头节点开始count = 0# 遍历到插入新节点的位置while count < pos:current = current.next  # 移动到下一个节点count += 1# 在正确的位置插入新节点new_node.prev = current.prev  # 新节点的前一个指向当前节点的前一个new_node.next = current  # 新节点的下一个指向当前节点if current.prev:  # 确保 current.prev 不是 Nonecurrent.prev.next = new_node  # 前一个节点的下一个指向新节点current.prev = new_node  # 当前节点的前一个指向新节点def remove(self, data):# 移除链表中指定数据的节点current = self.__head  # 从头节点开始pre = None  # 用于跟踪当前节点的前一个节点while current is not None:  # 遍历链表if current.data == data:  # 找到要删除的节点if current == self.__head:  # 如果是头节点self.__head = current.next  # 更新头指针if self.__head:  # 如果新的头节点不为空self.__head.prev = None  # 更新新头节点的前一个指针else:pre.next = current.next  # 将前一个节点的next指向当前节点的nextif current.next:  # 如果当前节点的下一个节点不为空current.next.prev = pre  # 更新下一个节点的前一个指针break  # 找到并删除后退出循环else:pre = current  # 移动前一个节点指针current = current.next  # 移动到下一个节点def search(self, data):# 查找链表中是否存在指定数据current = self.__head  # 从头节点开始while current is not None:  # 遍历链表if current.data == data:  # 找到数据return True  # 找到数据，返回Truecurrent = current.next  # 移动到下一个节点return False  # 遍历完成未找到数据，返回Falseif __name__ == '__main__':linklist = LinkList()  # 创建链表实例linklist.add(10)  # 添加节点10linklist.add(20)  # 添加节点20linklist.append(100)  # 在尾部添加节点100linklist.add(30)  # 添加节点30linklist.add(40)  # 添加节点40linklist.insert(3, 505)  # 在位置3插入节点505print(linklist.length())  # 输出链表长度print('*****************')linklist.travel()  # 遍历链表并打印节点数据

二、循环链表

循环链表是一种特殊的链表，其最后一个节点的指针不是指向None，而是指向链表的头节点。这样就形成了一个环形结构。

class Node:def __init__(self, data):# 初始化节点，包含数据和指向下一个节点的指针self.data = dataself.next = Noneself.prev = Noneclass LinkList:def __init__(self):# 初始化链表，头指针指向第一个节点（默认为None）self.__head = Nonedef is_empty(self):# 检查链表是否为空return self.__head is Nonedef length(self):# 计算链表的长度if self.is_empty():return 0current = self.__headcount = 1  # 从头节点开始计数while current.next != self.__head:  # 遍历到回到头节点count += 1current = current.nextreturn countdef travel(self):# 遍历链表并打印每个节点的数据if self.is_empty():returncurrent = self.__headwhile True:print(current.data)current = current.nextif current == self.__head:  # 回到头节点时停止breakdef add(self, data):# 在链表头部添加新节点new_node = Node(data)if self.is_empty():self.__head = new_nodenew_node.next = new_node  # 指向自己，形成循环new_node.prev = new_node  # 指向自己，形成循环else:new_node.next = self.__headnew_node.prev = self.__head.prevself.__head.prev.next = new_node  # 更新旧头节点的前一个节点的nextself.__head.prev = new_node  # 更新头节点的前一个指向新节点self.__head = new_node  # 更新头节点为新节点def append(self, data):# 在链表尾部添加新节点new_node = Node(data)if self.is_empty():self.__head = new_nodenew_node.next = new_node  # 指向自己，形成循环new_node.prev = new_node  # 指向自己，形成循环else:tail = self.__head.prev  # 找到尾节点tail.next = new_nodenew_node.prev = tailnew_node.next = self.__head  # 新节点的next指向头节点self.__head.prev = new_node  # 更新头节点的前一个指向新节点def insert(self, pos, data):# 在指定位置插入新节点if pos >= self.length():  # 使用 >= 来处理追加到末尾的情况self.append(data)  # 如果位置超出范围，添加到尾部elif pos <= 0:self.add(data)  # 如果位置小于等于0，添加到头部else:new_node = Node(data)current = self.__headcount = 0# 遍历到插入新节点的位置while count < pos:current = current.next  # 移动到下一个节点count += 1# 在正确的位置插入新节点new_node.prev = current.prev  # 新节点的前一个指向当前节点的前一个new_node.next = current  # 新节点的下一个指向当前节点# 更新周围节点的指针current.prev.next = new_node  # 前一个节点的next指向新节点current.prev = new_node  # 当前节点的前一个指向新节点def remove(self, data):# 移除链表中指定数据的节点if self.is_empty():returncurrent = self.__headwhile True:if current.data == data:if current == self.__head and current.next == self.__head:self.__head = None  # 只有一个节点的情况else:current.prev.next = current.next  # 前一个节点的next指向当前节点的nextcurrent.next.prev = current.prev  # 后一个节点的prev指向当前节点的previf current == self.__head:  # 如果是头节点，更新头指针self.__head = current.nextbreakcurrent = current.nextif current == self.__head:  # 遍历完成未找到数据breakdef search(self, data):# 查找链表中是否存在指定数据if self.is_empty():return Falsecurrent = self.__headwhile True:if current.data == data:return True  # 找到数据，返回Truecurrent = current.nextif current == self.__head:  # 遍历完成未找到数据breakreturn False  # 返回False