前言

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。在工作中，我們通常會(huì)直接使用已經(jīng)封裝好的集合API，這樣可以更高效地完成任務(wù)。但是作為一名程序員，掌握數(shù)據(jù)結(jié)構(gòu)是非常重要的，因?yàn)樗梢詭椭覀兏玫乩斫夂驮O(shè)計(jì)算法，從而提高程序的效率和可靠性。本文將對(duì)常見的幾種數(shù)據(jù)結(jié)構(gòu)進(jìn)行介紹，通過了解這些數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和優(yōu)勢(shì)，可以更好地在不同場(chǎng)景下選擇合適的數(shù)據(jù)結(jié)構(gòu)。

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

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

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

數(shù)組

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

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

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

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

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

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

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

鏈表

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

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

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

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

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

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

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

隊(duì)列和棧

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

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

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

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

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

樹

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

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

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

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

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

---

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

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

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

---

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

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

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

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

---

上面說的幾種樹都是二叉樹，即每個(gè)節(jié)點(diǎn)只有兩個(gè)分支，并且都都是有序的。因?yàn)橹挥袃蓚€(gè)分支，所以這也是二叉樹的通病，當(dāng)數(shù)據(jù)越來越多的時(shí)候，樹的高度也會(huì)越高，這種情況就不適合數(shù)據(jù)庫和文件系統(tǒng)這種場(chǎng)景了。

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

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

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

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

堆

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

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

堆通常被用作優(yōu)先隊(duì)列，因?yàn)槎训母?jié)點(diǎn)總是最大的或最小的。

總結(jié)

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