线性数据结构
1. 技术分析
1.1 线性数据结构概述
线性数据结构按顺序存储数据：
线性结构类型 数组: 连续内存 链表: 分散内存，指针连接 栈: LIFO 队列: FIFO 线性结构特性: 顺序访问 可遍历 可修改1.2 数组
数组特性 连续内存: 固定大小 随机访问: O(1) 插入删除: O(n) 数组操作: 访问: arr[i] 插入: 需要移动元素 删除: 需要移动元素1.3 链表
链表特性 分散内存: 动态大小 顺序访问: O(n) 插入删除: O(1) 链表类型: 单链表: 单向指针 双链表: 双向指针 循环链表: 首尾相连2. 核心功能实现
2.1 动态数组
class DynamicArray: def __init__(self, capacity=10): self.capacity = capacity self.size = 0 self.array = [None] * capacity def _resize(self, new_capacity): new_array = [None] * new_capacity for i in range(self.size): new_array[i] = self.array[i] self.array = new_array self.capacity = new_capacity def append(self, value): if self.size == self.capacity: self._resize(self.capacity * 2) self.array[self.size] = value self.size += 1 def insert(self, index, value): if index < 0 or index > self.size: raise IndexError("Index out of bounds") if self.size == self.capacity: self._resize(self.capacity * 2) for i in range(self.size, index, -1): self.array[i] = self.array[i-1] self.array[index] = value self.size += 1 def remove(self, value): for i in range(self.size): if self.array[i] == value: for j in range(i, self.size-1): self.array[j] = self.array[j+1] self.size -= 1 return True return False def get(self, index): if index < 0 or index >= self.size: raise IndexError("Index out of bounds") return self.array[index] def __getitem__(self, index): return self.get(index) def __len__(self): return self.size def __repr__(self): return str([self.array[i] for i in range(self.size)])2.2 单链表
class ListNode: def __init__(self, value): self.value = value self.next = None class SinglyLinkedList: def __init__(self): self.head = None self.tail = None self.size = 0 def append(self, value): new_node = ListNode(value) if not self.head: self.head = new_node self.tail = new_node else: self.tail.next = new_node self.tail = new_node self.size += 1 def prepend(self, value): new_node = ListNode(value) if not self.head: self.head = new_node self.tail = new_node else: new_node.next = self.head self.head = new_node self.size += 1 def insert_after(self, prev_node, value): if not prev_node: return new_node = ListNode(value) new_node.next = prev_node.next if prev_node == self.tail: self.tail = new_node prev_node.next = new_node self.size += 1 def delete(self, value): if not self.head: return False if self.head.value == value: self.head = self.head.next if not self.head: self.tail = None self.size -= 1 return True current = self.head while current.next: if current.next.value == value: current.next = current.next.next if not current.next: self.tail = current self.size -= 1 return True current = current.next return False def search(self, value): current = self.head while current: if current.value == value: return current current = current.next return None def __len__(self): return self.size def __repr__(self): values = [] current = self.head while current: values.append(str(current.value)) current = current.next return ' -> '.join(values)2.3 栈
class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): if not self.is_empty(): return self.items.pop() raise IndexError("Pop from empty stack") def peek(self): if not self.is_empty(): return self.items[-1] raise IndexError("Peek from empty stack") def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items) def __len__(self): return self.size() def __repr__(self): return str(self.items)2.4 队列
class Queue: def __init__(self): self.items = [] def enqueue(self, item): self.items.append(item) def dequeue(self): if not self.is_empty(): return self.items.pop(0) raise IndexError("Dequeue from empty queue") def front(self): if not self.is_empty(): return self.items[0] raise IndexError("Front from empty queue") def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items) def __len__(self): return self.size() def __repr__(self): return str(self.items) class Deque: def __init__(self): self.items = [] def add_front(self, item): self.items.insert(0, item) def add_rear(self, item): self.items.append(item) def remove_front(self): if not self.is_empty(): return self.items.pop(0) raise IndexError("Remove from empty deque") def remove_rear(self): if not self.is_empty(): return self.items.pop() raise IndexError("Remove from empty deque") def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items)3. 性能对比
3.1 数组vs链表
| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 头部插入 | O(n) | O(1) |
| 尾部插入 | O(1) | O(1) |
| 中间插入 | O(n) | O(1)* |
3.2 栈vs队列
| 操作 | 栈 | 队列 |
|---|---|---|
| 添加 | O(1) | O(1) |
| 删除 | O(1) | O(n)* |
| 访问 | O(1) | O(1) |
3.3 实现方式对比
| 实现 | 优点 | 缺点 |
|---|---|---|
| 数组实现 | 简单 | 扩容开销 |
| 链表实现 | 灵活 | 内存开销 |
| 双端队列 | 高效 | 复杂 |
4. 最佳实践
4.1 括号匹配
def is_valid_parentheses(s): stack = Stack() mapping = {')': '(', '}': '{', ']': '['} for char in s: if char in mapping.values(): stack.push(char) elif char in mapping.keys(): if stack.is_empty() or stack.pop() != mapping[char]: return False return stack.is_empty()4.2 队列应用
def bfs(graph, start): queue = Queue() visited = set() queue.enqueue(start) visited.add(start) while not queue.is_empty(): vertex = queue.dequeue() print(vertex) for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.enqueue(neighbor)5. 总结
线性数据结构是基础数据结构：
- 数组：随机访问快，插入删除慢
- 链表：插入删除快，随机访问慢
- 栈：LIFO，后进先出
- 队列：FIFO，先进先出
对比数据如下：
- 数组随机访问最优(O(1))
- 链表插入删除最优(O(1))
- 栈适合逆序操作
- 队列适合顺序处理
选择合适的线性结构可以显著提高程序效率。
