Data Structure 資料結構 - Linked List 鏈結串列

根據 Wiki 的定義，Linked List 為

A linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence.

Linked List 是一個線性資料元素集合，卻沒有順序性。它並沒有提供實體記憶體位置，相反的，它每個元素的節點 (node) 都會指向下一個元素為何。

示意圖

Different Structures 結構

以下根據 Wiki 做節錄

Singly Linked List 單向鏈結串列

A singly linked list whose nodes contain two fields: an integer value and a link to the next node

Linked List 中最簡單的一種是 Singly Linked List，它包含兩個域，一個資訊域和一個指標域。這個 List 指向列表中的下一個 node，而最後一個 node則指向一個空值。

Doubly Linked List 雙向鏈結串列

A doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node

一種更複雜的 Linked List 是 Doubly Linked List。每個 node有兩個連接：一個指向前一個 node，當此為第一個 node，前一個則指向 null；而另一個指向下一個 node ，當此為最後一個 node 時，後一個則指向 null。

Circular Linked List 迴圈鏈結串列

A circular linked list

Circular Linked List 中第一個 node 之前就是最後一個 node，反之亦然。Circular Linked List 的無邊界使得在這樣的連結串列上設計演算法會比普通 Linked List 更加容易。對於新加入的 node 應該是在第一個 node 之前還是最後一個 node 之後可以根據實際要求靈活處理。

特性

優點

1. 可以克服 Array 陣列需要預先知道資料大小的缺點。
2. 可以充分利用記憶體空間，實現靈活的記憶體動態管理。

缺點

1. 因為增加了 node 的儲存空間，需要額外的記憶體空間。
2. 無法 random access 隨機訪問，因此存取特定位置的 item 速度特別慢。

Ex. 取出第 21 個 item，ArrayList 只要指定 index 就可以取出，但 Linked List 需要從第一個開始找起