Adslv ·1. 前言
我們今天要通過了解鏈表的原理來掌握鏈表這個重要的數據結構，隨后用我們了解到的鏈表的知識來重新認識一下我們每天都要接觸的最常見的鏈表 java.util.LinkedList 類。
2. 數組的缺陷
數組作為我們最常見的通用數據結構，幾乎可以實現我們常見的所有數據結構。然而，數組的特點決定了它的適用場景必然是有限的，比如占用空間大小固定，空間過小可能不能滿足數據量的要求，空間過大又會造成內存資源的浪費，再比如數組的插入效率很低等等。
那有沒有一種插入效率很高，而且不需要頻繁擴容的基本數據結構呢？答案是肯定的，它就是 —— 鏈表。
3. 什么是鏈表
鏈表是一組鏈式結構的數據節點，每個節點都包含保存數據的部分，以及用來指向上一個或下一個節點位置的鏈接信息。鏈表是一種線性表，它可以靈活的根據數據大小來使用內存空間，但是由于它在內存中不是連續存儲的，所以根據角標查詢的效率很低，同時由于每一個節點上除了數據信息還額外存儲了與其他節點的鏈接信息，所以對空間的占用也更大一些。
4. 單向鏈表
我們首先通過最簡單的鏈表 —— 單向鏈表來熟悉一下鏈表的結構和存儲原理。
單鏈表的每一個節點我們稱之為 Node，都包含一個存儲數據的部分我們稱為之 data，還有一部分用來存儲下一個節點的地址我們稱之為 links。鏈表的第一個節點我們稱之為 head 頭節點。
5. 雙端鏈表
單向鏈表由于只記錄了自己的下一個節點，所以它的訪問方向是單向的。如果我想在最后一個節點后添加元素，就需要從第一個節點開始挨個遍歷，很不方便，于是我們給鏈表的最后一個節點標示為 tail 尾節點，便于我們在最后一個節點插入元素的時候可以直接引用尾節點，這就叫做雙端鏈表。
6. 雙向鏈表
前面講的單向鏈表和雙端鏈表其實主要是讓大家了解鏈表的存儲原理，實際我們使用最多的是雙向鏈表，雙向鏈表在單向鏈表的基礎上同時記錄了上一個節點和下一個節點兩個指針信息，遍歷更加方便。
Java 中對于雙向鏈表有現成的實現，就是我們非常熟悉的 java.util.LinkedList。在源碼中我們可以看到 LinkedList 把節點定義成三個部分：元素、上一節點和下一節點。
其實鏈表的最大的魅力就是可以優雅高效地插入數據，它只需要在要插入的位置修改前后節點的指針就可以完成，完全不需要移動其他的數據。LinkedList 源碼中是這樣實現的：
結合上圖，我們用動圖來模擬實現一下 LinkedList 的 add 方法：
動圖中的節點位置我故意擺放得很零散，就是為了突出這些節點在內存中的位置并不是連續的，這也體現出了鏈表可以對內存里這些零散角落高效利用的特點。
對于刪除操作，鏈表完全可以根據插入的逆操作來高效優雅地完成。
7. 鏈表的優缺點
鏈表的優點是大小可變，插入和刪除的效率很高，缺點是只能通過順序指針訪問，查詢的效率較低。無圖無真相，我們結合圖片看一下他們分別是如何獲取指定元素的。先來看下基于數組的 ArrayList：
再來看下基于鏈表的 LinkedList:
對比基于數組的 ArrayList 和基于鏈表的 LinkedList 的 get (index i) 方法的實現就會發現，鏈表需要遍歷才能返回想要的元素，所以效率才比較低下。知道了鏈表的這些特性，我們今后在使用這一數據結構的時候就知道如何讓它在合適的時候發揮它的最大優勢咯。
8. 小結
這一小節我們知道了鏈表是一種線性結構的基本數據類型，可以分為單向鏈表、雙端鏈表、雙向鏈表等，內部實現的原理都是在每一個節點上除了記錄數據外，還記錄了上一個或下一個節點的位置信息。它的特點是插入和刪除的效率很高，查詢的效率較低。
2025 imooc.com All Rights Reserved |