Day 5 - 讀書筆記

今天是讀書筆記。

資料結構

當數據存在記憶體中，決定這些數據的順序和位置的，就是資料結構。

以電話簿為例，若是完全不做分類，僅是簡單的將人名和電話為一組記在紙上，就會像這樣。

這些資料的排列並沒有特別的意義，只是按照先後順序一一加上而已。若是之後要新增，就直接加在下面。
這種方法雖然新增很簡單，但是當要查詢特定資料時就很困難了。若是電話簿中有一千筆資料，某一天突然想要找到特定某人的電話時，就要由上往下找，或是由下往上、或是隨機地靠運氣找，不管哪種方法，都很費時費力。

或是我們改變資料排列的方式，改成以姓為分類來編排

這樣一來，某天我們若想在一千筆資料中，找到特定的人的電話號碼，只要根據他的姓氏來尋找，就能省下很多時間。

將原始的資料按照特定的規則排列出先後順序，就是資料結構。

單向串列 (Linked list)

串列(link)指的是一串由節點(node)和指標(pointer)組成的資訊串鏈，節點就是一個一個單位數據，指標是一個具有指向性的標的，指向下一個節點。藉由節點和指標，將一筆一筆資料串接成一個單向的資料鏈，串鏈末尾的指標會指向null。

單向的串列中，若是要取用其中一筆資料，就必須從這一串資料鏈的起點開始，沿著指標一路尋找，直到找到為止，不能跳過。
在這種結構中，要新增或刪除資料的話，只要改變指標指向的對象就好，但是若要尋找特定資料卻很費時。

另外，這只是最簡單的單向串列，其實還有雙向串列（節點有首尾兩個指標）、以及環狀串列（末尾的指標指向首位）等其他模式。

陣列 (Array)

陣列的形式類似列表，也是將資料排成一列，但是與列表的指標不同，陣列會運用索引值來提取資料，索引，即為該筆資料在陣列中的位置。

由於電腦編號會從0開始，因此第一位索引值為0。要提取資料時，我們會用這樣的表示法：array[0]，就能提出第一位的A。
陣列與列表方便的地方在於，我們要提取特定資料時，不用再從頭開始一個一個找，只要知道該資料在陣列中的位置，就能一步就提出來。
但是陣列也有缺點，當我們想要安插一筆資料在中間時，舉例來說，我想要在B和C中間增加一個「小王」，會需要經歷以下步驟

1. 先在陣列的末尾開闢新的位置

2. 先把C和C以後的資料都往後移一位

3. 然後把小王給放進去

如果是串列的話，只要修改第一位和第二位節點的指標就好，但是使用陣列的話，就無法那麼簡單。

小結

串列與陣列雖然很像，但是優缺點卻相反，在選擇採用哪種方式之前，要先根據狀況來評估。

參考

演算法圖鑑
Linked List