數據結構是我們軟件開發中最基礎的部分了，它體現著我們編程的內功。大多數人在正兒八經學習數據結構的時候估計是在大學計算機課上，而在實際項目開發中，反而感覺到用得不多。

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

[[273724]]

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

線性的：就是連成一條線的結構，本文要講的數組和鏈表就屬于這一類，另外還有 隊列、棧 等

非線性的：顧名思義，數據之間的關系是非線性的，比如 堆、樹、圖 等

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

一、「 數組 」是什么?

數組是一個有限的、類型相同的數據的集合，在內存中是一段連續的內存區域。

如下圖：

 

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

• 數組的訪問：

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

array[n]的地址 =  array數組內存空間的首地址 + 每個元素大小*n 

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

• 數組的插入與刪除：

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

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

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

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

數組的刪除與數組的插入是類似的。

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

二、「 鏈表 」是什么?

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的，一般用于插入與刪除較為頻繁的場景。

 

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

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

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

雙向鏈表：

 

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

循環鏈表：

 

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

• 鏈表的訪問

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

• 鏈表的插入與刪除

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

例如：刪除一個元素E：

例如：插入一個元素：

 

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

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

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

三、「 數組和鏈表 」的算法實戰?

通過上面的介紹我們可以看到「 數組 」和「 鏈表 」各有優勢，并且時間復雜度在不同的操作情況下也不相同，不能簡單一句O(1)或O(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) { 
        //定義一個前置節點變量，默認是null，因為對于第一個節點而言沒有前置節點 
        ListNode pre = null; 
        //定義一個當前節點變量，首先將頭節點賦值給它 
        ListNode curr = head; 
        //遍歷整個鏈表，直到當前指向的節點為空，也就是最后一個節點了 
        while(curr != null){ 
            //在循環體里會去改變當前節點的指針方向，本來當前節點的指針是指向的下一個節點，現在需要改為指向前一個節點，但是如果直接就這么修改了，那鏈條就斷了，再也找不到后面的節點了，所以首先需要將下一個節點先臨時保存起來，賦值到temp中，以備后續使用 
            ListNode temp = curr.next; 
            //開始處理當前節點，將當前節點的指針指向前面一個節點 
            curr.next = pre; 
            //將當前節點賦值給變量pre，也就是讓pre移動一步，pre指向了當前節點 
            pre = curr; 
            //將之前保存的臨時節點（后面一個節點）賦值給當前節點變量 
            curr = temp; 
            //循環體執行鏈表狀態變更情況： 
            //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 
            //循環體遍歷完之后，pre指向5的節點 
        } 
        //完成，時間復雜度為O(n) 
        return pre; 
    } 
} 

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