前言

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

數(shù)據(jù)結(jié)構(gòu)介紹

常見的數(shù)據(jù)結(jié)構(gòu)大體分為兩種類型：線性和非線性。

線性數(shù)據(jù)結(jié)構(gòu)見名思義，整體結(jié)構(gòu)的圖像是一條直線。包括數(shù)組、鏈表、棧、隊列等。
非線性數(shù)據(jù)結(jié)構(gòu)包括，樹、堆、圖等。

數(shù)組

數(shù)組是由多個元素組成的一個集合，表現(xiàn)形式如下圖

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

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

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

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

示例代碼在內(nèi)存中的活動如下圖

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

鏈表

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

public class Node<T> {//存儲數(shù)據(jù)元素的數(shù)據(jù)域private T value;//下一個節(jié)點地址的指針域private Node next;
}

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

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

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

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

如果結(jié)構(gòu)為雙向鏈表，要刪除倒數(shù)第二個節(jié)點，只用找到尾節(jié)點的前面一個節(jié)點并刪除即可。Java 中的 LinkedList 就是一個雙向鏈表的實現(xiàn)。

隊列和棧

數(shù)組和鏈表的關(guān)注點主要聚焦于數(shù)據(jù)的存儲結(jié)構(gòu)和訪問方式，而隊列和棧關(guān)注的則是數(shù)據(jù)的處理順序和邏輯，有自己的特點。

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

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

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

兩者的底層實現(xiàn)可以根據(jù)具體需求和場景選擇數(shù)組或鏈表作為底層數(shù)據(jù)結(jié)構(gòu)。例如 Java 中的 ArrayBlockingQueue 是通過數(shù)組實現(xiàn)的阻塞隊列，LinkedBlockingQueue 通過隊列實現(xiàn)的非阻塞隊列。

樹

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

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

public class Node {//當(dāng)前節(jié)點的值private int value;//父節(jié)點、左子節(jié)點、右子節(jié)點private Node parent,left,right;}

表現(xiàn)形式如下圖

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

---

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

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

右旋就是：以某個節(jié)點為旋轉(zhuǎn)點，其左子節(jié)點變?yōu)槠涓腹?jié)點，左子節(jié)點的右子節(jié)點變?yōu)槠渥笞庸?jié)點，右子節(jié)點不變。
同理，左旋就是：以某個節(jié)點為旋轉(zhuǎn)點，其右子節(jié)點變?yōu)槠涓腹?jié)點，右子節(jié)點的左子節(jié)點變?yōu)槠溆易庸?jié)點，左子節(jié)點不變。

---

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

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

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

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

---

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

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

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

常見的多叉樹有2-3-4樹、B樹和B+樹，通常在數(shù)據(jù)庫和文件系統(tǒng)中會使用到，其表現(xiàn)形式如下圖。

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

堆

堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，其特點為：每個節(jié)點都大于或等于（小于或等于）其每個子節(jié)點。

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

堆通常被用作優(yōu)先隊列，因為堆的根節(jié)點總是最大的或最小的。

總結(jié)

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