【舌尖上的演算法】Day5 -- 線性資料結構(Linear Data Structures)

2020 IT邦鐵人賽

Posted by Hank Lee on Saturday, September 12, 2020

4 Minutes Read

Table of Contents

本系列文章同步分享於IT邦幫忙第12屆鐵人賽

前言

第三天我們說明了什麼是抽象資料型別(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)

線性資料結構,顧名思義,是直線性的資料結構,而這種資料結構最常被使用且最重要的就是ArrayLinked List

1. Array

Array

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

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

    (2) Insertion:

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

    (3) Deletion:

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

2. Linked List

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(如下圖)。 LinkedList-Insertion

    (2) Deletion:

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

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


小結

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

預告

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


References

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