链表的全面指南：结构、操作和复杂度分析 (链表完整程序)

文章编号：13941 / 分类：技术教程 / 更新时间：2024-07-02 18:12:27 / 浏览：次

链表是一种基本的数据结构，用于存储有序的数据，并且允许高效地插入和删除元素。

链表的结构

链表由一系列称为节点的元素组成。每个节点包含两个字段：

数据字段：存储实际数据。
指针字段：指向下一个节点或空（表示链表的末尾）。

一个链表通常使用一个头指针来引用第一个节点，以及一个尾指针来引用最后一个节点。头指针可以为空（表示空链表），而尾指针始终指向最后一个节点。

链表的操作

插入元素

插入元素到链表中可以在以下位置进行：

头部：在链表的开始处插入元素。
尾部：在链表的末尾插入元素。
中间：在两个现有节点之间插入元素。

删除元素

从链表中删除元素可以在以下位置进行：

头部：删除链表的第一个元素。
尾部：删除链表的最后一个元素。
中间：删除链表中两个给定节点之间的元素。

搜索元素

在链表中搜索元素涉及逐个遍历节点，并比较其数据字段与要查找的值。如果找到匹配项，则返回相应的节点。

复杂度分析

| 操作 | 平均时间复杂度 | 最差时间复杂度 ||---|---|---|| 插入(头部/尾部) | O(1) | O(1) || 插入(中间) | O(n) | O(n) || 删除(头部/尾部) | O(1) | O(1) || 删除(中间) | O(n) | O(n) || 搜索 | O(n) | O(n) |

其中 n 是链表中的元素数。

完整程序

以下是一个用 Python 实现的简单链表程序：

```pythonclass Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Noneself.tail = Nonedef insert_at_head(self, data):new_node = Node(data)if self.head is None:self.head = new_nodeself.tail = new_nodeelse:new_node.next = self.headself.head = new_nodedef insert_at_tail(self, data):new_node = Node(data)if self.tail is None:self.head = new_nodeself.tail = new_nodeelse:self.tail.next = new_nodeself.tail = new_nodedef insert_after(self, node, data):if node is None:returnnew_node = Node(data)new_node.next = node.nextnode.next = new_nodeif node == self.tail:self.tail = new_nodedef delete_at_head(self):if self.head is None:returnif self.head == self.tail:self.head = Noneself.tail = Noneelse:self.head = self.head.nextdef delete_at_tail(self):if self.tail is None:returnif self.head == self.tail:self.head = Noneself.tail = Noneelse:current = self.headwhile current.next != self.tail:current = current.nextcurrent.next = Noneself.tail = currentdef delete_node(self, node):if node is None or node == self.head:self.delete_at_head()elif node == self.tail:self.delete_at_tail()else:current = self.headwhile current.next != node:current = current.nextcurrent.next = node.nextdef Search(self, data):current = self.headwhile current is not None:if current.data == data:return currentcurrent = current.nextreturn Nonedef print_list(self):current = self.headwhile current is not None:print(current.data, end=" ")current = current.nextprint()示例用法linked_list = LinkedList()linked_list.insert_at_head(10)linked_list.insert_at_tail(20)linked_list.insert_after(linked_list.head, 15)linked_list.delete_at_head()linked_list.delete_at_tail()linked_list.delete_node(linked_list.head)linked_list.print_list()```