一、链表
链表是一种线性数据结构，由一系列按特定顺序排列的节点组成，这些节点通过指针相互连接。每个节点包含两部分：元素和指向下一个节点的指针。其中，最简单的形式是单向链表，每个节点含有一个信息域和一个指针域，该指针指向链表中的下一个节点，最后一个节点则指向一个空值。
1.1、Python中的链表
• 大部分都是用C语言实现链表，因为C有指针，可以很方便的控制内存，很轻易就可以实现链 表，在C/C++中，通常采用“指针+结构体”来实现链表。
• Python是一门动态语言，可以直接把对象赋值给新的变量，我们采用“引用+类”来实现 链表。
• 结构：data为自定义的数据，next为下一个节点的地址。
• 链表的种类：单向链表、双向链表、单向循环链表、双向循环链表。
1.2、基本元素
节点：每个节点有两个部分，左边称为值域，存放用户数据；右边部分称为指针域，用来存 放指向下一个元素的指针。
Head：head节点永远指向第一个节点。
Tail：tail节点永远指向最后一个节点。
None：链表中最后一个节点的指针域为None。
二、基本操作
2.1、节点的创建
class Node:
def __init__(self, data):
# 初始化节点，包含数据和指向下一个节点的指针
self.data = data
self.next = None 
2.2、初始化单向链表
class LinkList:
def __init__(self, node=None):
# 初始化链表，头指针指向第一个节点（默认为None）
self.__head = node2.3、判断是否为空
def is_empty(self):
# 检查链表是否为空
return self.__head == None2.4、链表长度
def length(self):
# 计算链表的长度
current = self.__head
count = 0
while current != None:
count += 1
current = current.next
return count2.5、遍历链表
def travel(self):
# 遍历链表并打印每个节点的数据
current = self.__head
while current != None:
print(current.data)
current = current.next2.4、插入节点
2.4.1、头节点
def add(self, data):
# 在链表头部添加新节点
new_node = Node(data)
new_node.next = self.__head
self.__head = new_node
2.4.2、中间节点
def insert(self, pos, data):
# 在指定位置插入新节点
if pos > self.length() - 1:
self.append(data) # 如果位置超出范围，添加到尾部
elif pos <= 0:
self.add(data) # 如果位置小于等于0，添加到头部
else:
new_node = Node(data)
pre = self.__head
count = 0
while count < pos - 1:
count += 1
pre = pre.next
new_node.next = pre.next # 将新节点的next指向当前节点的next
pre.next = new_node # 将前一个节点的next指向新节点
2.4.3、尾节点
def append(self, data):
# 在链表尾部添加新节点
new_node = Node(data)
if self.is_empty():
self.__head = new_node
else:
current = self.__head
while current.next != None:
current = current.next
current.next = new_node
2.5、删除节点
def remove(self, data):
# 移除链表中指定数据的节点
current = self.__head
pre = None
while current != None:
if current.data == data:
if current == self.__head:
self.__head = current.next # 如果是头节点，更新头指针
else:
pre.next = current.next # 将前一个节点的next指向当前节点的next
break
else:
pre = current
current = current.next
2.6、查找节点
def serch(self, data):
# 查找链表中是否存在指定数据
current = self.__head
while current != None:
if current.data == data:
return True # 找到数据，返回True
else:
current = current.next
return False # 遍历完成未找到数据，返回False三、链表的特点
1、动态数据集合：链表允许动态的添加和删除元素，这使得它们在处理未知数量或频繁变 化的数据集时非常有用。
2、元素顺序：链表可以按照插入顺序来保持元素的顺序，这对于需要维护元素插入顺序的 应用程序非常有用。
3、 内存效率：与数组相比，链表在内存使用上更为高效，因为它们不需要连续的内存空间。 链表通过节点之间的指针来连接元素，这样可以更有效地利用内存空间。
4、避免数组扩容：数组在初始化时需要指定大小，如果超出大小，则需要扩容，这是一个 昂贵的操作。链表则可以避免这个问题，因为它们可以动态地增长。
四、单向链表的缺点
1、只能从头遍历到尾或者从尾遍历到头(一般从头到尾)。
2、链表相连的过程是单向的。实现的原理是上一个链表中有一个指向下一个的引用。
3、 我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的。但是, 在实际开发中, 经 常会遇到需要回到上一个节点的情况。
举个例子:
假设一个文本编辑用链表来存储文本。每一行用一个String对象存储在链表的 一个节点中。当编辑器用户向下移动光标时, 链表直接操作到下一个节点即可。但是当用 于将光标向上移动呢? 这个时候为了回到上一个节点, 我们可能需要从头开始, 依次走到 想要的节点上。
五、完整代码
class Node:
def __init__(self, data):
# 初始化节点，包含数据和指向下一个节点的指针
self.data = data
self.next = None
class LinkList:
def __init__(self, node=None):
# 初始化链表，头指针指向第一个节点（默认为None）
self.__head = node
def is_empty(self):
# 检查链表是否为空
return self.__head == None
def length(self):
# 计算链表的长度
current = self.__head
count = 0
while current != None:
count += 1
current = current.next
return count
def travel(self):
# 遍历链表并打印每个节点的数据
current = self.__head
while current != None:
print(current.data)
current = current.next
def add(self, data):
# 在链表头部添加新节点
new_node = Node(data)
new_node.next = self.__head
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 != None:
current = current.next
current.next = new_node
def insert(self, pos, data):
# 在指定位置插入新节点
if pos > self.length() - 1:
self.append(data) # 如果位置超出范围，添加到尾部
elif pos <= 0:
self.add(data) # 如果位置小于等于0，添加到头部
else:
new_node = Node(data)
pre = self.__head
count = 0
while count < pos - 1:
count += 1
pre = pre.next
new_node.next = pre.next # 将新节点的next指向当前节点的next
pre.next = new_node # 将前一个节点的next指向新节点
def remove(self, data):
# 移除链表中指定数据的节点
current = self.__head
pre = None
while current != None:
if current.data == data:
if current == self.__head:
self.__head = current.next # 如果是头节点，更新头指针
else:
pre.next = current.next # 将前一个节点的next指向当前节点的next
break
else:
pre = current
current = current.next
def serch(self, data):
# 查找链表中是否存在指定数据
current = self.__head
while current != None:
if current.data == data:
return True # 找到数据，返回True
else:
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
print(linklist.is_empty()) # 检查链表是否为空
print(linklist.length()) # 输出链表长度
print('*****************')
linklist.remove(30) # 移除节点30
# linklist.travel() # 遍历链表并打印节点数据
print(linklist.serch(40)) # 查找节点40是否存在
# linklist.travel() # 遍历链表并打印节点数据六、思维导图
