iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 5
0
Software Development

擁抱「資料結構」的「演算法」系列 第 5

擁抱「資料結構」的「演算法」(05) - 雙向連結串列 Doubly Linked List

前言

昨天介紹了串列,發現串列的資料可以存在任意的位置,並透過連結將資料一個一個串起來,今天要介紹雙向連結串列,一起來看看它有什麼特色吧


生活常識

大家有玩過兩人三腳嗎?或是有跟好朋友勾肩搭背的經驗嗎?通常會做這個動作,代表跟對方的關係很緊密,從下圖觀察到,大家把兩隻手各別勾到左右夥伴的身上

https://ithelp.ithome.com.tw/upload/images/20200919/20129841gcBsh2XKUq.png
圖片來源:https://www.pexels.com/zh-tw/photo/3184396/

比對昨天的兔子舞的單向隊形,隊伍只能靠帶頭的人決定,大家的眼睛只能看同一個方向,自己只知道前面是誰,但卻不知道自己後面是誰,但使用左手與右手去勾肩搭背的隊形,大家都會很清楚自己的左邊跟右邊是誰,如果唱名本隊形的組員名字,不管是由右往左唱名,或由左往右唱名,都沒有問題

如果上圖中間穿著黑色裙子的小美,她將自己的左右手都放下,這群人也不會被拆散,因為小美的左邊與右邊的人的手,都還勾再小美身上,相對地這種隊形是更加緊密的


專業知識 - 雙向連結串列 Doubly Linked List

特色

  1. 一個節點包含資料2 個指標(指向前面與後面)
  2. 雙向讀取節點
  3. 可快速修補脫落的節點

依播放廣告為例,可由左而右讀取資料,也可以由右而左讀取資料
https://ithelp.ithome.com.tw/upload/images/20200919/20129841h98hdYrD6F.png

如果要新增中秋節的廣告,會需要調整 4 個指標
https://ithelp.ithome.com.tw/upload/images/20200919/20129841B1aAiEgHYK.png

如果要刪除3C大放送的廣告,會需要調整 2 個指標
https://ithelp.ithome.com.tw/upload/images/20200919/20129841GnrIcymdJh.png

程式碼

透過 C# 內建的 LinkedList 類別,不需要手動更換指標,即可簡易操作節點的新增或刪除,,以下以新增節點為例:

var list = new LinkedList<string>(); //建立廣告
list.AddLast("開學季");
list.AddLast("品牌日");
list.AddLast("3C大放送");
list.AddLast("集點加價購");
list.AddLast("周年慶");

Console.WriteLine("--------廣告--------");
foreach (var data in list)
{ 
    Console.WriteLine(data);//逐一印出廣告
}

LinkedListNode<String> year = list.Find("周年慶"); //找到周年慶的結點
list.AddBefore(year, "中秋節"); //在周年慶之前,新增中秋節廣告
Console.WriteLine("\n--------廣告--------");
foreach (var data in list)
{ 
    Console.WriteLine(data);//逐一印出廣告
}

程式輸出結果:

--------廣告--------
開學季
品牌日
3C大放送
集點加價購
周年慶

--------廣告--------
開學季
品牌日
3C大放送
集點加價購
中秋節
周年慶

今日小結

雖然雙向連結可緊密連結資料,可雙向讀取,但相對應也會有衍生的問題:

  • 較浪費空間(含有 2 個指標)
  • 加入節點(改變 4 個指標)與刪除節點(改變 2 個指標),比較困難

今日謎題

請猜一個的特殊世界節日
https://ithelp.ithome.com.tw/upload/images/20200919/20129841zA4YNzTddI.png

昨日解謎

解謎說明:依照傳話順序連線,就可以得到五盲星的圖形囉

https://ithelp.ithome.com.tw/upload/images/20200919/20129841v48C5hwP7V.png


上一篇
擁抱「資料結構」的「演算法」(04) - 單向連結串列 Singly Linked List
下一篇
擁抱「資料結構」的「演算法」(06) - 環狀連結串列 Circular Linked List
系列文
擁抱「資料結構」的「演算法」30

尚未有邦友留言

立即登入留言