數據結構是計算機存儲、組織數據的方式。在工作中，我們通常會直接使用已經封裝好的集合API，這樣可以更高效地完成任務。但是作為一名程序員，掌握數據結構是非常重要的，因為它可以幫助我們更好地理解和設計算法，從而提高程序的效率和可靠性。本文將對常見的幾種數據結構進行介紹，通過了解這些數據結構的特點和優勢，可以更好地在不同場景下選擇合適的數據結構。

一、數據結構介紹

常見的數據結構大體分為兩種類型：線性和非線性。

線性數據結構見名思義，整體結構的圖像是一條直線。包括數組、鏈表、棧、隊列等。

非線性數據結構包括，樹、堆、圖等。

二、數組

數組是由多個元素組成的一個集合，表現形式如下圖

在內存中存儲數組的空間是連續的，每個元素占據一定的內存空間，這也是為什么在聲明數組時要指定長度，不然不知道要占用多少空間。以 Java 語言為例，當聲明一個數組后，數組變量會指向數組對象的起始地址，也就是第一個元素的位置，如下圖

以此看來，當查詢數組中的某個元素時，通過下標就可以計算出這個元素的內存地址，比如想查找下標為2的元素，那么arr[2]的內存地址 = arr的內存地址 + 2 * 元素大小，也就可以直接通過內存地址訪問元素，時間復雜度為O(1)。

但是，數組也會帶來一個問題：由于數組長度是固定的，所以在添加或刪除元素時會涉及到創建新的數組來替換原數組，導致復雜度較高。例如，下面的代碼演示了如何在數組末尾添加一個元素：

int[] arr = {1, 2, 3, 4, 5};  
  
arr[arr.length] = 6; // 將要添加的元素放到數組的最后一個位置  
  
int[] newArr = new int[arr.length + 1]; // 創建一個新的數組，長度加1  
  
for (int i = 0; i < newArr.length; i++) {  
    newArr[i] = arr[i]; // 將原數組中的元素復制到新數組中  
}  
  
arr = newArr; // 使用新數組替換原數組

示例代碼在內存中的活動如下圖

在 Java 中有很多集合的底層實現都是基于數組，例如大家常用的 ArrayList、Vector、HashMap、ArrayBlockingQueue等等。

三、鏈表

鏈表由一系列結點組成，每個節點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個節點地址的指針域。以 Java 為例，一個節點的結構是這樣表示的：

public class Node<T> {

    //存儲數據元素的數據域
    private T value;

    //下一個節點地址的指針域
    private Node next;
}

每個元素的指針指向下一個元素，從而形成鏈表，表現形式如下圖。

與數組不同，鏈表在內存中是非連續的空間，可以充分利用計算機內存空間，實現靈活的內存動態管理，解決了數組需要預先知道數據大小的缺點。其在內存中的存儲如下圖

相比于數組，鏈表的插入和刪除操作可以達到O(1)的復雜度（只需要將鏈尾的指針指向下個節點或者指向null即可），但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間。

上面介紹的是單向鏈表，單向鏈表有個缺點：只能只能從頭到尾遍歷。如果要刪除倒數第二個節點，只能從頭遍歷。為了更加靈活的操作和更高的效率，就有了雙向鏈表，其結構表示如下圖

如果結構為雙向鏈表，要刪除倒數第二個節點，只用找到尾節點的前面一個節點并刪除即可。Java 中的 LinkedList 就是一個雙向鏈表的實現。

四、隊列和棧

數組和鏈表的關注點主要聚焦于數據的存儲結構和訪問方式，而隊列和棧關注的則是數據的處理順序和邏輯，有自己的特點。

隊列的特點是先進先出（FIFO）：第一個進入隊列的元素會第一個被訪問或取出，或者說在添加元素時在隊尾排隊依次入隊，在隊頭依次出隊。其表現形式如下圖

棧的特點是先進后出（FILO）：第一個入棧的元素最后一個被訪問或被取出，或者說最后一個入棧的元素會第一個被訪問或被取出。棧只允許在棧頂進行插入和刪除操作。

有一個很形象的描述就是：可以將棧想象成一個彈夾，最先裝入的子彈會被壓入底部，而射出時則是從頂部彈出。

兩者的底層實現可以根據具體需求和場景選擇數組或鏈表作為底層數據結構。例如 Java 中的 ArrayBlockingQueue 是通過數組實現的阻塞隊列，LinkedBlockingQueue 通過隊列實現的非阻塞隊列。

五、樹

樹是一種非線性結構，是由n個有限節點組成一個具有層次關系的集合。樹也有很多類型，比如二叉樹、平衡樹、2-3-4樹、紅黑樹、B樹、B+樹。

二叉樹是每個節點最多有兩個子樹的樹結構，通常用于實現二叉查找樹，其特點為：左子節點的值小于根節點的值，右子節點的值大于根節點的值。以 Java 為例，一個二叉查找樹的結構是這樣表示的：

public class Node {

    //當前節點的值
    private int value;

    //父節點、左子節點、右子節點
    private Node parent,left,right;

}

表現形式如下圖：

其查詢的時間復雜度為O(log n)，相對于鏈表，查詢效率大大提升。但是在最壞情況下可能會退化成O(n)，比如下面這種情況

為了避免這種情況，誕生了AVL樹。AVL樹是一種自平衡的二叉查找樹，在進行插入和刪除操作時，會通過左旋或者右旋自動調整自身的結構，確保每個節點的左右子樹的高度差不超過1，從而保持樹的平衡，也保障了查詢的時間復雜度為O(log n)。

以下圖為例，當插入節點5時，節點7左右子樹的高度差為2，這時候節點7就需要進行右旋保持樹的平衡。

右旋就是：以某個節點為旋轉點，其左子節點變為其父節點，左子節點的右子節點變為其左子節點，右子節點不變。

同理，左旋就是：以某個節點為旋轉點，其右子節點變為其父節點，右子節點的左子節點變為其右子節點，左子節點不變。

雖然AVL通過旋轉保持樹的平衡，但是在插入和刪除頻繁的場景中，頻繁的旋轉會導致性能下降，為解決此問題紅黑樹被提出。

紅黑樹大家應該都比較耳熟，面試的時候應該經常會被問到，但是理不理解是另一回事。

紅黑樹也是自平衡的二叉查找樹，它是通過節點顏色來保證樹的平衡的。相對AVL，紅黑樹較難被理解，第一疑惑就是：“不也是左旋右旋嗎？還這么麻煩，節點顏色變來變去，迷惑誰呢？”。

紅黑樹后面專門寫一篇文章介紹，這里先給結論：紅黑樹的旋轉次數相對于AVL樹來說較少，因此在插入、刪除等操作較多的情況下，通常使用紅黑樹，比如大家都知道的HashMap。下圖顯示的是按順序插入9, 7, 6, 10, 5, 8, 4, 2, 1, 0的AVL樹和紅黑樹，可以看到兩者在結構上存在一定的差異。

上面說的幾種樹都是二叉樹，即每個節點只有兩個分支，并且都都是有序的。因為只有兩個分支，所以這也是二叉樹的通病，當數據越來越多的時候，樹的高度也會越高，這種情況就不適合數據庫和文件系統這種場景了。

上面提到的幾種樹結構都是二叉樹，每個節點只有兩個子節點，并且都是有序的。當數據量不斷增加時，二叉樹的高度也會逐漸增加，從而導致查詢效率降低，并且在有磁盤I/O操作的場景下，樹越高越不利于查詢。

為了解決上述問題，采用多叉樹結構，可以有效地降低樹的高度，提高查詢效率。

常見的多叉樹有2-3-4樹、B樹和B+樹，通常在數據庫和文件系統中會使用到，其表現形式如下圖。

B+樹是B樹的一種擴展，它更適合用于磁盤或其他存儲設備中。在B+樹中，非葉子節點不保存數據信息，只保存關鍵字和子節點指針，這樣會存儲更多有效數據，比如索引。同時，每個葉子節點都指向相鄰葉子節點的指針，這樣的話在數據庫范圍查詢會變得非常高效。

六、堆

堆是一種特殊的樹形數據結構，其特點為：每個節點都大于或等于（小于或等于）其每個子節點。

常見的堆有二叉堆、斐波那契堆等，二叉堆是一種完全二叉樹，可以分為最大堆和最小堆，最大堆中的每個節點都大于或等于其子節點，最小堆中的每個節點都小于或等于其子節點。下圖左為最大堆的表示，右不符合為一個完全二叉樹（依次從左到右插入的節點為完全二叉樹）。

堆通常被用作優先隊列，因為堆的根節點總是最大的或最小的。

七、總結

很多編程語言都提供了不同類型的集合類，以 Java 為例，我們常用的集合有List、Set、Queue、Map，其底層的實現就是數組、鏈表或樹這幾種數據結構。所以通過了解數據結構，我們可以更好地選擇和使用這些集合，甚至可以自行設計更高效的數據結構來解決問題。