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.next current.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: # 如果位置小于等于0 self.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 不是 None current.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指向当前节点的next if 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 # 找到数据，返回True current = 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.next current.next = new_node # 最后一个节点的下一个指向新节点 new_node.prev = current # 新节点的前一个指向最后一个节点 def insert(self, pos, data): # 在指定位置插入新节点 if pos >= self.length(): # 如果位置超出范围 self.append(data) # 添加到尾部 elif pos <= 0: # 如果位置小于等于0 self.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 不是 None current.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指向当前节点的next if 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 # 找到数据，返回True current = current.next # 移动到下一个节点 return False # 遍历完成未找到数据，返回False if __name__ == '__main__': linklist = LinkList() # 创建链表实例 linklist.add(10) # 添加节点10 linklist.add(20) # 添加节点20 linklist.append(100) # 在尾部添加节点100 linklist.add(30) # 添加节点30 linklist.add(40) # 添加节点40 linklist.insert(3, 505) # 在位置3插入节点505 print(linklist.length()) # 输出链表长度 print('*****************') linklist.travel() # 遍历链表并打印节点数据 二、循环链表

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

class Node: def __init__(self, data): # 初始化节点，包含数据和指向下一个节点的指针 self.data = data self.next = None self.prev = None class LinkList: def __init__(self): # 初始化链表，头指针指向第一个节点（默认为None） self.__head = None def is_empty(self): # 检查链表是否为空 return self.__head is None def length(self): # 计算链表的长度 if self.is_empty(): return 0 current = self.__head count = 1 # 从头节点开始计数 while current.next != self.__head: # 遍历到回到头节点 count += 1 current = current.next return count def travel(self): # 遍历链表并打印每个节点的数据 if self.is_empty(): return current = self.__head while True: print(current.data) current = current.next if current == self.__head: # 回到头节点时停止 break def add(self, data): # 在链表头部添加新节点 new_node = Node(data) if self.is_empty(): self.__head = new_node new_node.next = new_node # 指向自己，形成循环 new_node.prev = new_node # 指向自己，形成循环 else: new_node.next = self.__head new_node.prev = self.__head.prev self.__head.prev.next = new_node # 更新旧头节点的前一个节点的next 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 new_node.next = new_node # 指向自己，形成循环 new_node.prev = new_node # 指向自己，形成循环 else: tail = self.__head.prev # 找到尾节点 tail.next = new_node new_node.prev = tail new_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.__head count = 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(): return current = self.__head while True: if current.data == data: if current == self.__head and current.next == self.__head: self.__head = None # 只有一个节点的情况 else: current.prev.next = current.next # 前一个节点的next指向当前节点的next current.next.prev = current.prev # 后一个节点的prev指向当前节点的prev if current == self.__head: # 如果是头节点，更新头指针 self.__head = current.next break current = current.next if current == self.__head: # 遍历完成未找到数据 break def search(self, data): # 查找链表中是否存在指定数据 if self.is_empty(): return False current = self.__head while True: if current.data == data: return True # 找到数据，返回True current = current.next if current == self.__head: # 遍历完成未找到数据 break return False # 返回False 三、思维导图