链表（Linked List）是一种动态数据结构，它允许我们在不需要预先知道元素数量的情况下添加或删除元素。链表中的元素称为节点（Node），每个节点包含数据和指向下一个节点的指针。链表可以分为单向链表、双向链表和循环链表等多种类型，但在这里我们将主要讨论单向链表的实现。
一、链表的基本概念
链表是一种线性数据结构，由一系列节点组成，每个节点包含两个部分：数据域（用于存储数据）和指针域（用于指向下一个节点）。链表的第一个节点称为头节点（Head Node），最后一个节点的指针域通常设置为空（NULL 或 None），表示链表的结束。链表与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针连接在一起。
二、链表的特点
1.动态分配：链表不需要预先分配固定大小的内存空间，可以根据需要动态地分配和释放内存。
2.非连续存储：链表中的元素在内存中不是连续存储的，而是通过指针连接在一起。这使得链表在插入和删除操作上具有更高的灵活性。
3.需要额外空间：链表中的每个节点都需要一个额外的指针域来存储下一个节点的地址，这会增加存储空间的开销。
三、链表的基本操作
1.创建链表：创建一个空链表或根据给定数据创建链表。
2.插入节点：在链表的指定位置插入一个新的节点。
3.删除节点：删除链表中的指定节点。
4.查找节点：根据节点的数据或位置查找链表中的指定节点。
5.遍历链表：从头节点开始依次访问链表中的每个节点，直到遍历到链表末尾。
四、链表的代码实现（以Python为例）
1. 定义节点类（Node）
首先，我们需要定义一个节点类来表示链表中的节点。每个节点包含一个数据域和一个指针域。
python复制代码
class Node: def __init__(self, data=None): self.data = data self.next = None
2. 定义链表类（LinkedList）
接下来，我们定义一个链表类来表示整个链表。链表类包含头节点和一系列基本操作。
python复制代码
class LinkedList: def __init__(self): self.head = None # 插入节点到链表末尾 def append(self, data): if not self.head: self.head = Node(data) else: current = self.head while current.next: current = current.next current.next = Node(data) # 插入节点到链表指定位置（索引从0开始） def insert(self, index, data): if index < 0: raise IndexError("Negative index") if not self.head and index != 0: raise IndexError("Index out of range") new_node = Node(data) if index == 0: new_node.next = self.head self.head = new_node else: current = self.head for _ in range(index - 1): if not current: raise IndexError("Index out of range") current = current.next new_node.next = current.next current.next = new_node # 删除指定位置的节点 def delete(self, index): if index < 0: raise IndexError("Negative index") if not self.head: raise IndexError("Index out of range") if index == 0: self.head = self.head.next else: current = self.head for _ in range(index - 1): if not current: raise IndexError("Index out of range") current = current.next if not current.next: raise IndexError("Index out of range") current.next = current.next.next # 查找指定数据的节点并返回其位置（如果不存在则返回-1） def search(self, data): current = self.head index = 0 while current: if current.data == data: return index current = current.next index += 1 return -1 # 遍历链表并打印节点数据 def display(self): current = self.head while current: print(current.data, end=" ") current = current.next print() # 使用
链表是一种线性数据结构，由一系列节点组成，每个节点包含两个部分：数据域（用于存储数据）和指针域（用于指向下一个节点）。
