iT邦幫忙

2021 iThome 鐵人賽

DAY 6
0
Software Development

程式菜鳥自學C++資料結構演算法系列 第 6

[Day06]程式菜鳥自學C++資料結構演算法 – 常見的線性串列其一:鏈結串列Linked List

前言:討論完陣列之後接著就要來看看它的好兄弟鏈結串列Linked List,在Day03的文章中有提到陣列是屬於靜態資料結構,而鏈結串列則是屬於動態資料結構,接下來就解釋一下動態資料結構的特點。

鏈結串列(動態資料結構)的特性:

  1. 是一種將線性串列的資料使用不連續記憶空間來儲存
  2. 優點是資料的插入或刪除都相當方便,不需要移動大量資料
  3. 記憶體配置是在執行時才發生,所以不需事先宣告,能夠充份節省記憶體空間。
  4. 缺點就是設計資料結構時較為麻煩,另外在搜尋資料時,也無法像靜態資料一般可隨機讀取資料,必須循序找到該資料為止

看起來很難理解,那生活中有沒有甚麼相似的實物?
https://ithelp.ithome.com.tw/upload/images/20210920/20140187IpsGJrdyXX.png
圖片來源:https://img.pcstore.com.tw/~prod/M17326047/_sE_5938373233.jpg?pimg=static&P=1400414726
活頁筆記本的便利之處想必大家都非常清楚,這種筆記本不管是在新增或移除葉面都相當方便,但如果沒有標上頁數,在尋找想要的內容之前是不是都得把筆記本都翻過一遍?
活頁筆記本是否和連結串列有異曲同工之處呢?或著是可以加減車廂的捷運也是一樣的道理喔!

單向鏈結串列:

再來就是比較專門的知識了,鏈結串列還能再細分成單向雙向環狀三種,先來看看單向鏈結串列。
https://ithelp.ithome.com.tw/upload/images/20210920/20140187dZkrY8BS3H.png

  1. 第一個節點又被稱作頭節點
  2. 每個節點都有資料和指標
  3. 只能透過指標尋訪下一筆節點的資料(只能同一方向)
  4. 最後一個節點的指標不指向任何地方(標示為Null),表示串列的盡頭。

刪除節點:只要把A原本指向B的指標改為C,再把B節點刪除就完成了。
https://ithelp.ithome.com.tw/upload/images/20210920/20140187nbVDhuBFgl.png

新增節點:假設新增一E節點再AB之間,把A的指標指向E,再把E的指標指向B就可以囉,是不是比陣列簡單很多!
https://ithelp.ithome.com.tw/upload/images/20210920/20140187Cr8iDxnQqz.png

雙向鏈結串列:

進入到下一個雙向鏈結串列,不過其實只是依樣畫葫蘆,只要多增加向前一個節點的指標就可以了喔!
https://ithelp.ithome.com.tw/upload/images/20210920/20140187MZTWGSarAN.png
一個節點就包含兩個指標(前後)和資料,雙向鏈結串列也有能快速修補脫落節點的妙用!

環狀鏈結串列:

終於到了最後的環狀鏈結串列,只要把最後一個節點指向第一個節點就可以了。
https://ithelp.ithome.com.tw/upload/images/20210920/20140187FCjjFa0wRg.png

今日小結:今天介紹完了鏈結串列,明天就要來實作練習了,雙向和環狀鏈結串列的新增和刪除跟單向鏈結串列都大同小異,只要更動指標的指向的節點,有興趣的人可以練習看看(≧▽≦)


上一篇
[Day05]程式菜鳥自學C++資料結構演算法 – 陣列Array List實作之二
下一篇
[Day07]程式菜鳥自學C++資料結構演算法 – 鏈結串列實作應用
系列文
程式菜鳥自學C++資料結構演算法30

尚未有邦友留言

立即登入留言