前言

有的小伙伴說沒有學過數據結構，對鏈表不是特別了解，所以今天我們就來對鏈表進行一個系統的總結，另外大家如果想提高算法思想的話，我建議還是要系統的學一下數據結構的。閱讀完本文你會有以下收獲1.知道什么是鏈表？2.了解鏈表的幾種類型。3.了解鏈表如何構造。4.鏈表的存儲方式5.如何遍歷鏈表6.了解鏈表的操作。7.知道鏈表和數組的不同點8.掌握鏈表的經典題目。

鏈表的定義：

定義：鏈表是一種遞歸的數據結構，他或者為空(null)，或者是指向一個結點(node)的引用，該結點含有一個泛型的元素和一個指向另一條鏈表的引用。

我們來對其解讀一下，鏈表是一種常見且基礎的數據結構，是一種線性表，但是他不是按線性順序存取數據，而是在每一個節點里存到下一個節點的地址。我們也可以這樣理解，鏈表是通過指針串聯在一起的線性結構，每一個鏈表結點由兩部分組成，數據域及指針域，鏈表的最后一個結點指向null。也就是我們所說的空指針。

鏈表的幾種類型

我們先來看一下鏈表的可視化表示方法，以便更好的對其理解。

• 用長方形表示對象

• 將實例變量的值寫在長方形中；

• 用指向被引用對象的箭頭表示引用關系。

單鏈表

一個單向鏈表包含兩個值: 當前節點的值和一個指向下一個節點的鏈接。我們通過上面說到的可視化表示方法，將單鏈表可視化，如圖所示。

雙向鏈表

上面提到了單鏈表的節點只能指向節點的下一個節點。而雙向鏈表有三個整數值: 數值、向后的節點鏈接、向前的節點鏈接，所以雙鏈表既能向前查詢也可以向后查詢。

還有一個常用的鏈表則為循環單鏈表，則單鏈表尾部的指針指向頭節點。例如在leetcode61旋轉鏈表中，我們就是先將鏈表閉合成環，找到新的打開位置，并定義新的表頭和表尾。

構造鏈表

java是面向對象語言，實現鏈表很容易。我們首先用一個嵌套類來定義節點的抽象數據類型

private?class?Node{
??Item?item;
??Node?next;
}

現在我們需要構造一條含有one,two,three的鏈表，我們首先為每個元素創造一個節點

Node?first?=?new?Node();
Node?second?=?new?Node();
Node?third?=?new?Node();

將每個節點的item域設為所需的值

first.item?=?"one";
second.item?=?"two";
third.item?=?"three";

然后我們設置next域來構造鏈表

first.next?=?second;
second.next?=?third;

注：此時third的next仍為null，即被初始化的值。

鏈表的存儲方式

我們知道了如何構造鏈表，我們再來說一下鏈表的存儲方式。

我們都知道數組在內存中是連續分布的，但是鏈表在內存不是連續分配的。鏈表是通過指針域的指針鏈接內存中的各個節點。

所以鏈表在內存中是散亂分布在內存中的某地址上，分配機制取決于操作系統的內存管理。我們可以根據下圖來進行理解。

遍歷鏈表

鏈表的遍歷我們通常使用while循環(for循環也可以但是代碼不夠簡潔)下面我們來看一下鏈表的遍歷代碼

for:

for(Node?x?=?first;x!=null;x=x.next){
?????//處理x.item
}

while:

Node?x?=?first;
while(x!=null){
??//處理x.item
??x=x.next;
}

鏈表的幾種操作

添加節點

添加節點E，如圖所示

刪除節點

刪除B節點，如圖所示

我們只需將A節點的next指針指向C節點即可。

有的同學可能會有這種疑問，B節點這樣不會留著內存里嗎？java含有自己的內存回收機制，不用自己手動釋放內存了，但是C++,則需要手動釋放。

我們通過上圖知道了刪除和插入都是O(1)操作。

鏈表和數組的比較

	插入/刪除操作(時間復雜度)	查詢(時間復雜度)	存儲方式
數組	O(n)	O(1)	內存連續分布
鏈表	O(1)	O(n)	內存散亂分布

鏈表經典題目

我們上周做了很多鏈表的題目，全部都是在題庫中精挑細選出來的，掌握了那些題目不僅能夠掌握了鏈表的基本操作，而且還能學到很多算法思想，以后我們再遇到鏈表的題目就可以往我們的框架上靠。

鏈表必會題目：

雙指針思想

老鷹：我要抓走倒數第K個小雞

老鷹：一口氣吃掉一半小雞仔

兜兜轉轉還是你

遇見

合二為一

刪除節點

我們長的像是我們的錯嗎？

大家完成了這些題目應該就會對鏈表有自己的理解了，對其他鏈表題目也不會一頭霧水了，大家記得打卡呀。

大家如果覺得這篇文章對大家有幫助的話，就請你將它轉發給需要的人吧，順便請大家點個關注和在看吧。掃碼關注程序員愛做飯，讓我們一起領略代碼的魅力吧。長按掃一掃在這里你一定有所收獲。

? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ?

總結

以上是生活随笔為你收集整理的利用双向循环链表实现长整数的存储_链表看这一篇真的就够了！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。