你好，我是你的數據結構課老師蔡元楠，歡迎進入第 03 課時的內容“鏈表基礎原理”。 這一講，我想和你一起研究數據結構中另外一個基本的知識點——鏈表（Linked List）。在講解這個概念之前，先來復習一下數組的內存模型。 #### 內存管理器 當我們在使用高級語言創建一個數組的時候，實際上是將這個指令傳達了給操作系統里面的內存管理器（Memory Manager），內存管理器在收到指令后會在內存中分配一塊相應大小的連續存儲空間給這個數組。 例如，當想創建一個大小為 5 的數組時，內存管理器有可能會從 0x80000000 這個地址開始分配一個連續的內存塊給我們，我們便可以操作這個數組了，如下圖所示。  而因為數組的大小在一開始是已經確定好的，所以當我們想要增加一個元素的時候，內存管理器無法滿足這個需求，只能重新創建一個新的大小為 6 的數組。然后將原來大小為 5 的數組里的值一一復制到新的數組中去，再對新的元素進行賦值。我們假設內存管理器將新的數組的起始地址設在了 0x80000018 這里，那這個時候的內存如下圖所示。  所以我們看到，當每次要增加一個元素的時候，底層的內存管理器必須為我們重新分配一次內存，我們自己還必須將原來數組上的元素重新復制一遍到新的數組上。那有沒有辦法當每次增加元素的時候能減少這種內存上的消耗呢？其實可以想到的是，當每次新增加一個元素的時候讓內存管理器不要分配一段連續的內存空間就可以了。 假設這時候我們想要保存 3 個元素，但是我們想告訴系統的內存管理器不需要一次性分配 3 個連續的字節內存空間出來了，而是當我們聲明它們的時候才分配一個相應的內存空間出來。假設內存管理器所分配出來的內存空間如下圖所示：  這三個元素被分配在了非相鄰的內存空間里。但從上圖中我們可以知道這三個元素各自的地址，所以想要遍歷它們的話，我們需要保存一些額外的信息，比如，下一個能遍歷到的元素地址。這樣的話，每一個元素就保存了兩部分的內容，一部分是元素本身的值，另一部分是下一個元素的地址，而最后一個元素的下一個地址我們可以保存一個 0x0 的值來表示這個元素是最后一個了。這時候這些數據的內存就如下圖所示：  從上圖可以看到，盡管這些元素不是分配在連續的空間里，但是通過保存額外的信息讓一個元素可以鏈接到下一個元素上，只要知道了這些數據中的第一個元素，便可以將全部元素都遍歷一遍。在計算機里，這種不保存在連續存儲空間中，而每一個元素里都保存了到下一個元素的地址的數據結構，我們稱之為鏈表（Linked List）。鏈表上的每一個元素又可以稱它為節點（Node），而鏈表中第一個元素，稱它為頭節點（Head Node），最后一個元素稱它為尾節點（Tail Node）。 #### 順序訪問 與數組不同的是，我們無法使用一個固定的公式來直接算出某一個特定元素的地址，從而得到那個元素的值。要找到鏈表中的第 N 個元素的值，我們必須要從第一個元素開始，一個一個地遍歷 N 次才能找到第 N 個元素，這種訪問方式，我們就稱之為順序訪問（Sequential Access）。 當我們需要在鏈表的結尾增加一個元素的時候應該怎么辦呢？很簡單，只需要新創建一個鏈表的節點，然后將尾節點中保存地址的值更新成新的節點地址便可。 假設我們原有的鏈表內存圖如下所示：  當我們要插入的一個值為 4 的新節點進這個鏈表的時候，系統的內存管理器會分配一個新的內存空間給我們，然后我們再將值為 3 這個尾節點的地址更新為它的地址，如下圖所示：  #### 數組與鏈表的性能差異 * [ ] 空間利用率 首先我們來一起看看在空間利用率上的對比。因為數組在創建之后大小是無法改變的，想要增加元素的話就必須重新創建一個新的數組。所以有的時候，為了能夠動態地增加元素，我們會在一開始創建數組的時候聲明一個比我們本來需要的大小還多的空間出來，以便后面添加新的元素。這個時候就會造成空間上的浪費，所以，數組的空間利用率相當于本來需要的大小除以創建出來數組的大小。 而因為鏈表中的元素只有當需要的時候才會被創建出來，所以不存在需要多預留空間的情況。對于我們工程師來說，只有節點里的值是可以利用上的，而保存節點地址的內存其實對于我們來說是無法應用的。所以鏈表的空間利用率上相當于值的大小除以值的大小和節點地址大小的和。 在我們上面所舉的例子中，因為鏈表中保存的值只是一個 int 的值，和節點地址大小一樣，所以在空間利用率上只有 50%。但是在現實應用中，鏈表中保存的值遠遠不是一個基本類型就這么簡單，當我們所保存的值的大小越大的時候，空間利用率也會越高。 * [ ] 時間復雜度 在第 01 講的內容中，我們知道了訪問數組元素的時間復雜度是 O(1)。而因為鏈表順序訪問的這個特性，訪問鏈表中第 N 個元素需要從第一個元素一直遍歷到第 N 個元素，所以平均下來的時間復雜度是 O(N)。 對于數組來說，插入操作無論是發生在數組結尾還是發生在數組的中間，因為都需要重新創建一個新的數組出來，并復制一遍之前的元素到新的數組中，所以平均的時間復雜度都是 O(N)。而對于鏈表來說，要是我們一直都能維護一個尾節點的地址的話，那么插入一個新的元素只需要 O(1) 的時間復雜度。而當插入一個元素到鏈表中間的時候，因為鏈表順序訪問的這個特性，我們需要先遍歷一遍鏈表，從第一個節點開始直到第 N 個位置，然后再進行插入，所以平均下來的時間復雜度是 O(N)。 #### 鏈表的各種形式 * [ ] 單向鏈表 在上面所舉的例子當中，你可能已經發現了，所有的鏈表節點中都只保存了指向下一個節點地址的信息。這種在一個節點中既保存了我們需要的數據，也保存了指向下一個節點地址信息的鏈表，稱之為單向鏈表（Singly Linked List）。抽象的數據圖就如下圖所示：  * [ ] 雙向鏈表 單向鏈表有著只能朝著一個方向遍歷的局限性，既然我們可以保存指向下一個節點地址的信息，也可以保存指向上一個節點地址的信息。這種在一個節點中保存了我們需要的數據也保存了連向下一個和上一個節點地址信息的鏈表，稱之為雙向鏈表（Doubly Linked List）。和鏈表中尾節點的下一個節點只保存空地址一樣，鏈表中頭節點的上一個節點地址也保存著空地址，抽象的數據圖就如下圖所示：  * [ ] 循環鏈表 無論是單向鏈表或者是雙向鏈表，當我們遍歷至尾節點之后就無法再遍歷下去了，如果將尾節點指向下一個節點地址的信息更新成指向頭節點的話，這樣整個鏈表就形成了一個環，這種鏈表稱之為循環鏈表（Circular Linked List）。抽象的數據圖就如下圖所示：  今天我們一起學習了鏈表這個基本概念以及了解了鏈表的內存結構，同時我們也對比了數組與鏈表中空間利用率以及基本操作的時間復雜度，在最后也學習了鏈表的不同表達形式。在下一講中，我將會和你一起看看環形鏈表這種數據結構是如何被大量應用在操作系統定時器和 Apache Kafka 中的。 OK，這節課就講到這里啦，下一課時我將分享“鏈表在 Apache Kafka 中的應用”，記得按時來聽課哈。