iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 4
1
Software Development

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

擁抱「資料結構」的「演算法」(04) - 單向連結串列 Singly Linked List

  • 分享至 

  • xImage
  •  

前言

陣列有一個很大的特色,就是一定要預留一段的連續空間來儲存資料,所以當有空間已經用完,且有額外的資料想要存入時,就會非常不方便,所以今天要來介紹另外一種線性串列,這一種資料結構稱為連結串列 Linked List,不用像陣列那樣需要在一開始就保留連續空間,串列的資料可以存在任意的位置,然後透過連結將資料一個一個串起來,讓我們一起來看看生活中的例子吧


生活常識

保健盒

你還記得小美吃保健食品的故事嗎?有沒有哪些情境是讓你印象深刻的,像我自己覺得保健食品盒雖然格子很多很方便,但是如果遇到放錯格子或想調整保健品的順序,真的會很崩潰,因為可能要把保健品通通拿出來再重新放一遍,很曠日廢時,但其實有一種保健盒很方便,提供了組裝功能,我們一起來看看下面的圖:

https://ithelp.ithome.com.tw/upload/images/20200918/20129841JuUAVR0HhY.png
圖片來源:momo

透過上圖,可以觀察到,每個盒子左右兩邊,分別做了凸槽凹槽設計,意思也就是說,每個盒子都是獨立的,可以單獨一格使用,也可以把很多格串再一起使用,增加了很多彈性,如果想要調整順序或數量都是很容易的事情,如果放錯格子或放錯順序,完全不需要把保健品拿出來,只需要將小格子拆下來,再重新組合即可,不像一體成形的盒子那樣,要調整就只能大搬風,保健品通通要拿出來

車廂

生活中會接觸到交通工具,像是火車,也是將很多車廂串在一起,今天要增加車廂或是減少車廂,都可以處理,因為車廂可以放在倉庫,需要用到在去挪出來並串到火車上,用講的可能不好理解,一起來欣賞一下網友提供的youtube影片

加掛車廂
Yes

維修車廂
Yes

兔子舞

童年回憶XD,每個人將雙手搭在前者的肩膀看,然後進行左跳右跳、跳跳跳的團康活動,透過我們的雙手可以快速的將人串再一起,讓活動氣氛達到最高點XD

https://ithelp.ithome.com.tw/upload/images/20200918/201298410y4FvDWyO2.jpg
圖片來源:百度百科

人脈弱連結

不知道你有沒有這樣的經驗,當今天認識一個新朋友的時候,互相加 Facebook 好友時,才發現其實你與對方有很多共同朋友,但之前都不知道;亦或是從對方的朋友清單中,發現他認識某某領域的朋友,是你也很想認識,想請他引薦的,其實人與人之間也存在某種連結,或是我們常常說的緣分,如果今天跟對方沒有緣分,就像兩條平行線,永遠沒有交集XD,如果想要有交集,就必須創造連結

如果今天小美,想邀請祖克伯來公司演講,但小美不認識祖克伯,但小美曾聽過自己的朋友小明說,他朋友小華的爸爸是祖克伯,所以今天小美在不認識小華的情況下,想要聯繫到祖克伯,就必須先拜託小明,小明再去拜託小華,小華再去拜託自己的爸爸祖克伯,才能成功讓小美直接聯繫到祖克伯
https://ithelp.ithome.com.tw/upload/images/20200918/20129841n2mbhqQ6Gb.png


專業知識 - 單向連結串列 Singly Linked List

連結串列有細分單向雙向環狀連結串列,今天先來講單向連結串列

特性

  1. 不需要預留固定數量且一段連續的儲存空間
  2. 一個節點包含資料指標
  3. 必須單向依序讀取節點,透過指標,才知道下一個要讀取哪個節點(無法像陣列透過索引就能讀取資料)
  4. 插入或新增節點很方便,只要改變指標即可

火車例子

  1. 不需要指定大小,不需要預留一段連續的儲存空間
    車廂數量沒有固定值,車廂可隨意調整,不需要連續

  2. 一個節點包含資料指標
    每個車廂都可以載,並且會以連接器串接下一個車廂

  3. 必須依序讀取節點,透過指標,才知道下一個要讀取哪個節點(無法像陣列透過索引就能讀取資料)
    火車進站時,一定會先看到第一車廂、第二車廂,依序到最後一節車廂,你一定要站在月台看到最後面,才會知道這個車次的最後一個車廂是什麼,可能是夜間婦女車廂也不一定
    https://ithelp.ithome.com.tw/upload/images/20200918/20129841QsyF2R9iPk.png

  4. 插入或新增節點很方便,只要改變指標即可
    如果今天鐵路局發現,下班時間搭乘人數很多,就可以考慮加掛車廂。如果進廠維修時,發現第四車廂發生故障,可直接將故障車廂卸下,並將正常的第三車廂繼續串接第五車廂,只要調整車廂與車廂之間的連結器即可
    https://ithelp.ithome.com.tw/upload/images/20200918/20129841O35fDKjZ0R.png


今日小結

可能會覺得串列好像比陣列更好用,其實兩者還是要依照實際需求來使用,雖然串列中的節點,可快速的新增或移除,但如果今天想快速存取某一個節點,則非常不方便,因為串列之間的節點必須依序讀取才會知道節點的指標指向哪裡,不像陣列可以透果索引直接存取資料,例如小美想到找到祖柏克,就只能透過朋友間的層層聯繫,才能找到人,但如果小美今天知道祖柏克住在哪,就能直接找到他,就不需要透過朋友穿針引線的幫忙囉,同一件事情根據情況不同,所使用的方式也會不同


今日謎題

小美發現之前的神祕客就是小乖,他想跟小乖開啟對話,但他們兩個人並不認識,必須逐一請小明、小華、小草與小英轉達,才能將訊息傳達給小乖,請問你有發現神秘圖形嗎?

https://ithelp.ithome.com.tw/upload/images/20200918/20129841g8RAxgALmu.png

昨日解謎

解謎說明:要清楚二維陣列的存取使用方式,透過索引找到相對應的儲存位置,答案就呼之欲出囉

Maps[2,2] = D
Maps[0,1] = I
Maps[3,0] = M
Maps[1,3] = E
Maps[4,0] = N
Maps[5,0] = S
Maps[5,3] = I
Maps[4,1] = O
Maps[7,1] = N

答案就是DIMENSION,維度 Dimension,你答對了嗎XD


上一篇
擁抱「資料結構」的「演算法」(03) - 多維陣列 Multidimensional Arrays
下一篇
擁抱「資料結構」的「演算法」(05) - 雙向連結串列 Doubly Linked List
系列文
擁抱「資料結構」的「演算法」30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

1
金金
iT邦新手 1 級 ‧ 2022-03-16 17:39:21

喜歡這系列~覺得解釋得很清楚又平易近人!

我要留言

立即登入留言