一、双向链表
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
三、思维导图
