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

第一章、陣列的基本介紹

1-1、透過靜態串列(List)方式實踐陣列

串列是一種緊密相連，且「連續性」儲存於記憶體位置的一種資料結構，好比一條街道的地址，通常是以連續的方式儲存。在Python中，List常用的屬性有四種，分別是串列名稱、維度、元素個數和索引值。

串列名稱顧名思義就是該串列的名稱，同時也會指向此陣列在記憶體中被儲存的位置；維度則代表此串列中的資料維度，如一維串列、二維串列等等；元素個數則是指串列中總元素個數有幾項；索引(index)是串列中用來指定元素位置的一種方式，在Python中，第一個元素的索引值是0，第二個是1，以此類推，也可以說第一個元素的索引值是0。

串列中每一個元素可以為任一資料型態，無需事先宣告，透過中括弧[ ]將資料包含在內，即可完成串列的宣告。以下方程式碼為例，list_demo中包含了數字與文字兩種資料型態，索引值為0的元素為1，索引值為1的元素為Apple，一共有三個元素。此外，若我們事先不曉得元素的內容，則可透過[None]這種方式先行佔據記憶體位置，提供後續資料儲存。

---

1-2、透過鏈結串列(Linked-List)實踐陣列

在Python上透過靜態結構來建立陣列的方式有一項明顯的缺點，那就是我們必須先宣告陣列中的元素個數。若我們事先不知道可能會用到的元素個數，我們必須先假定一個較大的元素個數供未來使用，這可能會導致部分記憶體空間沒有被使用到而浪費掉了，鏈結串列則可解決此浪費記憶體空間的問題。

鏈結串列如同火車車廂般，可以隨時依照使用者需求大小而動態改變鏈結的個數，並將元素儲存至各車廂中，隨時可進行動態增加或刪除，鏈結始終保持前後關係，將不連續的記憶體透過鍊結的方式維繫關係，為了能成功走訪所有鏈結，我們須確保每一個車廂都有被連接到，最後要走訪時在以首節點為起點，循序走訪所有資料，底下程式碼透過以員工資料做為範例，每個節點儲存三筆資料，分別為name、salary與下個節點位置，請看範例。

---

1-3、陣列的走訪

走訪陣列的方式十分簡單，若是靜態結構，我們僅須透過for迴圈即可尋訪所有元素；若是採用動態的鏈結串列，首先我們必須先將當下的位置指向首節點後的節點位置，開始判斷當下的節點位置是否為空值，若否，則依序走訪，並印出相關資訊，當我們走到最後一個位置時，該指標應為None，便不會進入迴圈中，我們可以試著將走訪單向串列寫成一個函式show，方便後續呼叫使用。

下一節我們會繼續討論陣列中靜態結構與動態結構新增、修改元素的方式，有任何問題歡迎寄信至我的信箱或於底下留言和我討論。

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

---

參考書目

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