本系列文章同步分享於個人Blog → Informistry-HankLee

前言

第四天我們說明了什麼是抽象資料型別(Abstract Data Type, ADT)，同時也介紹了8種相對常被使用的ADT，還沒有看過的朋友或是想要複習的朋友可以點擊【舌尖上的演算法】Day4 -- 抽象資料型別及特性；但這些ADT畢竟只是概念，真正將ADT實作出來的物件就是所謂的資料結構(Data Structure)。

在接下來的20多天裡，我們將會針對一些比較淺顯易懂的演算法一一介紹，但是在正式開始品味這些演算法之前，我會先介紹資料結構本身，才會開始說明利用這種資料結構的演算法。今天，我會先提出兩種線性資料結構(Linear Data Structure)的範例。

日後會再針對Binary Search Tree及HashTable做說明。

什麼是資料結構(Data Structure)？

• 上面提到ADT只是一個概念，並不是『真正』在演算法中使用的物件；既然ADT只是概念，勢必就會有將這些概念實作出來的物件，而這實作ADT的物件就是資料結構(Data Structures)。
• 資料結構用不同的方式來達到管理、儲存資料的目的。
• 一個好的資料結構可以大幅增加系統運行的效能。
• 不同類型的資料結構都有其適合的應用情境。
• 有些資料結構也可能是針對某單一應用情境下被設計實作出來的。

線性資料結構(Linear Data Structure)

線性資料結構，顧名思義，是直線性的資料結構，而這種資料結構最常被使用且最重要的就是Array及Linked List。

1. Array

• Array是一個1-D(one dimensional)的結構，每個Elements會有自己的index
• Array也是一個集合物件(Collection)
• 基本上用來儲存相同資料型態的物件
• 儲存物件的時候具有連續性，如上圖，儲存物件的時候會依據index檢查該Element是否為空，當找到空的位置的時候，才將物件儲存在那個位置。
• 具快速存取性
• Array的三個操作模式：

  (1) Search:

  
  從Array當中尋找指定的Element時，會從第0個index開始針對其Element做比較，一步一步往下查找，直到找到指定的Element才結束流程。

  (2) Insertion:

  當要把一個Element插入Array中指定的某一個位置時，對於這個指定位置後面的Elements來說，全部都要往後退一格。
  
  但假設在插入這個新Element之前，Array本身的空間已經是滿的了，那就是變成要新增一個原Array長度加1的Array，然後再將Elements一個一個放進這個新Array裡面。
  

  (3) Deletion:

  
  從Array當中刪除指定的Element時，原本位在此Element後方的其他Elements都會往前移動一格。

2. Linked List

• 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的兩個操作模式：

  (1) Insertion:

  因為Linked List是透過pointer將Node關聯起來，因此其實在改變『結構』的時候，只要做一件事：調整pointer連線的對象。在做Insertion的時候，是將插入位置前一個Node的pointer指到New Node，再將New Node的pointer指到插入位置後一個的Node（如下圖）。
  

  (2) Deletion:

  正如Insertion中提到的，我們針對要刪除的Node(B Node)的前一個Node(A Node)的Pointer做改變，只要將這個Pointer直接指定到『下一個Node(C Node)』，那這個要刪除的Node就斷開了連繫，進而被系統刪除(如下圖）。
  

Array和Linked List在程式實作中都很常被使用，很多簡單的演算法也都是透過這兩種資料結構來進行運用。

小結

• ADT畢竟只是概念，真正將ADT實作出來的物件就是所謂的資料結構(Data Structure)。
• 一個好的資料結構可以大幅增加系統運行的效能。
• 線性資料結構，顧名思義，是直線性的資料結構，而這種資料結構最常被使用且最重要的就是Array及Linked List

預告

接下來的數天，我們會將一些比較容易理解的演算法分類，然後再一一跟大家介紹，準備上主菜囉～

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin
2. Data Structure - Wikipedia