线性数据结构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, capacity10): 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[j1] 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))栈适合逆序操作队列适合顺序处理选择合适的线性结构可以显著提高程序效率。