資料結構-鏈結串列(List)

資料結構

資料結構(Data Structure, DS)，代表將資料有組織的存放在記憶體中，以提升程式的執行效率

鏈結串列(List)

• 每一個元素可以當作是一個Node(節點)，例如下圖的12，就可以當作一個Node

• 一個Node會儲存兩份資訊，本身的值及指向下一筆資料在記憶體的位址，藉此將多個Node鏈結成串列(Linked List)

鏈結串列的種類

1. 單向鏈結串列：包含兩個值目前節點的值和一個指向下一個節點的連結，最後一個Node指標會指向Null

2. 雙向鏈結串列：每個Node有兩個指標，一個指向上一個節點的連結，一個指向下一個節點的連結以及目前節點的值，第一個節點之前儲存一個永遠不會被刪除或者移動的虛擬節點

特性

• 不像Array有Index，找到特定資料(Node)，需從頭(HEAD)開始找起，搜尋複雜度為O(n)

• 新增/刪除元素，只要Node調整pointer即可，新增/刪除複雜度為O(1)，但是尋找特定Node執行新增刪除，可能會需要O(n)的時間

• 需要額外記憶體儲存指標(pointer)

• 非連續的方式儲存在記憶體

參考資料：

• Linked List: Intro(簡介)

• 《演算法圖鑑》第一章：資料結構

• 鏈結串列 Linked List

• 連結串列