在Python中，链表（Linked List）是一种重要的数据结构，它由一系列节点（Node）组成，每个节点包含数据和指向下一个节点的指针。链表相较于数组（List）具有动态分配内存和高效插入/删除操作的优点。链表通常用于需要频繁插入和删除操作的场合。
下面，我们将通过定义一个链表节点类ListNode来具体说明链表的构造。
链表节点类的定义
首先，我们需要定义一个节点类ListNode，该类至少包含两个属性：value（节点存储的值）和next（指向下一个节点的指针）。以下是ListNode的实现代码：
class ListNode:
def __init__(self, value=0, next=None):
self.value = value # 节点存储的值
self.next = next # 指向下一个节点的指针
在上述代码中，__init__方法用于初始化节点的值和指针。在创建节点对象时，可以选择性地提供下一节点的引用，默认为None。
链表的基本操作
接下来，我们可以实现一些基本的链表操作，例如插入、删除节点和遍历链表。下面是一个简单的链表类LinkedList的实现：
class LinkedList:
def __init__(self):
self.head = None # 初始化链表时，头节点为None
def append(self, value):
"""在链表末尾添加新节点"""
new_node = ListNode(value)
if not self.head: # 如果链表为空，直接将新节点设为头节点
self.head = new_node
return
current = self.head
while current.next: # 遍历到链表末尾
current = current.next
current.next = new_node # 将新节点添加到链表末尾
def delete(self, value):
"""删除链表中指定值的节点"""
if not self.head: # 如果链表为空
return
if self.head.value == value: # 如果头节点就是要删除的节点
self.head = self.head.next
return
current = self.head
while current.next: # 遍历链表，查找要删除的节点
if current.next.value == value:
current.next = current.next.next # 删除节点
return
current = current.next
def display(self):
"""遍历链表，输出每个节点的值"""
current = self.head
while current:
print(current.value, end=' -> ')
current = current.next
print('None')
# 使用示例
if __name__ == "__main__":
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.display() # 输出: 1 -> 2 -> 3 -> None
ll.delete(2)
ll.display() # 输出: 1 -> 3 -> None
解释代码
-
链表的初始化：在
LinkedList类中，head属性用于指向链表的头节点，初始值为None。 -
添加节点：
append方法用于在链表末尾添加新节点。如果链表为空，直接将新节点设为头节点；否则，我们遍历链表找到末尾节点，并将新节点链接到该末尾节点。 -
删除节点：
delete方法接受一个值，如果该值的节点存在于链表中，则执行删除操作。我们需要处理两种情况：删除的节点是头节点和删除的节点是非头节点。 -
遍历链表：
display方法用于打印出链表中所有节点的值，方便我们直观地查看链表的结构。
总结
通过上述代码，我们实现了一个简单的单向链表。链表在很多场合中都是非常有用的，尤其在需要动态内存分配和频繁修改数据结构的应用中，更是展现了其强大的优势。掌握链表的相关操作是理解更复杂数据结构和算法的基础。希望通过这篇文章，读者能对链表有一个初步的理解和认识。
