我的DSA 日記— 2

陣列(array) vs 連結串列(linked list)

記憶體就像鞋櫃,一格格整齊排列,且一個格子只能放一雙鞋子(一筆資料);若是有兩雙鞋,就必須用到兩格鞋櫃;若是有一台遊覽車,上面載著來戶外教學的小學生,那麼我若要儲存這筆資料,就得空出等同於小學生數量的空鞋櫃給他們。這時就有兩個選擇:
1. 讓每個小學生自行挑選喜歡的位置放置
2. 依照座號,依序整齊放入鞋櫃
而這裡的1就是連結串列,2就是陣列。

陣列

總記憶體有許多空間,但當我預計要用陣列存入一堆資料時,由於陣列需要按照順序擺放,所以不容許擺放到一半有已經被佔用的空間,因此需要獨立規劃出一個確定能容納此陣列的空間來擺放。

插入或刪除為O(n)
因為是按照順序擺放的,所以當我需要插入一個新的資料項目,就得把插入點後的資料全往後挪動,然後再放入新資料;刪除資料也是一樣,當我把某項資料刪除後,這項資料後的資料全部要往前挪動。如此一來才能保持陣列的連續性。

讀取為O(1)
雖然說增減資料看似很麻煩,但陣列的優點就在於讀取資料。由於資料都是按照順序擺放,所以可以直接拿對應的索引值去找我要的資料。

連結串列

為了克服陣列的連續性所造成的麻煩,多了另一種方式稱做連結串列。連結串列允許資料項目散落在各個空的記憶體內,但這樣又要怎麼去知道哪些資料項是來自這一個連結串列?實行方式是,連結串列的第一項資料會存入下一項資料的位址,因此只要知道第一個,就能知道第二個;知道第二個,就能知道第三個,以此類推,就能知道整個連結串列的各個資料項了,即使他們都散落在各處。

插入或刪除為O(1)
如果要插入一個資料項,直接隨便找個空的位址放入,然後再前後互相存取位址即可;刪除也是同樣的道理。就不用像陣列還要整個大搬家。

讀取為O(n)
由於資料不是連續排列,因此當我想知道第五項資料項是什麼的時候,就得先從第一個開始找起,然後才能依序找到第五個。

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.