本系列文章同步分享於個人Blog → Informistry-HankLee
第四天我們說明了什麼是抽象資料型別(Abstract Data Type, ADT),同時也介紹了8種相對常被使用的ADT,還沒有看過的朋友或是想要複習的朋友可以點擊【舌尖上的演算法】Day4 -- 抽象資料型別及特性;但這些ADT畢竟只是概念,真正將ADT實作出來的物件就是所謂的資料結構(Data Structure)。
在接下來的20多天裡,我們將會針對一些比較淺顯易懂的演算法一一介紹,但是在正式開始品味這些演算法之前,我會先介紹資料結構本身,才會開始說明利用這種資料結構的演算法。今天,我會先提出兩種線性資料結構(Linear Data Structure)
的範例。
日後會再針對Binary Search Tree及HashTable做說明。
線性資料結構,顧名思義,是直線性的資料結構,而這種資料結構最常被使用且最重要的就是Array
及Linked List
。
Array
是一個1-D(one dimensional)的結構,每個Elements會有自己的index
Array
也是一個集合物件(Collection)Array
的三個操作模式:
Linked List
的特性是每一個Node除了儲存Element之外,還包含了一個『指標』,這個指標代表的是下一個Node,也就是說,透過這個指標可以將每一個Node都串起來,形成一個List的結構。(Node = Element + Pointer)
head pointer
用來記錄第一個Node;有時候會另外有一個tail pointer
紀錄最後一個Node。Singly Linked List
外,Linked List
還有其他種類的實作方式,其中一種是Doubly Linked List
,Double代表的是每一個Node都會記錄『前一個』和『後一個』的Node,在這邊我們不多做說明,因為在第25天的時候,我們會花比較多篇幅來介紹Doubly Linked List
,也會在第30天的時候介紹Cyclic Doubly Linked List
。Linked List
的兩個操作模式:
Linked List
是透過pointer將Node關聯起來,因此其實在改變『結構』的時候,只要做一件事:調整pointer連線的對象
。在做Insertion的時候,是將插入位置前一個Node的pointer指到New Node,再將New Node的pointer指到插入位置後一個的Node(如下圖)。Array
和Linked List
在程式實作中都很常被使用,很多簡單的演算法也都是透過這兩種資料結構來進行運用。
Array
及Linked List
接下來的數天,我們會將一些比較容易理解的演算法分類,然後再一一跟大家介紹,準備上主菜囉~