終於來到了 data structure 的部分，看來這系列一定會超過30天了XD

Linked List

A linked list is a linear data structure that consist with series of nodes connected by pointers(Array is another common linear data structure).

linked list 是線性資料結構的一種，由數個 node 構成，利用 node 中的 pointer 指標來指向下一個node
另外 array 是另種常見的線性資料結構

Difference between Linked List & Array

Linked List

• A collection of nodes where each node contains two parts:data and a reference(pointer) to the next node.
• Memory Allocation: Non-contiguous, elements are scattered across memory with each node pointing to the next node.
• Insertion/Deletion: Efficient; can add or remove elements without shifting other elements.
• Element Access: Dependent; to access an element, you must traverse through previous nodes.
• Memory Management: Allocated at runtime, allowing flexible use of memory.
• Memory Utilization: Efficient, as it only allocates memory as needed.

--

• Linked List 是多個節點(node)構成的集合體，每個 node 又由 data 跟指向下個 node 的 reference(pointer) 構成
• 非連續（不同 node 存取在不同位置的記憶體），每個 node 散落在不同記憶體中，節點與節點間由 pointer 指向
• 插入/移除元素： 高效率，插入或刪除 node 都不會搬移其他 node
• 獲取 Linked List 內的元素： 依賴，要存取某個 node 需要先遍歷之前的 node
• 記憶體分配：在運行時分配，對於記憶體分配上有更大彈性
• 記憶體使用率： 高效率，僅在必須情況下分配記憶體

Array

• Array is a collection of elements of the same data type storage at contiguous memory locations.
• Memory Allocation: Contiguous, meaning all elements are stored in sequence.
• Insertion/Deletion: Inefficient, because adding or removing elements may require shifting multiple elements.
• Element Access: Independent; any element can be accessed directly by its index.
• Memory Management: Allocated at compile time, with a fixed size determined beforehand.
• Memory Utilization: Inefficient, especially if the array is underutilized or resized frequently.

--

• Array 是儲存在連續記憶體中，由多個相同資料類別構成的集合
• 連續，於同個 array 內的元素會存在同一區塊的記憶體中
• 插入/移除元素： 低效率，插入或刪除 element 將會改變其他 element 的索引值(index value)
• 獲取 Array 內的元素： 獨立，可以直接由索引值獲取特定元素
• 記憶體分配：在編譯時分配，會先決定 array 的固定尺寸(length)
• 記憶體使用率： 低效率，特別是 array 頻繁變更大小與未充分利用的情況

Advantage of Linked List

Disadvantage of Linked List

• More space required
  Linked lists need more memory space than arrays because each nodes stores both the data and a pointer to the next node.
• Access time is slower
  To access a specific node by index, you must traverse the list starting from the head, unlike arrays, which can simply access by index.
• Non-contiguous memory
  Since linked lists use non-contiguous memory, accessing nodes is slower compared to arrays, as data may not be stored sequentially in the CPU cache.
• Difficult to traverse backward
  Traversing a linked list backward is more complex and requires additional work or a doubly linked list, making reverse traversal cumbersome.

Big O of Linked List & Array

其他資源

Linked List: Intro(簡介)
https://alrightchiu.github.io/SecondRound/linked-list-introjian-jie.html
Array vs Linked List
https://www.javatpoint.com/ds-array-vs-linked-list
How to Implement a Linked List in JavaScript
https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/
linked list intro
https://alrightchiu.github.io/SecondRound/linked-list-introjian-jie.html