数据结构实战：从选择题到代码实现，5个经典操作手把手复现-开发者社区

数据结构实战：从选择题到代码实现，5个经典操作手把手复现

1. 单链表删除后继节点

链表操作是数据结构中最基础也最考验指针理解能力的内容。让我们从单链表删除后继节点开始，这个操作看似简单，但隐藏着指针操作的精华。

核心逻辑：给定节点p（非首尾节点），需要跳过其直接后继节点，将p的next指针指向后继的后继节点。关键是要注意内存管理和指针顺序。

// C++实现 struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; void deleteNextNode(ListNode* p) { if (!p || !p->next) return; // 边界检查 ListNode* temp = p->next; // 保存待删除节点 p->next = temp->next; // 跳过后继节点 delete temp; // 释放内存 }

测试用例设计：

# Python测试代码 class TestDeleteNext(unittest.TestCase): def test_normal_case(self): # 构造链表 1->2->3->4 n1 = ListNode(1) n2 = ListNode(2) n3 = ListNode(3) n4 = ListNode(4) n1.next, n2.next, n3.next = n2, n3, n4 deleteNextNode(n2) # 删除节点3 self.assertEqual(n2.next.val, 4) def test_edge_case(self): # 构造链表 1->2 n1 = ListNode(1) n2 = ListNode(2) n1.next = n2 with self.assertRaises(Exception): deleteNextNode(n2) # 尝试删除尾节点的后继

复杂度分析：

时间复杂度：O(1)
空间复杂度：O(1)
内存安全：需要特别注意被删除节点的内存释放

2. 循环队列判满实现

循环队列通过重用数组空间实现高效队列操作，其核心难点在于判满条件的判断。我们来看两种常见的实现方式。

方案一：牺牲一个存储单元

class CircularQueue: def __init__(self, capacity): self.capacity = capacity + 1 # 多分配一个空间 self.queue = [None] * self.capacity self.front = 0 self.rear = 0 def is_full(self): return (self.rear + 1) % self.capacity == self.front

方案二：使用size变量

// Java实现 public class CircularQueue { private int[] data; private int front, rear, size; public CircularQueue(int k) { data = new int[k]; front = rear = size = 0; } public boolean isFull() { return size == data.length; } }

性能对比：

方案	优点	缺点	适用场景
牺牲单元	逻辑简单	浪费一个空间	嵌入式系统
size变量	空间利用率高	需要维护size	通用场景

实际应用建议：在内存受限的嵌入式系统中推荐方案一，现代应用开发推荐方案二。

3. 二叉搜索树插入操作

二叉搜索树（BST）的插入操作需要保持"左小右大"的性质。我们来看递归和迭代两种实现方式。

递归实现

class TreeNode: def __init__(self, val=0): self.val = val self.left = None self.right = None def insertIntoBST(root, val): if not root: return TreeNode(val) if val < root.val: root.left = insertIntoBST(root.left, val) else: root.right = insertIntoBST(root.right, val) return root

迭代实现

// C++迭代版本 TreeNode* insertBST(TreeNode* root, int val) { TreeNode* node = new TreeNode(val); if (!root) return node; TreeNode* curr = root; while (true) { if (val < curr->val) { if (!curr->left) { curr->left = node; break; } curr = curr->left; } else { if (!curr->right) { curr->right = node; break; } curr = curr->right; } } return root; }

复杂度分析：

平均情况：O(log n)
最坏情况（退化成链表）：O(n)
空间复杂度：递归O(h)，迭代O(1)，h为树高

平衡性优化：实际工程中应考虑使用AVL树或红黑树保持平衡，避免退化成链表。

4. 哈希表线性探测解决冲突

哈希表的线性探测法是解决冲突的经典方法。我们实现一个支持插入、查找的基础哈希表。

class HashTable: def __init__(self, size=10): self.size = size self.table = [None] * size self.DELETED = object() # 删除标记 def _hash(self, key): return key % self.size def insert(self, key): index = self._hash(key) for _ in range(self.size): if self.table[index] is None or self.table[index] == self.DELETED: self.table[index] = key return True index = (index + 1) % self.size raise Exception("Hash table is full") def search(self, key): index = self._hash(key) for _ in range(self.size): if self.table[index] == key: return True if self.table[index] is None: # 遇到空位说明不存在 return False index = (index + 1) % self.size return False

性能影响因素：

装载因子（load factor）：建议保持在0.7以下
哈希函数质量：应尽量均匀分布
聚集现象：线性探测可能导致"一次聚集"

工程优化建议：

动态扩容：当装载因子超过阈值时扩大哈希表
二次探测：使用平方探测减少聚集
双重哈希：使用第二个哈希函数计算步长

5. 快速排序划分算法

快速排序的核心在于划分（partition）操作，我们实现Lomuto和Hoare两种经典划分方案。

Lomuto划分方案

// Java实现 public int partitionLomuto(int[] arr, int low, int high) { int pivot = arr[high]; // 选择最后一个元素作为基准 int i = low; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { swap(arr, i, j); i++; } } swap(arr, i, high); return i; }

Hoare划分方案

// C语言实现 int partitionHoare(int arr[], int low, int high) { int pivot = arr[low + (high - low)/2]; // 选择中间元素 int i = low - 1; int j = high + 1; while (1) { do { i++; } while (arr[i] < pivot); do { j--; } while (arr[j] > pivot); if (i >= j) return j; swap(&arr[i], &arr[j]); } }

两种方案对比：