擁抱「資料結構」的「演算法」(05) - 雙向連結串列 Doubly Linked List
前言
昨天介紹了串列，發現串列的資料可以存在任意的位置，並透過連結將資料一個一個串起來，今天要介紹雙向連結串列，一起來看看它有什麼特色吧
生活常識
大家有玩過兩人三腳嗎？或是有跟好朋友勾肩搭背的經驗嗎？通常會做這個動作，代表跟對方的關係很緊密，從下圖觀察到，大家把兩隻手各別勾到左右夥伴的身上
圖片來源:https://www.pexels.com/zh-tw/photo/3184396/
比對昨天的兔子舞的單向隊形，隊伍只能靠帶頭的人決定，大家的眼睛只能看同一個方向，自己只知道前面是誰，但卻不知道自己後面是誰，但使用左手與右手去勾肩搭背的隊形，大家都會很清楚自己的左邊跟右邊是誰，如果唱名本隊形的組員名字，不管是由右往左唱名，或由左往右唱名，都沒有問題
如果上圖中間穿著黑色裙子的小美，她將自己的左右手都放下，這群人也不會被拆散，因為小美的左邊與右邊的人的手，都還勾再小美身上，相對地這種隊形是更加緊密的
專業知識 - 雙向連結串列 Doubly Linked List
特色
- 一個
節點包含資料與2 個指標(指向前面與後面) - 可
雙向讀取節點 - 可快速修補脫落的節點
依播放廣告為例，可由左而右讀取資料，也可以由右而左讀取資料
如果要新增中秋節的廣告，會需要調整 4 個指標
如果要刪除3C大放送的廣告，會需要調整 2 個指標
程式碼
透過 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 個指標)，比較困難
今日謎題
請猜一個的特殊世界節日
昨日解謎
解謎說明：依照傳話順序連線，就可以得到五盲星的圖形囉
留言
張貼留言