Linked List (鏈表) 是一種常見的資料結構，用來儲存一系列的元素。與陣列 (Array) 不同，Linked List 的元素稱為節點 (Node) 在記憶體中不必是連續的。每個節點除了儲存資料外，還會儲存一個指向下一個節點的參考 (指標)。

但是很不巧的 Python 並沒有像 Java 有支援 Linked List，雖然本系列是以 Python 為主，但是也不會直接使用高階 API 來實作，因為這樣就沒有意義了，所以會使用 Python 來自己建立類別來實現，甚至之後的有些資料結構 Python 都沒有，我也會用 Python 來自定義出類別。

為什麼要用 Linked List?

相較 Array，Linked List 可以隨時增加或刪除元素，不需要事先宣告大小，而且在在已知位置插入或刪除元素時，只需改變指標，不需搬移其他元素，也就是說如果程式需要頻繁的新增與刪除，Linked List 表現會更為優秀；但是 Linked List 不論是哪種型態的，最多只會儲存前後 Node 的位址，所以當需要查詢的時候，就必須遍歷整個 Linked List，所以在這部分就不及 Array 的效率。

Linked List 的種類

常見的 Linked List 有以下這幾種型態:

• Singly Linked List (單向鏈表): 每個 Node 只指向下一個節點。
• Doubly Linked List (雙向鏈表): 每個 Node 同時指向前一個和下一個節點。
• Circular Linked List (循環鏈表): 最後一個 Node 指向第一個節點，形成一個環。

Node 的結構

看完 Linked List 的種類，其實會發現這些的差異都在 Node，有的 Node 只指向下一個節點，有 Node 同時指向前一個和下一個節點，接下來我們就用 Python 來演式 Node 的結構:

• Node in a Singly Linked List

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

• Node in a Doubly Linked List

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

• Node in a Circular Linked List

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

從前述的程式碼看起來，雖然 Singly Linked List 與 Circular Linked List 一致，但是 Singly Linked List 在最後一個 Node 會指向 None，而 Circular Linked List 的最後一個 Node 會指向第一個 Node 形成一個閉環。

自己建立一個 Linked List

如果你是第一次學習 Linked List 看到這邊會一臉矇，會浮現出這是什麼? 怎麼用? 好像懂的又不懂的感覺，我們就以 Singly Linked List 為例:

• Create a Node class

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

• Create a LinkedList class

class LinkedList:
	def __init__(self):
		self.head = None

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

寫到這裡，已經完成一個沒有任何功能的 Linked List，這邊說明一下 Linked List class 的 head 是什麼，他代表的就是 Node，可以想像一下，Node 就是一個一個的點，Linked List 是將這些點整個串起來；而 __iter__ 為了後續要 print 出 Linked List 的內容，所實作的方法，只是為了讓這個資料結構可以透過 for loop 來印出，這部分不在本系列的範圍，就不多做解釋。接下來我們就繼續建立一些常見的方法，讓這個 Linked List 更完整。

• Create an append() method

  說明一下這段代碼的流程:

  • 有資料要加入這個 Linked List，會建立一個沒有連接的 Node 並把資料放進去 (new_node)
  • 判斷這個 Linked List 是不是空的，如果是這個新的 Node 就會作為第一個 Node
  • 如果不是空的，就要遍歷整個 Linked List 直到 self.head.next == Node，把新的 Node 放在最後面

class LinkedList:
	def __init__(self):
		self.head = None

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

	def append(self, data):
		new_node = Node(data)
		if self.head == None:
			self.head = new_node
			return
		
		current = self.head
		while current.next:
			current = current.next
		current.next = new_node

• Create an insert() method

  append() 是把新的元素，一直往 Linked List 後面添加，接下來我們來實作，指定 index 的插入功能

class LinkedList:
	def __init__(self):
		self.head = None

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

	def append(self, data):
		new_node = Node(data)
		if self.head == None:
			self.head = new_node
			return
		
		current = self.head
		while current.next:
			current = current.next
		current.next = new_node
	
	def insert(self, index, data):
		new_node = Node(data)
		
		# 插在頭部
		if index == 0:
			new_node.next = self.head
			self.head = new_node
			return
		
		# 遍歷 Linked List 找 index
		current = self.head
		pos = 0
        while current and pos < index - 1:
            current = current.next
            pos += 1
        
        if current is None:
            return False

        # 插入新節點
        new_node.next = current.next
        current.next = new_node
        return True

到這邊我們就先來測試一下程式，透過 append() 與 insert() 把元素放入，再透過 for loop 印出來，我們可以看到所有的元素都被依序印出來了。

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


class LinkedList:
    def __init__(self):
        self.head = None

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

    def append(self, data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            return

        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def insert(self, index, data):
        new_node = Node(data)

        # 插在頭部
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        # 遍歷 Linked List 找 index
        current = self.head
        pos = 0

        while current and pos < index - 1:
            current = current.next
            pos += 1

        if current is None:
            return False

        # 插入新節點
        new_node.next = current.next
        current.next = new_node
        return True


ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.insert(1, 9)

for value in ll:
    print(value, end=" ")  # Output: 1 9 2 3

LeetCode

• LeetCode 206. Reverse Linked List
• LeetCode 21. Merge Two Sorted Lists
• LeetCode 141. Linked List Cycle

結語

本文章只實作了 append() 與 insert() 方法，還有很多方法還沒實作，這邊就不一一實作了，Linked List 是一種靈活且常用的資料結構，適合用於需要頻繁插入、刪除元素的場合。雖然存取速度不如陣列，但在某些情境下能大幅提升效率。建議初學者多加練習，熟悉其基本操作與應用。