[ CS 筆記 ] Data Structure|Linked List

Linked List Intro

  1. a list of an element called nodes that are connected together or linked together in a single file line 一個清單把 nodes 連結起來
  2. a linear collection:把資料用線性方式串在一起,這些 nodes 的順序不是按照在記憶體中物理的位置排序(在記憶體中物理性位置是四散的)(array 就是按照在記憶體中物理位置排序),instead, each element points to the next
  3. a data structure that contains only head and length property
  4. link list 裡面有 nodes, and each node has a value, and a pointer(next property) 指向另一個 node 或 null
  5. there are two types of linked lists

a single linked list: each node only has reference to the node after it or next node 每個 node 只跟下一個 node 有關聯

a double linked list: each node has reference to the node after it and the one before or previous it 每個 node 和之前 / 之後的一個 node 都有關

6. the linked list itself as a whole only needs to know about two nodes in the whole list for it to function correctly. it needs to know about the head node and the tail node, and it keeps reference to these nodes by two pointers aka head pointer and tail pointer

Advantage of Linked List

  1. nodes can be inserted into linked list indefinitely 可以無限增加,array will eventually fill up or need to be resized. (在其他語言例如 Java 會需要在定義時就決定陣列長度,JavaScript 會自動增加)
  2. very fast insertion and deletion compared to Array

Disadvantage of Linked List

  1. use more memory than arrays because of the sotrage used by the next property. 記憶體多存了一個 next property,array 只需要存值
  2. Nodes in a linked list must be read in order from the beginning because linked list is inherently sequential access. 像 array 可以直接透過 arr[6] 取得第 7 項,但 linked list 一定要從頭走才能走到想要的地方
  3. Nodes are stored noncontiguous (非連續性), so greatly increasing the time required to access individual elements within the list, especially with a CPU cache. array 在記憶體中的物理性位置,儲存是連續性的,但 linked list 不是,所以大大增加要找每一個 node 的時間
  4. 很難 reverse traversing,因為 linked list 是從頭讀取,要從最後讀到前面很難

Difference Between Array and Linked List

- Linked List

  1. do not have indices (index 複數)
  2. connection between nodes are a “next” pointer (property) 透過 next 連接
  3. randomly access is not allowed(must go through each item before the one you want to access)

- Array

  1. items are indexed in order
  2. insertion and deletion are time consuming 需要重新整理 index
  3. can quickly access with a specific index

Big O

Difference Between Single Linked List and Double Linked List

- single linked list

  1. simple implementation
  2. require less memory
  3. faster insertion and deletion
  4. can’t be iterated in reverse or traverse from back to front

- double linked list

  1. can be iterated in reverse or traverse from back to front
  2. more complex
  3. require more memory

Implementing Linked List

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store