以下是編程中常見的數據結構及其實現方式、應用場景與優缺點的系統總結：

---

一、線性數據結構

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算法）。

---

五、對比總結

數據結構	優勢	劣勢	典型應用
數組	快速隨機訪問	大小固定，插入刪除慢	數值計算
鏈表	動態擴展，高效插入刪除	隨機訪問慢	實現棧/隊列
哈希表	平均O(1)操作	內存占用大，無序	緩存、去重
二叉搜索樹	有序數據存儲，查找高效	可能退化為鏈表	數據庫索引
堆	快速獲取極值	僅支持極值訪問	任務調度
圖	建模復雜關系	算法復雜度高	推薦系統

---

選擇建議：

• 需要快速查詢 → 哈希表。
• 需要有序數據 → 平衡二叉搜索樹（如TreeMap）。
• 高頻插入刪除 → 鏈表。
• 分層處理數據 → 樹（如文件系統）。
• 數據存在復雜關聯 → 圖。