DAY 03 : 線性串列

3.1什麼是線性串列(Linear List)?

線性串列有以下幾個特色:

它是一個序列(元素之間是有順序)

第一個元素沒有前驅者(前面的元素)，最後一個元素沒有後繼者(後面的元素)，其餘的元素都只有一個前驅者(predecessor)和一個後繼者(successor)。

它是有限的(在電腦中處理的物件都是有限的)

它必須都是相同型別的資料

當n = 0時，我們稱為空串列。

線性串列有分為兩種物理結構:順序儲存結構和鏈結儲存結構

3.2順序(Sequential)儲存結構

順序儲存結構是只用一段位置連續的儲存單元(陣列)，依次儲存線性串列的資料元素。

要建立順序儲存結構，必須要在記憶體佔著一定的空間，並且找到起始的位置，之後再插入資料，很重要的一點是: 線性串列的目前長度不可以超過陣列長度。

陣列長度是什麼?
陣列長度是存放線性串列的儲存空間的長度，通常是不變的(在一般高階語言中可透過程式設計的方式做到動態分配陣列來改變陣列的長度)。
線性串列長度是什麼?
線性串列長度是資料元素的個數，因此是會變動的。

儲存或讀取資料時，會需要知道該元素的位址。

3.2.1位址的計算方式

記憶體中的每個儲存單元都有自己的編號:位址
可以透過以下的公式計算出任意位置的位址的儲存結構我們稱為｢隨機存取結構」:
LOC(ai) = LOC(a1) + (I-1)*c
(c:佔用的儲存單元
LOC(ai):第i個資料元素的位置
LOC(a1):第一個資料元素的位置)
時間複雜度為O(1)。

3.2.2順序儲存結構的插入與刪除

1.取得元素:如果想要i的數值，就把陣列第i-1編號的值傳回。
2.插入元素:

1.如果插入位置不合理則跳出異常。
2.如果插入元素後線性串列長度大於或等於陣列長度則跳出異常或動態增加容量。
3.如果要將最後一個元素往前移到第i個位置，則在第i個位置(包含i)的元素都需往後移一位。
4.插入一個新元素則陣列長度+1
最好情況時間複雜度:O(1) (插入最後一個位置)
最壞情況時間複雜度:O(n) (插入第一個位置)
平均情況:O(n)(插入的位置較前面，移動的元素越多，插入的位置較後面移動的元素越少，平均後為(n-1)/2，因此時間複雜度依然為O(n)

3.刪除元素

1.如果刪除位置不合理則跳出異常。
2.取出刪除元素
3.刪除元素位置開始到最後一個元素位置，向前移一個位置。
4.刪除一個新元素則陣列長度-1
最好情況時間複雜度:O(1)(刪除最後一個位置)
最壞情況時間複雜度:O(n)(刪除第一個位置)
平均情況:O(n) (刪除的位置較前面，移動的元素越多，刪除的位置較後面移動的元素越少，平均後為(n-1)/2，因此時間複雜度依然為O(n)

3.2.3優缺點

優點:
1.不用為了表示線性串列中各元素之間的邏輯關係去增加額外的儲存空間。
2.可以較方便快速的去存取線性串列中的元素。
缺點:
1.插入和刪除需要移動大量的元素。
2.當線性串列的長度變化較大時，難以確定儲存空間的容量。
3.容易造成儲存空間的｢碎片」。

3.3鏈結(Linked)儲存結構

鏈結儲存結構使用一組任意的儲存單元來儲存資料元素，可以是連續也可以是不連續並儲存於記憶體的資料元素，具有單線索且無分支的特性，鏈結儲存結構也可以解決順序儲存結構插入和刪除時需要大量移動元素的缺點。

由於鏈結儲存結構的資料元素有可能是不連續的，因此還需另外儲存其後繼者的儲存位址，也就是所謂的｢指標」。

我們將儲存資料元素資訊的欄位稱為｢資料欄位」，然後將儲存｢指標(Pointer)」或叫｢鏈結(Linked)」的資訊存放於｢鏈結欄位」，而這兩個欄位合併我們稱為｢節點」。
當有n個節點連結成一個鏈結串列(Linked List)，我們就稱它為｢鏈結儲存結構」，又或是稱為｢單向鏈結串列(Single Linked List)」(此鏈結每個節點都只包含一個鏈結位)。

接下來用圖片來說明: