數(shù)據(jù)結(jié)構(gòu)是我們軟件開發(fā)中最基礎(chǔ)的部分了，它體現(xiàn)著我們編程的內(nèi)功。大多數(shù)人在正兒八經(jīng)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候估計(jì)是在大學(xué)計(jì)算機(jī)課上，而在實(shí)際項(xiàng)目開發(fā)中，反而感覺到用得不多。

其實(shí)也不是真的用得少，只不過我們?cè)谑褂玫臅r(shí)候被很多高級(jí)語言和框架組件封裝好了，真正需要自己去實(shí)現(xiàn)的地方比較少而已。但別人封裝好了不代表我們就可以不關(guān)注了，數(shù)據(jù)結(jié)構(gòu)作為程序員的內(nèi)功心法，是非常值得我們多花時(shí)間去研究的，我這就翻開書復(fù)習(xí)復(fù)習(xí)：

[[273724]]

本文就先從大家最經(jīng)常使用的「 數(shù)組 」和「 鏈表 」聊起。不過在聊數(shù)組和鏈表之前，咱們先看一下數(shù)據(jù)的邏輯結(jié)構(gòu)分類。通俗的講，數(shù)據(jù)的邏輯結(jié)構(gòu)主要分為兩種：

線性的：就是連成一條線的結(jié)構(gòu)，本文要講的數(shù)組和鏈表就屬于這一類，另外還有 隊(duì)列、棧 等

非線性的：顧名思義，數(shù)據(jù)之間的關(guān)系是非線性的，比如 堆、樹、圖 等

知道了分類，下面我們來詳細(xì)看一下「 數(shù)組 」和「 鏈表 」的原理。

一、「 數(shù)組 」是什么?

數(shù)組是一個(gè)有限的、類型相同的數(shù)據(jù)的集合，在內(nèi)存中是一段連續(xù)的內(nèi)存區(qū)域。

如下圖：

數(shù)組的下標(biāo)是從0開始的，上圖數(shù)組中有6個(gè)元素，對(duì)應(yīng)著下標(biāo)依次是0、1、2、3、4、5，同時(shí)，數(shù)組里面存的數(shù)據(jù)的類型必須是一致的，比如上圖中存的都是數(shù)字類型。數(shù)組中的全部元素是“連續(xù)”的存儲(chǔ)在一塊內(nèi)存空間中的，如上圖右邊部分，元素與元素之間是不會(huì)有別的存儲(chǔ)隔離的。另外，也是因?yàn)閿?shù)組需要連續(xù)的內(nèi)存空間，所以數(shù)組在定義的時(shí)候就需要提前指定固定大小，不能改變。

• 數(shù)組的訪問：

數(shù)組在訪問操作方面有著獨(dú)特的性能優(yōu)勢(shì)，因?yàn)閿?shù)組是支持隨機(jī)訪問的，也就是說我們可以通過下標(biāo)隨機(jī)訪問數(shù)組中任何一個(gè)元素，其原理是因?yàn)閿?shù)組元素的存儲(chǔ)是連續(xù)的，所以我們可以通過數(shù)組內(nèi)存空間的首地址加上元素的偏移量計(jì)算出某一個(gè)元素的內(nèi)存地址，如下：

array[n]的地址 =  array數(shù)組內(nèi)存空間的首地址 + 每個(gè)元素大小*n 

通過上述公式可知：數(shù)組中通過下標(biāo)去訪問數(shù)據(jù)時(shí)并不需要遍歷整個(gè)數(shù)組，因此數(shù)組的訪問時(shí)間復(fù)雜度是 O(1)，當(dāng)然這里需要注意，如果不是通過下標(biāo)去訪問，而是通過內(nèi)容去查找數(shù)組中的元素，則時(shí)間復(fù)雜度不是O(1)，極端的情況下需要遍歷整個(gè)數(shù)組的元素，時(shí)間復(fù)雜度可能是O(n)，當(dāng)然通過不同的查找算法所需的時(shí)間復(fù)雜度是不一樣的。

• 數(shù)組的插入與刪除：

同樣是因?yàn)閿?shù)組元素的連續(xù)性要求，所以導(dǎo)致數(shù)組在插入和刪除元素的時(shí)候效率比較低。

如果要在數(shù)組中間插入一個(gè)新元素，就必須要將要相鄰的后面的元素全部往后移動(dòng)一個(gè)位置，留出空位給這個(gè)新元素。還是拿上面那圖舉例，如果需要在下標(biāo)為2的地方插入一個(gè)新元素11，那就需要將原有的2、3、4、5幾個(gè)下標(biāo)的元素依次往后移動(dòng)一位，新元素再插入下標(biāo)為2的位置，最后形成新的數(shù)組是：

23、4、11、6、15、5、7 

如果新元素是插入在數(shù)組的最開頭位置，那整個(gè)原始數(shù)組都需要向后移動(dòng)一位，此時(shí)的時(shí)間復(fù)雜度為最壞情況即O(n)，如果新元素要插入的位置是最末尾，則無需其它元素移動(dòng)，則此時(shí)時(shí)間復(fù)雜度為最好情況即O(1)，所以平均而言數(shù)組插入的時(shí)間復(fù)雜度是O(n)

數(shù)組的刪除與數(shù)組的插入是類似的。

所以整體而言，數(shù)組的訪問效率高，插入與刪除效率低。不過想改善數(shù)組的插入與刪除效率也是有辦法的，來來來，下面的「 鏈表 」了解一下。

二、「 鏈表 」是什么?

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的，一般用于插入與刪除較為頻繁的場景。

上圖是“單鏈表”示例，鏈表并不需要數(shù)組那樣的連續(xù)空間，它只需要一個(gè)個(gè)零散的內(nèi)存空間即可，因此對(duì)內(nèi)存空間的要求也比數(shù)組低。

鏈表的每一個(gè)節(jié)點(diǎn)通過“指針”鏈接起來，每一個(gè)節(jié)點(diǎn)有2部分組成，一部分是數(shù)據(jù)(上圖中的Data)，另一部分是后繼指針(用來存儲(chǔ)后一個(gè)節(jié)點(diǎn)的地址)，在這條鏈中，最開始的節(jié)點(diǎn)稱為Head，最末尾節(jié)點(diǎn)的指針指向NULL。

「 鏈表 」也分為好幾種，上圖是最簡單的一種，它的每一個(gè)節(jié)點(diǎn)只有一個(gè)指針(后繼指針)指向后面一個(gè)節(jié)點(diǎn)，這個(gè)鏈表稱為：單向鏈表，除此之外還有 雙向鏈表、循環(huán)鏈表 等。

雙向鏈表：

雙向鏈表與單向鏈表的區(qū)別是前者是2個(gè)方向都有指針，后者只有1個(gè)方向的指針。雙向鏈表的每一個(gè)節(jié)點(diǎn)都有2個(gè)指針，一個(gè)指向前節(jié)點(diǎn)，一個(gè)指向后節(jié)點(diǎn)。雙向鏈表在操作的時(shí)候比單向鏈表的效率要高很多，但是由于多一個(gè)指針空間，所以占用內(nèi)存也會(huì)多一點(diǎn)。

循環(huán)鏈表：

其實(shí)循環(huán)鏈表就是一種特殊的單向鏈表，只不過在單向鏈表的基礎(chǔ)上，將尾節(jié)點(diǎn)的指針指向了Head節(jié)點(diǎn)，使之首尾相連。

• 鏈表的訪問

鏈表的優(yōu)勢(shì)并不在與訪問，因?yàn)殒湵頍o法通過首地址和下標(biāo)去計(jì)算出某一個(gè)節(jié)點(diǎn)的地址，所以鏈表中如果要查找某個(gè)節(jié)點(diǎn)，則需要一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的遍歷，因此鏈表的訪問時(shí)間復(fù)雜度為O(n)

• 鏈表的插入與刪除

也正式因?yàn)殒湵韮?nèi)存空間是非連續(xù)的，所以它對(duì)元素的插入和刪除時(shí)，并不需要像數(shù)組那樣移動(dòng)其它元素，只需要修改指針的指向即可。

例如：刪除一個(gè)元素E：

例如：插入一個(gè)元素：

既然插入與刪除元素只需要改動(dòng)指針，無需移動(dòng)數(shù)據(jù)，那么鏈表的時(shí)間插入刪除的時(shí)間復(fù)雜度為O(1)不過這里指的是找到節(jié)點(diǎn)之后純粹的插入或刪除動(dòng)作所需的時(shí)間復(fù)雜度。

如果當(dāng)前還未定位到指定的節(jié)點(diǎn)，只是拿到鏈表的Head，這個(gè)時(shí)候要去刪除此鏈表中某個(gè)固定內(nèi)容的節(jié)點(diǎn)，則需要先查找到那個(gè)節(jié)點(diǎn)，這個(gè)查找的動(dòng)作又是一個(gè)遍歷動(dòng)作了，這個(gè)遍歷查找的時(shí)間復(fù)雜度卻是O(n)，兩者加起來總的時(shí)間復(fù)雜度其實(shí)是O(n)的。

其實(shí)就算是已經(jīng)定位到了某個(gè)要?jiǎng)h除的節(jié)點(diǎn)了，刪除邏輯也不簡單。以“刪除上圖的E節(jié)點(diǎn)”為例，假如當(dāng)前鏈表指針已經(jīng)定位到了E節(jié)點(diǎn)，刪除的時(shí)候，需要將這個(gè)E節(jié)點(diǎn)的前面一個(gè)節(jié)點(diǎn)H的后繼指針改為指向A節(jié)點(diǎn)，那么E節(jié)點(diǎn)就會(huì)自動(dòng)脫落了，但是當(dāng)前鏈表指針是定位在E節(jié)點(diǎn)上，如何去改變H節(jié)點(diǎn)的后續(xù)指針呢，對(duì)于“單向鏈表”而言，這個(gè)時(shí)候需要從頭遍歷一遍整個(gè)鏈表，找到H節(jié)點(diǎn)去修改其后繼指針的內(nèi)容，所以時(shí)間復(fù)雜度是O(n)，但如果當(dāng)前是“雙向鏈表”，則不需要遍歷，直接通過前繼指針即可找到H節(jié)點(diǎn)，時(shí)間復(fù)雜度是O(1)，這里就是“雙向鏈表”相當(dāng)于“單向鏈表”的優(yōu)勢(shì)所在。

三、「 數(shù)組和鏈表 」的算法實(shí)戰(zhàn)?

通過上面的介紹我們可以看到「 數(shù)組 」和「 鏈表 」各有優(yōu)勢(shì)，并且時(shí)間復(fù)雜度在不同的操作情況下也不相同，不能簡單一句O(1)或O(n)。所以下面我們找了個(gè)常用的算法題來練習(xí)練習(xí)。

算法題：反轉(zhuǎn)一個(gè)單鏈表 
輸入: 1->2->3->4->5->NULL 
輸出: 5->4->3->2->1->NULL 
 
/** 
 * Definition for singly-linked list. 
 * public class ListNode { 
 *     int val; 
 *     ListNode next; 
 *     ListNode(int x) { val = x; } 
 * } 
 */ 
class Solution { 
    public ListNode reverseList(ListNode head) { 
        //定義一個(gè)前置節(jié)點(diǎn)變量，默認(rèn)是null，因?yàn)閷?duì)于第一個(gè)節(jié)點(diǎn)而言沒有前置節(jié)點(diǎn) 
        ListNode pre = null; 
        //定義一個(gè)當(dāng)前節(jié)點(diǎn)變量，首先將頭節(jié)點(diǎn)賦值給它 
        ListNode curr = head; 
        //遍歷整個(gè)鏈表，直到當(dāng)前指向的節(jié)點(diǎn)為空，也就是最后一個(gè)節(jié)點(diǎn)了 
        while(curr != null){ 
            //在循環(huán)體里會(huì)去改變當(dāng)前節(jié)點(diǎn)的指針方向，本來當(dāng)前節(jié)點(diǎn)的指針是指向的下一個(gè)節(jié)點(diǎn)，現(xiàn)在需要改為指向前一個(gè)節(jié)點(diǎn)，但是如果直接就這么修改了，那鏈條就斷了，再也找不到后面的節(jié)點(diǎn)了，所以首先需要將下一個(gè)節(jié)點(diǎn)先臨時(shí)保存起來，賦值到temp中，以備后續(xù)使用 
            ListNode temp = curr.next; 
            //開始處理當(dāng)前節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)的指針指向前面一個(gè)節(jié)點(diǎn) 
            curr.next = pre; 
            //將當(dāng)前節(jié)點(diǎn)賦值給變量pre，也就是讓pre移動(dòng)一步，pre指向了當(dāng)前節(jié)點(diǎn) 
            pre = curr; 
            //將之前保存的臨時(shí)節(jié)點(diǎn)（后面一個(gè)節(jié)點(diǎn)）賦值給當(dāng)前節(jié)點(diǎn)變量 
            curr = temp; 
            //循環(huán)體執(zhí)行鏈表狀態(tài)變更情況： 
            //NULL<-1  2->3->4->5->NULL 
            //NULL<-1<-2  3->4->5->NULL 
            //NULL<-1<-2<-3  4->5->NULL 
            //NULL<-1<-2<-3<-4  5->NULL 
            //NULL<-1<-2<-3<-4<-5 
            //循環(huán)體遍歷完之后，pre指向5的節(jié)點(diǎn) 
        } 
        //完成，時(shí)間復(fù)雜度為O(n) 
        return pre; 
    } 
} 

以上，就是對(duì)「 數(shù)組與鏈表 」的一些思考。