你有沒有想過當你刪掉列表第一個的元素，程式背後會怎麼運作？

mylist = [1,2,3,4]
mylist.remove(1)

電腦會將剩餘的元素向前移動一格：
mylist[0] = mylist[1], mylist[1] = mylist[2], mylist[2] = mylist[3]...

如果列表包含1000個元素或更多，那麼電腦會花費很多時間在處理這件事情上。

今天要介紹的這個資料結構叫做「鏈結串列」，他可以解決這個問題喔！

鏈結串列

鏈結串列又可以簡單分成「單向鏈結串列」與「雙向鏈結串列」。

原理概述

鏈結串列是由許多節點構成的一種資料結構，節點中紀錄資料內容之外，也記錄其鄰居節點。
紀錄鄰居節點的變數我們稱為鏈結，因此我們稱「節點」為「資料」+「鏈結」，而這些節點相連成「鏈結串列」。

鏈結串列最重要的部分是紀錄「頭部節點 head」的變數，因為每一個節點都包含著至少一個鏈結，我們可以從「鏈結」知道下一個節點。如果指向的節點，其鏈結指向 None，代表這個節點是鏈結串列的最後一個。

從外型來看

• 單向鏈結串列
  

• 雙向鏈結串列
  

鏈結串列的缺點（無法隨機存取）

列表具有隨機存取的功能，即 list[idx] 來取得某一個列表元素，且所費時間僅 O(1)。

鏈結串列則沒有隨機存取的功能，當我們要取得第 idx 個元素時，我們需要從頭開始搜尋，直到找到該元素。

鏈結串列的優點（插入、刪除）

當我們使用列表時，我們要實行插入與刪除，我們需要搬動大量的元素（取決於列表大小）。

如果我們使用鏈結串列，我們可以用 O(1)的時間完成插入與刪除，我們只需要把該節點的前一項的鄰居設為該節點的下一項。

如上圖：
假設我們要刪除資料內容為 5 的節點
綠色箭頭代表改變的鏈結

如上圖：
假設我們要新增資料內容為 5 的節點
綠色箭頭代表改變的鏈結

也許聽完上述的說明，仍不清楚鏈結串列！沒關係，接下來我們會更清楚的介紹鏈結串列。

下一篇開始，我們會開始實作鏈結串列！