iT邦幫忙

2023 iThome 鐵人賽

DAY 7
0

概念

Linked List 是一種線性資料結構,可以從中間直接插入元素,相對陣列來說會比較省時,不過在競賽程式其實我其實一次也沒有用過,原因我會在底下做說明。

缺點

一般 Linked List 會包含以下操作

  • 插入元素
  • 遍歷元素
  • 刪除元素

特殊的是插入、刪除元素(不管是從中間或是前後)的時間複雜度都是 https://chart.googleapis.com/chart?cht=tx&chl=O(1),不過有趣的點是要找到插入的位置也要先遍歷元素,而遍歷元素是 https://chart.googleapis.com/chart?cht=tx&chl=O(n)

因此,其實 Linked List 在競賽程式中沒有太多人做使用,不過還是需要瞭解一下,因為在大學資料結構課程中好像是蠻重要的一個部分,且通常會使用指標實作,但因為競賽程式中會很追求程式執行效率,所以就不太會使用到。

實作

因為競賽程式中不太常使用到,因此我這邊就不進行實作,需要看看實作的部分可以自行到網路上查找教學。

總結 & 預告

這邊是基礎資料結構的最後一篇,後面的東西會以演算法為主,並時不時穿插一些題目或是資料結構,大家可以跟著解題目,或是有哪些部分不清楚又或是有哪些主題想要瞭解的都可以在留言區留言敲碗,我有可能會以此為主題撰寫文章。


上一篇
Day-6 堆疊 & 佇列例題講解
下一篇
Day-8 演算法概念
系列文
從競賽程式學習資料結構與演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言