LinkedList中文叫做鏈結串列，對於初學者來說會是一個相當不好學習的資料結構，想當初大學時為了用C語言來實作LinkedList在學習指標的過程真的是一波三折，好在之後用了Python來實作後發現相對簡單許多，這邊也建議新手可以先用Python來實作喔~

初探LinkedList

我們之前說到Array時有說，他是一塊連續的記憶體空間，那如果今天沒辦法有連續的記憶體空間呢 ? 那我們就可以用LinkedList來實作啦。

LinkedList裏頭我們會把存放資料的單位稱作「節點(Node)」，Node裡就包含兩個訊息，一個訊息是「LinkedList 要存放的資料」另一個訊息是「下一個LinkedList的位置」。

到這邊大家可能已經有點暈了，為什麼LinkedList要這樣設計？接下來我們用下面這一張圖來看看。

如果我要存放3個資料，我們在這種情況下很明顯是沒有辦法找到「連續的」3個格子。

但是大家可以看到如果不連續的話，我是有位置可以存放的。

那我們就放在不連續的位子然後每兩個節點用繩子連在一起，然後決定頭跟串接的順序性，這樣我們就能串起所有的資料了。

上面我所說串接也就是Node需要知道下個Node的位置，這樣是不是更加深了大家的印象呢。

在python實作中我們常常用class來表示一個Node，值是data，下一個Node的位置是next，因此我們可以用node.next表示下一個Node。而尾巴Node的next會是None。

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

搜尋

在搜尋的部分，不管是找特定的值，或是特定的Index，因為我們沒辦法知道每一個Node在哪裡，我們只能從第一個 Node 開始一個一個尋找過去，所以很明顯時間複雜度會是 O(n)。

新增到頭或尾巴

如果要新增一個Node在尾巴，我們只需要把最後面的節點在連到新的Node上，如果要加到最前面的Node，我們也只需要把新的Node尾巴接到原本的頭就好了，所以複雜度會是O(1)。

在這邊讀者可能會問，如果我要新增到最後一個，我不是應該先遍歷到最後一個才能append所以複雜度是O(n)嗎 ? 這麼說其實是正確的喔~代表您對時間複雜度有更深的理解了，那為什麼我還會說是O(1)呢? 其實我們在實作的時候就可以特別去紀錄最後一個Node。

插入和刪除

插入和刪除，插入和刪除的這個「動作」也只需要O(1)的時間，我們就是把指標移來移去而已，但是如果我們今天是要從頭「尋找」到要插入或是刪除的位置(譬如說，我要插入或刪除index是5的節點)，接著再去進行插入和刪除的動作。這樣的時間複雜度就會等於「搜尋O(n)」+「插入/刪除O(1)」也就是O(n)囉。

結論

LinkedList對於一些初學者來說可能真的不好理解，我建議可以多上網看看一些別人實作的方式，然後自己動手做，更重要的是因為節點跟節點之間是用指標來去連結的，所以很有可能一不小心，把連結斷掉後就會找不到後面的資料了，至於更詳細的做法，我會在後面的篇幅再詳細告訴大家，這邊大家只需要初步的了解LinkedList的概念就足夠囉！