前言
有的小伙伴說沒有學過數據結構,對鏈表不是特別了解,所以今天我們就來對鏈表進行一個系統(tǒng)的總結,另外大家如果想提高算法思想的話,我建議還是要系統(tǒng)的學一下數據結構的。閱讀完本文你會有以下收獲1.知道什么是鏈表?2.了解鏈表的幾種類型。3.了解鏈表如何構造。4.鏈表的存儲方式5.如何遍歷鏈表6.了解鏈表的操作。7.知道鏈表和數組的不同點8.掌握鏈表的經典題目。鏈表的定義:
定義:鏈表是一種遞歸的數據結構,他或者為空(null),或者是指向一個結點(node)的引用,該結點含有一個泛型的元素和一個指向另一條鏈表的引用。我們來對其解讀一下,鏈表是一種常見且基礎的數據結構,是一種線性表,但是他不是按線性順序存取數據,而是在每一個節(jié)點里存到下一個節(jié)點的地址。我們也可以這樣理解,鏈表是通過指針串聯在一起的線性結構,每一個鏈表結點由兩部分組成,數據域及指針域,鏈表的最后一個結點指向null。也就是我們所說的空指針。
鏈表的幾種類型
我們先來看一下鏈表的可視化表示方法,以便更好的對其理解。-
用長方形表示對象
-
將實例變量的值寫在長方形中;
-
用指向被引用對象的箭頭表示引用關系。
單鏈表
一個單向鏈表包含兩個值: 當前節(jié)點的值和一個指向下一個節(jié)點的鏈接。我們通過上面說到的可視化表示方法,將單鏈表可視化,如圖所示。
雙向鏈表
上面提到了單鏈表的節(jié)點只能指向節(jié)點的下一個節(jié)點。而雙向鏈表有三個整數值: 數值、向后的節(jié)點鏈接、向前的節(jié)點鏈接,所以雙鏈表既能向前查詢也可以向后查詢。還有一個常用的鏈表則為循環(huán)單鏈表,則單鏈表尾部的指針指向頭節(jié)點。例如在 leetcode61旋轉鏈表中,我們就是先將鏈表閉合成環(huán),找到新的打開位置,并定義新的表頭和表尾。
構造鏈表
java是面向對象語言,實現鏈表很容易。我們首先用一個嵌套類來定義節(jié)點的抽象數據類型private class Node{
Item item;
Node next;
}
現在我們需要構造一條含有one,two,three的鏈表,我們首先為每個元素創(chuàng)造一個節(jié)點
Node first = new Node();
Node second = new Node();
Node third = new Node();
將每個節(jié)點的item域設為所需的值
first.item = "one";
second.item = "two";
third.item = "three";
然后我們設置next域來構造鏈表
first.next = second;
second.next = third;
注:此時third的next仍為null,即被初始化的值。
鏈表的存儲方式
我們知道了如何構造鏈表,我們再來說一下鏈表的存儲方式。
我們都知道數組在內存中是連續(xù)分布的,但是鏈表在內存不是連續(xù)分配的。鏈表是通過指針域的指針鏈接內存中的各個節(jié)點。
所以鏈表在內存中是散亂分布在內存中的某地址上,分配機制取決于操作系統(tǒng)的內存管理。我們可以根據下圖來進行理解。
遍歷鏈表
鏈表的遍歷我們通常使用while循環(huán)(for循環(huán)也可以但是代碼不夠簡潔)下面我們來看一下鏈表的遍歷代碼
for:
for(Node x = first;x!=null;x=x.next){
//處理x.item
}
while:
Node x = first; while(x!=null){
//處理x.item
x=x.next;
}
鏈表的幾種操作
添加節(jié)點
添加節(jié)點E,如圖所示
刪除節(jié)點
刪除B節(jié)點,如圖所示
我們只需將A節(jié)點的next指針指向C節(jié)點即可。
有的同學可能會有這種疑問,B節(jié)點這樣不會留著內存里嗎?java含有自己的內存回收機制,不用自己手動釋放內存了,但是C++,則需要手動釋放。
我們通過上圖知道了刪除和插入都是O(1)操作。
鏈表和數組的比較
插入/刪除操作(時間復雜度)
查詢(時間復雜度)
存儲方式
數組
O(n)
O(1)
內存連續(xù)分布
鏈表
O(1)
O(n)
內存散亂分布
鏈表經典題目
我們上周做了很多鏈表的題目,全部都是在題庫中精挑細選出來的,掌握了那些題目不僅能夠掌握了鏈表的基本操作,而且還能學到很多算法思想,以后我們再遇到鏈表的題目就可以往我們的框架上靠。
鏈表必會題目:
雙指針思想
老鷹:我要抓走倒數第K個小雞
老鷹:一口氣吃掉一半小雞仔
兜兜轉轉還是你
遇見
合二為一
刪除節(jié)點
我們長的像是我們的錯嗎?
大家完成了這些題目應該就會對鏈表有自己的理解了,對其他鏈表題目也不會一頭霧水了,大家記得打卡呀。
END
來源:袁廚的算法小屋,作者:程序員愛做飯
版權歸原作者所有,如有侵權,請聯系刪除。
免責聲明:本文內容由21ic獲得授權后發(fā)布,版權歸原作者所有,本平臺僅提供信息存儲服務。文章僅代表作者個人觀點,不代表本平臺立場,如有問題,請聯系我們,謝謝!