链表是一种由节点组成的线性数据结构，每个节点包含一个数据元素和一个指向下一个节点的指针。
(1)节点定义
链表中的每一个元素都是一个节点，每个节点通常包含两部分：数据和下一个节点的引用。
class Node: def __init__(self, data): self.data = data # 节点存储的数据 self.next = None # 默认下一个节点为空(2)链表定义
链表通常有一个头节点来表示链表的开始。尾节点是链表中的最后一个节点，它的下一个节点引用为None。
class LinkedList: def __init__(self): self.head = None # 初始链表为空(1)在链表的开头添加元素
def add_first(self, data): new_node = Node(data) # 创建新的节点 new_node.next = self.head # 将新节点指向当前的头节点 self.head = new_node # 更新头节点为新节点LinkedList.add_first = add_first(2)在链表的结尾添加元素
def add_last(self, data): new_node = Node(data) if self.head is None: # 若链表为空，则直接将新节点设置为头节点 self.head = new_node return last_node = self.head # 遍历到链表的尾部 while last_node.next: last_node = last_node.next last_node.next = new_node # 在链表尾部添加新节点LinkedList.add_last = add_last(1)删除链表的第一个元素
def remove_first(self): if self.head: self.head = self.head.next # 更新头节点为下一个节点LinkedList.remove_first = remove_first(2)删除链表的最后一个元素
def remove_last(self): if self.head is None: # 若链表为空，直接返回 return if self.head.next is None: # 若链表只有一个元素，将头节点设置为空 self.head = None return second_to_last = self.head # 找到倒数第二个节点 while second_to_last.next.next: second_to_last = second_to_last.next second_to_last.next = None # 将倒数第二个节点的next设置为空，从而删除最后一个节点LinkedList.remove_last = remove_lastdef print_list(self): current_node = self.head # 从头节点开始遍历 while current_node: print(current_node.data, end=" -> ") current_node = current_node.next # 移动到下一个节点 print("None")LinkedList.print_list = print_listdef search(self, target): current_node = self.head # 从头节点开始遍历 while current_node: if current_node.data == target: # 若找到目标数据，返回True return True current_node = current_node.next # 移动到下一个节点 return False # 遍历完链表后，未找到目标数据，返回FalseLinkedList.search = search6.实战案例：反转链表一个常见的面试问题是如何反转链表。我们可以使用迭代的方法来解决这个问题。
def reverse(self): prev = None # 上一个节点 current = self.head # 当前节点 while current: next_node = current.next # 记录下一个节点 current.next = prev # 将当前节点指向上一个节点 prev = current # 更新上一个节点为当前节点 current = next_node # 移动到下一个节点 self.head = prev # 更新头节点LinkedList.reverse = reverse# 使用示例ll = LinkedList()ll.add_last(1)ll.add_last(2)ll.add_last(3)ll.print_list() # 输出：1 -> 2 -> 3 -> Nonell.reverse()ll.print_list() # 输出：3 -> 2 -> 1 -> None链表提供了一种在内存中存储有序元素的方法，它的主要优势在于插入和删除操作的效率高，不需要移动其他元素。不过，链表的随机访问速度比数组慢，因为需要从头节点开始遍历。理解链表的结构和常用操作是计算机科学基础，也经常用于面试中。
本文链接：http://www.28at.com/showinfo-26-12388-0.html五分钟搞懂链表实现：Python数据结构与算法
声明：本网页内容旨在传播知识，不代表本站观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。