【数据结构】实现方式、应用场景与优缺点的系统总结

以下是编程中常见的数据结构及其实现方式、应用场景与优缺点的系统总结：

一、线性数据结构

1. 数组 (Array)

• 定义：连续内存空间存储相同类型元素。
• 实现方式：

  int[] arr = new int[10]; // Java
  

  arr = [0] * 10  # Python
  

• 操作：
  • 访问：O(1)（通过索引）
  • 插入/删除：O(n)（需移动元素）
• 优点：内存连续，高速缓存友好。
• 缺点：大小固定，动态扩容成本高。
• 应用场景：频繁随机访问，如矩阵运算。

2. 链表 (Linked List)

• 定义：通过指针连接的非连续内存节点。
• 实现方式（单向链表）：

  class Node {
      int val;
      Node next;
      Node(int val) { this.val = val; }
  }
  Node head = new Node(0); // Java
  

• 操作：
  • 插入/删除：O(1)（已知位置时）
  • 访问：O(n)
• 优点：动态大小，高效插入删除。
• 缺点：内存不连续，缓存不友好。
• 变种：双向链表、循环链表。
• 应用场景：LRU缓存、浏览器历史记录。

3. 栈 (Stack)

• 定义：后进先出（LIFO）结构。
• 实现方式：
  • 数组实现：

    stack = []
    stack.append(1)  # Push
    stack.pop()      # Pop (Python)
    

  • 链表实现：

    class Stack {
        Node top;
        void push(int val) { /* 插入链表头部 */ }
        int pop() { /* 删除链表头部 */ }
    }
    

• 应用场景：函数调用栈、括号匹配。

4. 队列 (Queue)

• 定义：先进先出（FIFO）结构。
• 实现方式：
  • 数组实现（循环队列）：

    class CircularQueue {
        int[] arr;
        int front, rear, size;
        // 实现enqueue、dequeue
    }
    

  • 链表实现：

    from collections import deque
    q = deque()  # Python双端队列
    q.append(1)  # 入队
    q.popleft()  # 出队
    

• 变种：双端队列（Deque）、优先队列（Priority Queue）。
• 应用场景：任务调度、BFS算法。

二、树形数据结构

1. 二叉树 (Binary Tree)

• 定义：每个节点最多两个子节点。
• 实现方式：

  class TreeNode {
      int val;
      TreeNode left, right;
      TreeNode(int val) { this.val = val; }
  }
  

• 变种：
  • 二叉搜索树 (BST)：左子树所有节点值 < 根 < 右子树。
  • 平衡树 (AVL/红黑树)：自动调整高度平衡。
• 操作：插入/删除/查找（BST平均 O(log n), 最差 O(n)）。

2. 堆 (Heap)

• 定义：完全二叉树，满足堆属性（最大堆/最小堆）。
• 实现方式：
  • 数组实现：

    # Python heapq模块（最小堆）
    import heapq
    heap = []
    heapq.heappush(heap, 3)
    heapq.heappop(heap)
    

• 应用场景：优先队列、Top K问题。

三、散列表 (Hash Table)

• 定义：通过哈希函数映射键到存储位置。
• 实现方式（链地址法）：

  class HashMap {
      LinkedList<Entry>[] buckets;
      class Entry { K key; V value; }
      void put(K key, V value) { /* 计算哈希并处理冲突 */ }
      V get(K key) { /* 查找链表 */ }
  }
  

• 操作：
  • 平均 O(1)（假设哈希函数均匀）。
  • 最差 O(n)（所有键冲突）。
• 优点：高效查找、插入、删除。
• 缺点：内存开销大，无序。
• 应用场景：字典、缓存（如Redis）。

四、图 (Graph)

• 定义：由顶点和边组成的非线性结构。
• 实现方式：
  • 邻接矩阵：

    graph = [[0 for _ in range(n)] for _ in range(n)]
    graph[i][j] = weight  # 边权重
    

  • 邻接表：

    class Graph {
        List<List<Integer>> adjList;
        Graph(int n) { adjList = new ArrayList<>(n); }
        void addEdge(int u, int v) { adjList.get(u).add(v); }
    }
    

• 应用场景：社交网络、路径规划（Dijkstra算法）。

五、对比总结

选择建议：

• 需要快速查询 → 哈希表。
• 需要有序数据 → 平衡二叉搜索树（如TreeMap）。
• 高频插入删除 → 链表。
• 分层处理数据 → 树（如文件系统）。
• 数据存在复杂关联 → 图。