一、双向链表
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三、思维导图
详解)
快速入门实时数据湖存储系统Apache Paimon(3))
 getName() string {)
