被偷走的 Data Structure (I) — Array, Linked List

前言

接下來一系列的文章,我會透過 GeeksforGeeks 來介紹 Data Structure,而今天要講到的主題是

  • array
  • Linked List

正文

Array 特質

  • index(key) — value
  • value 相同型態
  • 由 一串連續記憶體位址 組成

優點

  • 適合 搜尋隨機存取 (random access) 需要 O(1)
  • 較好的 快取區域性 (Cache Locality)

缺點

  • 不適合 新增刪除 (可能需要移動其他陣列的值
The picture is from GeeksFromGeeks

相較於以往 C or Java 的靜態 array ,在 Python中,array是動態的,但比起array,Python中的 list 更是具備了額外的彈性 - value不需要具備相同型態,不過額外付出的代價則是,動態陣列所使用的空間比靜態陣列來得多。

Python List vs. Array — when to use?

更具體一點來說,在Python,絕大多數的時間都使用到 list,不過這還是取決於需求而定。

面試的時候,公司常常問到不透過函式,如何寫出reverse的方法,當下還有點卡,因為 Python 的 [::-1] 已經用習慣了,此外還不用考量到變數型態是 string or list 的情況,真的要重造輪子,就來造一個吧。

List reverse

String Reverse

  1. trivial for-loop

2. 尾遞迴


(Singly) Linked List 特質

  • 動態 長度

優點

  • 適合 新增(在 Head)、刪除

缺點

  • 不適合 搜尋
  • 不允許 隨機存取 (random access)
  • 額外花費 pointer 的記憶體空間
The picture is from GeeksFromGeeks

By the way, Linked List 其實也能實作出 Binary Search。

Binary Search on Singly Linked List
Find the middle of a given linked list