從Python認識資料結構(三)．陣列

3-1、刪除元素

我們如果運用靜態結構-串列(List)方式來建立陣列的話，那麼刪除元素主要有三種方式，根據不同需求採用不同函式，第一種是remove，語法是list.remove(元素)，這種方法用於我們不用知道指定元素的索引值，可以直接從串列中將指定元素移除，但若指定元素沒有出現在串列中，則會回傳錯誤訊息。

第二種移除元素的方法是pop，語法是list.pop(元素的索引值)，與remove不同的是，pop需要知道該元素確切的索引值才可進行移除，且pop後會回傳該索引值的元素，並將其移除串列中，若使用pop卻不給定元素的索引值，則會移除串列最後一個元素並回傳。最後一種方法是del，語法是del list[索引值]，與上述pop方法不同的是，del函式並不會回傳該元素，而是直接將其刪除。

若採用鏈結串列(Linked List)的方式建立陣列，刪除的要求可分為刪除最前面的元素、最後的元素及指定元素。若要刪除最前面的元素，我們可以將head的next屬性改為第一個元素的next屬性，如此一來，原先第二個元素就會被接在head後方，完成第一個元素的刪除，此時的刪除並非將其移除記憶體空間，而是改變鏈結的順序，刻意丟失該元素的資訊而已。

在鏈結串列要刪除最後一個元素，我們先找到倒數第二個節點位置，並將此節點的next屬性改為None，此時倒數第二個節點後就沒有資料點，其成為倒數最後一個節點，也就完成上述功能。最後一種刪除指定的元素的作法，我們同樣先找到指定元素的前一個節點位置，並將指定元素前個節點的next屬性改為指定元素的next屬性，這個部分可以會比較難以理解，提供一張鏈結的圖來想像一下過程。

從上述三種鏈結串列刪除方法可以發現，透過鏈結串列來實作刪除功能時，我們並非真的去刪除節點，而是透過更改next屬性來刻意的丟失該節點資料，使鏈結串列在尋訪過程中不被走訪。

---

3-2、計算元素數量

大概介紹完陣列的主要功能，接下來就介紹一些實用的語法，並嘗試在鏈結串列中進行實作，第一個是count，這個函數可以統計指定元素在串列中出現的個數，語法為list.count(指定元素)。若要在鏈結串列中實作，我們可以初始化一個計數器，並走訪所有節點，將鏈結串列中所有等於指定元素的節點個數計算出來。

---

3-3、 反轉功能

在靜態串列中要進行反轉相當容易，方法為list.reverse()，此函數會直接更改list內容。但在鏈結串列中，順序的反轉就需要經過特別設計，我們首先宣告兩個變數temp與prev來儲存節點資訊，從第一個資料點開始進行迴圈。

將第一個資料節點的next屬性存進temp，並將next改為前位節點(第一次是預設的None)，接著將自己存為prev，當作下個迴圈的前位節點，接著移動到下一個節點位置繼續此四步驟。當更改完最後一個迴圈時，我們還要將head的next屬性改到最後一個節點位置，於是將head.next設為prev所儲存的最後一個節點。

上圖是鏈結串列反轉的示意圖，後面迴圈的邏輯都一樣，紅框代表在一次迴圈中會被更動到的變數，這個部分比較困難，應該也還有更好的做法，都歡迎討論看看XD。以上部分就是Python陣列的主要介紹，下一節我們會繼續介紹鏈結串列的延伸與實作，有任何問題歡迎寄信至我的信箱或於底下留言和我討論。

• Institute of Education, NYCU
• clay.jz.huang@gmail.com

---

參考書目

1. 圖解資料結構 - 使用Python(第二版)
2. 圖書演算法 - 使用Python
3. Python3 物件導向程式設計 第二版
4. 精通Python (第二版)