#3 我需要懂資料結構嗎 ?

如果你的工作是系統管理或是網路工程領域,那麼資料結構可能對你不會有太大的影響,如果你的工作是程式設計或資料庫方面的領域,那麼資料結構對你將會是很重要的主題.若你的工作是程式設計類或資料庫類,即便你沒念過書本上的內容,我相信你對資料結構也有基本的認識.資料結構可以說是整個電腦科學裡相當基礎的知識,如果你把電腦科學用國中國小數學來比喻的話,則資料結構就像小學的四則運算一樣的基礎,必須要了解它才能通往更高級的方程式.

以目前的電腦架構來看,你可以把CPU視為一個做運算的單位,比如做加法運算或除法運算等等,而記憶體和硬碟的空間就像是一條有限長度的磁帶,你可以將資料寫在這條磁帶上,而記憶體這條磁帶比較短,但它讀取寫入速度較快,硬碟這條磁帶比較長,它讀取寫入速度較慢,所以當 CPU 運算時所需要的資料都是在記憶體和硬碟這兩條磁碟裡.接下來,當 CPU在運行時,要透過什麼規則來讀取寫入以及運算資料,那就會因為不同的程式應用而不同,所以在電腦科學裡就會因為不同的應用而定義出適合的資料結構.因此,簡單的來說,資料結構就是定義資料該如何儲存,該如何讀取,以及如何運算.

不論是那一種電腦系統,運行在該電腦上的作業系統一定都會提供一些基本的資料結構,例如 Array, Stack, Queue, List等等,而每個資料結構都有個自的特色以及運用的時機和技巧.比如,Array 的特色就是它的元素在記憶體空間中需要連在一起,也就是只要找到了 Array 的開始位置後,找第一個元素和找最後一個元素所需的時間都是一樣的,因為 Array 裡面的元素都是同一種 data type,所以每個元素在記憶體所佔的大小也都相同,因此很簡單就可以算的出來.List 跟 Array 在這方面剛好就有點不同,List 裡面的每個元素也都是一樣,但它並不需要把每個元素把放在記憶體中連續的空間,List 的元素可以東放一個,西放一個,在儲存位置的選擇上比較有彈性空間,也正是因為這樣的彈性空間,所以每個元素裡面需要有一個特別的位置 (我們稱它為pointer),用來記錄下一個元素的位置在那裡,透過 pointer,我們才能從第一個元素一直走到最後一個元素,所以當你要存取 List 裡面某一個元素時,它的位置就不能像 Array 是用算出來,而必須從第一個元素開始走,一直走到你要的元素為止,所以每個元素的尋找時間是不一樣的.

接下來你可能會問,Array 和 List 看起來有點像,其實又不太一樣,我們該怎麼知道什麼情況下要用那一種呢? 這是一個很好的問題,有時很難給出很好的答案,但基本上我能給的答案是,如果你知道你所需要的元素個數,那麼你就用 Array,因為 Array 一開始必須要宣告它裡面能裝幾個元素,若情況剛好相反,你不確定你要裝多少個元素,而且存取元素的時間也不是你所在意的,那麼用 List 就提供了一些彈性.

如果你曾用過 java 或 .net 平台提供的 ArrayList,你可能曾想過這到底是 Array 還是 List 呢? 簡單地說,它是長的像 List 的 Array,本質上它還是 Array,但也提供了一些 List 的存取方式讓你來寫入或讀取裡面的元素.同時,它加上了改變 Array 長度的功能,也就是說你一直新增元素進去的話,那勢必會塞滿原有的 Array,所以若要再裝進更多的元素,則需要改變 Array 的長度.但是 Array 一旦宣告了之後就不能改變長度,所以有兩個可能的解決方法.
第一,宣告一個更長 Array,然後把原有 Array 的元素放到新的 Array 上,此時新的 Array 就有更多空間可以裝新的元素,然後把原有的 Array 從記憶體中釋放.
第二,宣告另一個一樣長度的 Array 來裝新的元素.此時就要做一些管理的動作,這樣 ArrayList 來讀取寫入資料時,才知道那一個 Array 是第一個,那一個 Array 是第二個.
可能還會有其他的方法,總之都是在做類似 Array 管理的動作,主要就是解決 Array 長度的問題.

未來文章再機會來談談這些基本的資料結構.

Share: