鏈結串列(linked list)是一種將資料串連起來的結構。這個結構可以比喻成一列火車，而我們可以從火車頭開始，依次的到每節車廂存取資料，如下：

圖源：維基百科

當然，如果你熟悉在熟悉了記憶體的底層配置方式以後，再回來看這個比喻的話，應該比較像是把散落在各處的車廂，用傳送門依次的連接起來，而不是在同一軌道上把一批車廂連成一串。

Linked list 的基本操作，有取得某個位置的值、搜尋某個值是否存在、插入一個值、刪除某個位置的值、取得長度、取得是否為空、...等等。你可能知道，這些操作也可以用一般的陣列來達成；因此，「linked list」這個名稱，其實不是指一種 ADT，而是相對於一般陣列的另一種實作手段。以下會先介紹這種手段的各個基本細節，最後再跟陣列做比較。

而就像火車的每節車廂，可能搭載一些乘客或存放貨物，以及有連結器（或傳送門）讓你前往下一個車廂一樣；linked list 的具體結構，也是有許多節點，每個節點有它本身的資料，以及前往下個節點的傳送門，如下：

用程式建構出上圖的 linked list，以及走訪它的方法則如下：

class ListNode(object):
    def __init__(self, val=0, next_node=None):
        self.val = val
        self.next = next_node


# Construct
head = ListNode(10, None)
ptr = head
for v in (20, 30, 40, 50):
    ptr.next = ListNode(v, None)
    ptr = ptr.next

# Traverse
ptr = head
while ptr:
    print(ptr.val)
    ptr = ptr.next

上述的建構部分，其分解動作演示如下：

⟲

← 上一步   下一步 →

而若要取得特定位置的值，或者搜尋某個值是否存在，則可以很簡單的從走訪的部分修改；而取得長度的操作，則可以藉由多維護一個變數來進行。因此，以下只對比較複雜的插入和刪除來做說明。

插入一個元素：

刪除一個元素：

複雜度：

操作	Linked list	Array
取得 index k 的值
搜尋某個值是否存在
在 index k 的位置插入一個值
在 index k 的位置刪除一個值