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

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

[[273724]]

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

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

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

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

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

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

如下圖：

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

• 數(shù)組的訪問：

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

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

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

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

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

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

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

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

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

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

二、「 鏈表 」是什么?

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

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

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

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

雙向鏈表：

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

循環(huán)鏈表：

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

• 鏈表的訪問

鏈表的優(yōu)勢并不在與訪問，因為鏈表無法通過首地址和下標去計算出某一個節(jié)點的地址，所以鏈表中如果要查找某個節(jié)點，則需要一個節(jié)點一個節(jié)點的遍歷，因此鏈表的訪問時間復(fù)雜度為O(n)

• 鏈表的插入與刪除

也正式因為鏈表內(nèi)存空間是非連續(xù)的，所以它對元素的插入和刪除時，并不需要像數(shù)組那樣移動其它元素，只需要修改指針的指向即可。

例如：刪除一個元素E：

例如：插入一個元素：

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

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

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

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

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

算法題：反轉(zhuǎn)一個單鏈表 
輸入: 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) { 
        //定義一個前置節(jié)點變量，默認是null，因為對于第一個節(jié)點而言沒有前置節(jié)點 
        ListNode pre = null; 
        //定義一個當前節(jié)點變量，首先將頭節(jié)點賦值給它 
        ListNode curr = head; 
        //遍歷整個鏈表，直到當前指向的節(jié)點為空，也就是最后一個節(jié)點了 
        while(curr != null){ 
            //在循環(huán)體里會去改變當前節(jié)點的指針方向，本來當前節(jié)點的指針是指向的下一個節(jié)點，現(xiàn)在需要改為指向前一個節(jié)點，但是如果直接就這么修改了，那鏈條就斷了，再也找不到后面的節(jié)點了，所以首先需要將下一個節(jié)點先臨時保存起來，賦值到temp中，以備后續(xù)使用 
            ListNode temp = curr.next; 
            //開始處理當前節(jié)點，將當前節(jié)點的指針指向前面一個節(jié)點 
            curr.next = pre; 
            //將當前節(jié)點賦值給變量pre，也就是讓pre移動一步，pre指向了當前節(jié)點 
            pre = curr; 
            //將之前保存的臨時節(jié)點（后面一個節(jié)點）賦值給當前節(jié)點變量 
            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é)點 
        } 
        //完成，時間復(fù)雜度為O(n) 
        return pre; 
    } 
} 

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