每周一數據結構之鏈表(Kotlin描述)
一、鏈表的定義
鏈表是一種遞歸的數據結構，是一種線性結構，但是并不會按線性的順序存儲數據，而是在每一個節點里存到下一個節點的指針(Pointer)，簡單來說鏈表并不像數組那樣將數組存儲在一個連續的內存地址空間里，它們可以不是連續的因為他們每個節點保存著下一個節點的引用（地址）
二、鏈表的類型
單鏈表
1、定義
一、鏈表的定義
鏈表是一種遞歸的數據結構，是一種線性結構，但是并不會按線性的順序存儲數據，而是在每一個節點里存到下一個節點的指針(Pointer)，簡單來說鏈表并不像數組那樣將數組存儲在一個連續的內存地址空間里，它們可以不是連續的因為他們每個節點保存著下一個節點的引用（地址）
二、鏈表的類型
1、定義
單鏈表(又稱單向鏈表)是鏈表中的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要從頭部(head)開始，然后依次通過next指針讀取下一個節點。
2、數據結構
單鏈表的數據結構可以分為兩部分：數據域和指針域，數據域存儲數據，指針域指向下一個存儲節點的地址。注意: 單向鏈表只可向一個方向進行遍歷
3、節點代碼描述
//(Kotlin描述)
class?LinkedNode(var?value:?Int)?{
var?next:?LinkedNode??=?null?//指向下一個存儲節點的next指針
}
//(Java描述)
public?class?LinkedNode?{
int?value;
LinkedNode?next;?//指向下一個存儲節點的next指針
public?LinkedNode(int?value)?{
this.value?=?value;
}
}
1、定義
雙鏈表(又稱雙向鏈表)，是鏈表中一種，與單鏈表不同的是它的每個節點都有兩個指針，分別指向直接后繼節點和直接前驅節點；所以，從雙鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。
2、數據結構
雙鏈表的數據結構可以分為三部分：prev指針域、數據域和next指針域，prev指針域指向上一個存儲節點的地址(也即指向直接前驅節點),數據域存儲數據，next指針域指向下一個存儲節點的地址(也即指向直接后繼節點)。注意: 單向鏈表可向兩個方向進行遍歷,分別為正序和逆序遍歷
3、節點代碼描述
//(Kotlin描述)
class?LinkedNode(var?value:?Int)?{
var?prev:?LinkedNode??=?null?//指向上一個存儲節點的prev指針
var?next:?LinkedNode??=?null?//指向下一個存儲節點的next指針
}
//(Java描述)
public?class?LinkedNode?{
int?value;
LinkedNode?prev;?//指向上一個存儲節點的prev指針
LinkedNode?next;?//指向下一個存儲節點的next指針
public?LinkedNode(int?value)?{
this.value?=?value;
}
}
1、定義
單向循環鏈表，只是在單鏈表的基礎上，它的最后一個結點不再為null而是指向頭結點，形成一個環。并且在節點結構上和單鏈表是一樣的。因此，從單向循環鏈表中的任何一個結點出發都能找到任何其他結點。
2、數據結構
1、定義
雙向循環鏈表，只是在雙鏈表的基礎，它的頭節點的prev指針不再為null，而是直接指向它的尾節點；它的尾節點的next指針不再為null，而是直接指向它的頭節點。
2、數據結構
三、鏈表的特點
1、在內存中不是連續的內存地址空間，它只是一種邏輯上的線性連續結構。每個節點都含有指向下一個節點的next指針(可能指向下一個節點或null)
2、鏈表在節點的刪除和增加有著很高效率，基本是O(1)常數級的時間效率，而順序表實現刪除和增加操作則是線性級O(n)的時間效率。所以一般用于用于元素節點頻繁刪除和增加
3、而對于鏈表的查找和獲得第K個鏈表中節點，往往需要采用遍歷的方式實現，所以一般需要O(n)的時間效率
4、鏈表長度是可變的，也就意味著在內存空間足夠范圍內，鏈表長度可以無限擴大。而順序表則一般是固定的，當超出長度的時候則會進行擴容。
四、鏈表的基本操作
我們知道一個節點類型的變量就可以表示一條鏈表，只要保證對應的每個節點的next指針能夠指向下一個節點即可或指向null(表示鏈表最后一個節點)
1、單鏈表的構造
//鏈表結構定義
class?LinkedNode(var?value:?Int)?{
var?next:?LinkedNode??=?null
}
//鏈表的構造
fun?main(args:?Array
val?node1?=?LinkedNode(value?=?1)//創建節點1
val?node2?=?LinkedNode(value?=?2)//創建節點2
val?node3?=?LinkedNode(value?=?3)//創建節點3
node1.next?=?node2//通過node1的next指針指向node2，把node1和node2連接起來
node2.next?=?node3//通過node2的next指針指向node3，把node2和node3連接起來
}
2、雙鏈表的構造
class?LinkedNode(var?value:?Int)?{
var?prev:?LinkedNode??=?null
var?next:?LinkedNode??=?null
}
fun?main(args:?Array
val?node1?=?LinkedNode(value?=?1)//創建節點1?此時的prev,next均為null
val?node2?=?LinkedNode(value?=?2)//創建節點2?此時的prev,next均為null
val?node3?=?LinkedNode(value?=?3)//創建節點3?此時的prev,next均為null
node1.next?=?node2?//node1的next指針指向直接后繼節點node2
node2.prev?=?node1?//node2的prev指針指向直接前驅節點node1
node2.next?=?node3?//node2的next指針指向直接后繼節點node3
node3.prev?=?node2?//node3的prev指針指向直接前驅節點node2
}
在鏈表表頭插入一個節點是最簡單的一種操作，一般處理方式，先創建一個oldFirst指向第一個節點，然后重新創建一個新的節點,將新節點的next指向oldFirst指向的節點，first指向新插入的節點。
1、單鏈表表頭插入節點
fun?insertToHead(head:?LinkedNode):?LinkedNode?{
var?first:?LinkedNode?=?head
val?oldFirst:?LinkedNode?=?head
first?=?LinkedNode(value?=?6)
first.next?=?oldFirst
return?first
}
2、雙鏈表表頭插入節點
fun?insertToHead(head:?LinkedNode):?LinkedNode?{
var?first:?LinkedNode?=?head
val?oldFirst:?LinkedNode?=?head
first?=?LinkedNode(value?=?6)
oldFirst.prev?=?first
first.next?=?oldFirst
return?first
}
1、單鏈表表頭刪除節點
fun?deleteToHead(head:?LinkedNode):?LinkedNode??{
var?first:?LinkedNode??=?head
first?=?first?.next
return?first
}
2、雙鏈表表頭刪除節點
fun?deleteToHead(head:?LinkedNode):?LinkedNode??{
var?first:?LinkedNode??=?head
first?=?first?.next
first?.prev?=?null
return?first
}
1、單鏈表尾部插入節點
fun?insertToTail(head:?LinkedNode):?LinkedNode??{
var?last?=?getTailNode(head)?//通過遍歷得到尾部節點
val?oldLast?=?last
last?=?LinkedNode(value?=?4)
oldLast?.next?=?last
return?head
}
2、雙鏈表尾部插入節點
fun?insertToTail(head:?LinkedNode):?LinkedNode??{
var?last?=?getTailNode(head)?//通過遍歷得到尾部節點
val?oldLast?=?last
last?=?LinkedNode(value?=?4)
oldLast?.next?=?last
last.prev?=?oldLast
return?head
}
1、單鏈表其他位置插入節點
fun?insertToOther(head:?LinkedNode):?LinkedNode??{
val?current?=?getInsertPrevNode(head)?//拿到需要的插入位置的上一個節點
val?newNode?=?LinkedNode(value?=?6)
newNode.next?=?current?.next//?新插入的節點next指向插入位置的上一個節點的next
current?.next?=?newNode//然后斷開插入位置的上一個節點的next，并把指向新插入的節點
return?head
}
2、雙鏈表其他位置插入節點
fun?insertToOther(head:?LinkedNode):?LinkedNode??{
val?current?=?getInsertPrevNode(head)?//拿到需要的插入位置的上一個節點
val?newNode?=?LinkedNode(value?=?6)
newNode.next?=?current?.next//?新插入的節點next指向插入位置的上一個節點的next
newNode.prev?=?current?//新插入的節點prev指向插入位置的上一個節點
current?.next?=?newNode//然后斷開插入位置的上一個節點的next，并把它指向新插入的節點
current?.next?.prev?=?newNode?//然后斷開插入位置的上一個節點的prev,并把它指向新插入的節點
return?head
}
1、單鏈表其他位置刪除節點
fun?deleteToOther(head:?LinkedNode):?LinkedNode??{
val?current?=?getInsertPrevNode(head)?//拿到需要的刪除節點的上一個節點
current?.next?=?current?.next?.next
return?head
}
2、雙鏈表其他位置刪除節點
fun?deleteToOther(head:?LinkedNode):?LinkedNode??{
val?current?=?getDeletePrevNode(head)?//拿到需要的刪除節點的上一個節點
current?.next?=?current?.next?.next
current?.next?.prev?=?current
return?head
}
fun?traverseLinkedList(head:?LinkedNode?)?{
var?current?=?head
while?(current?!=?null){
println(current.value)
current?=?current.next
}
}
fun?getLength(head:?LinkedNode?):?Int?{
var?len?=?0
var?current?=?head
while?(current?!=?null){
len++
current?=?current.next
}
return?len
}
五、鏈表實現棧和隊列數據結構
由于棧是一個表，因此任何實現表的方法都能實現棧。顯然，Java中常用的ArrayList和LinkedList集合都是支持棧操作的。
實現思路
單鏈表也是能實現棧的，通過在表的頂端插入實現棧的push壓棧操作，通過刪除表的頂端元素實現pop入棧操作。top操作只需要返回頂部的元素的值即可。
實現代碼
class?LinkedStack?{
private?var?first:?Node??=?null
private?var?len:?Int?=?0
fun?push(value:?Int)?{//相當于鏈表從表頭插入新的元素
val?oldFirst?=?first
first?=?Node(value)
first?.next?=?oldFirst
len++
}
fun?pop():?Int?{//相當于鏈表從表頭刪除新的元素
val?value?=?first?.value
first?=?first?.next
return?value??:?-1
}
fun?top():?Int?{
return?first?.value??:?-1
}
fun?isEmpty():?Boolean?{
return?first?==?null
}
fun?size():?Int?{
return?len
}
inner?class?Node(var?value:?Int)?{
var?next:?Node??=?null
}
}
class?LinkedQueue?{
private?var?first:?Node??=?null
private?var?last:?Node??=?null
private?var?len:?Int?=?0
fun?enqueue(value:?Int)?{//相當于鏈表從尾部插入新的節點
val?oldLast?=?last
last?=?Node(value)
last?.next?=?null
if?(isEmpty())?{
first?=?last
}?else?{
oldLast?.next?=?last
}
len++
}
fun?dequeue():?Int?{//相當于鏈表從尾部刪除最后節點
val?value?=?first?.value??:?-1
first?=?first?.next
if?(isEmpty())?{
last?=?null
}
return?value
}
fun?isEmpty():?Boolean?{
return?first?==?null
}
fun?size():?Int?{
return?len
}
inner?class?Node(var?value:?Int)?{
var?next:?Node??=?null
}
}
六、鏈表反轉問題
1、定義
鏈表反轉(也稱鏈表的逆序)是鏈表中一種比較經典的操作，在一些數據結構的題目鏈表的反轉也是常考點，鏈表的反轉也會做為一部分融入題目，比如回文鏈表問題等
2、實現過程
3、代碼描述
fun?reverseLinkedList(head:?LinkedNode?):?LinkedNode??{
var?prev:?LinkedNode??=?null
var?current:?LinkedNode??=?head
var?next:?LinkedNode??=?head
while?(current?!=?null)?{
next?=?current.next
current.next?=?prev
prev?=?current
current?=?next
}
return?prev
}
七、鏈表中經典快慢指針問題
快慢指針追趕問題在鏈表中是非常經典的，快慢指針問題一般用于解決鏈表中間節點問題和鏈表是否含有環以及鏈表中環的入口位置等問題。
如果使用快慢指針是判斷鏈表是否含有環的問題，我們更希望fast和slow指針的相對路程是正好是環的長度，(也就是slow指針剛進入環，而fast指針剛繞環一圈，此時兩指針正好相遇)這樣兩個指針就相遇了。這樣取每步的速度差能夠被環長度整除的數字。但是我們并不知道環的具體長度，所以只能取每步的速度差能夠被環長度整除的數字為1(1能被所有的數整除),所以我們取fast指針每次走2步，slow指針每次走1步，實際上只要保證兩者速度差為1就可以了，你甚至可以fast每次走3步，slow指針每次走2步都是可以的，這樣一來只要它們在環里面就一定能相遇。
public?boolean?hasCycle(ListNode?head)?{
if(head?==?null?||?head.next?==?null)?return?false;
ListNode?slow?=?head;
ListNode?fast?=?head;
while(fast?!=?null?&&?fast.next?!=?null){
slow?=?slow.next;//慢指針每次走1步
fast?=?fast.next.next;//快指針每次走2步
if(slow?==?fast){//如果鏈表存在環，那么slow和fast指針會相遇
return?true;
}
}
return?false;
}
由快慢指針追趕的原理可知，如果fast指針和slow指針同時從鏈表(鏈表不含環)的頭結點出發開始遍歷，如果fast指針的每次遍歷步數是slow指針的兩倍，那么可得到如果fast遍歷到鏈表的尾部，那么此時的slow指針應該處于鏈表的中間節點位置(具體題目可參考：LeetCode第876題)。
public?ListNode?middleNode(ListNode?head)?{
if(head?==?null)?return?null;
ListNode?slow?=?head;
ListNode?fast?=?head;
while(fast?!=?null?&&?fast.next?!=?null){
slow?=?slow.next;
fast?=?fast.next.next;
}
return?slow;
}
八、LeetCode鏈表相關題目
1、刪除鏈表的節點
2、反轉鏈表
3、鏈表的中間節點
4、合并兩個有序鏈表
5、刪除排序鏈表中的重復元素
6、移除鏈表中的元素
7、相交鏈表
8、環形鏈表
9、回文鏈表
10、設計鏈表
歡迎關注Kotlin開發者聯盟，這里有最新Kotlin技術文章，每周會不定期翻譯一篇Kotlin國外技術文章。如果你也喜歡Kotlin，歡迎加入我們~~~
Kotlin系列文章，歡迎查看:
Kotlin邂逅設計模式系列:
當Kotlin完美邂逅設計模式之單例模式(一)
數據結構與算法系列:
每周一算法之二分查找(Kotlin描述)
翻譯系列：
[譯] Kotlin中關于Companion Object的那些事
[譯]記一次Kotlin官方文檔翻譯的PR(內聯類)
[譯]Kotlin中內聯類的自動裝箱和高性能探索(二)
[譯]Kotlin中內聯類(inline class)完全解析(一)
[譯]Kotlin的獨門秘籍Reified實化類型參數(上篇)
[譯]Kotlin泛型中何時該用類型形參約束?
[譯] 一個簡單方式教你記住Kotlin的形參和實參
[譯]Kotlin中是應該定義函數還是定義屬性?
[譯]如何在你的Kotlin代碼中移除所有的!!(非空斷言)
[譯]掌握Kotlin中的標準庫函數: run、with、let、also和apply
[譯]有關Kotlin類型別名(typealias)你需要知道的一切
[譯]Kotlin中是應該使用序列(Sequences)還是集合(Lists)?
[譯]Kotlin中的龜(List)兔(Sequence)賽跑
原創系列：
教你如何完全解析Kotlin中的類型系統
如何讓你的回調更具Kotlin風味
Jetbrains開發者日見聞(三)之Kotlin1.3新特性(inline class篇)
JetBrains開發者日見聞(二)之Kotlin1.3的新特性(Contract契約與協程篇)
JetBrains開發者日見聞(一)之Kotlin/Native 嘗鮮篇
教你如何攻克Kotlin中泛型型變的難點(實踐篇)
教你如何攻克Kotlin中泛型型變的難點(下篇)
教你如何攻克Kotlin中泛型型變的難點(上篇)
Kotlin的獨門秘籍Reified實化類型參數(下篇)
有關Kotlin屬性代理你需要知道的一切
淺談Kotlin中的Sequences源碼解析
淺談Kotlin中集合和函數式API完全解析-上篇
淺談Kotlin語法篇之lambda編譯成字節碼過程完全解析
淺談Kotlin語法篇之Lambda表達式完全解析
淺談Kotlin語法篇之擴展函數
淺談Kotlin語法篇之頂層函數、中綴調用、解構聲明
淺談Kotlin語法篇之如何讓函數更好地調用
淺談Kotlin語法篇之變量和常量
淺談Kotlin語法篇之基礎語法
Effective Kotlin翻譯系列
[譯]Effective Kotlin系列之考慮使用原始類型的數組優化性能(五)
[譯]Effective Kotlin系列之使用Sequence來優化集合的操作(四)
[譯]Effective Kotlin系列之探索高階函數中inline修飾符(三)
[譯]Effective Kotlin系列之遇到多個構造器參數要考慮使用構建器(二)
[譯]Effective Kotlin系列之考慮使用靜態工廠方法替代構造器(一)
實戰系列:
用Kotlin擼一個圖片壓縮插件ImageSlimming-導學篇(一)
用Kotlin擼一個圖片壓縮插件-插件基礎篇(二)
用Kotlin擼一個圖片壓縮插件-實戰篇(三)
淺談Kotlin實戰篇之自定義View圖片圓角簡單應用
Java Kotlin
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
