🔗用Python 實現 Singly Linked List 單向鏈結串列(鍊表)

更新於 發佈於 閱讀時間約 15 分鐘

在資料結構與演算法裡,
最簡單的線性資料結構除了array之外就是linked list鏈結串列了。

Linked list又有分為單向Singly linked list 和雙向Doubly linked list

在這篇文章,會從最基礎的Singly linked list開始講起。


定義

每個節點Node只有兩個欄位

data: 儲存這個節點的資料

next: 指向下一個節點的reference (在C/C++ 就是指標pointer) 對應到圖中的箭頭


而單向連結串列就是由數個節點所構成,形成由頭部逐一串接到尾巴的串列。

raw-image

優點

1.在頭部、尾巴、或者已知節點新增、刪除、修改都是O(1) 常數時間

2.可以根據需求動態延伸或縮短有效利用記憶體空間。

缺點

1.不支援random acess,不支援Linkedlist[ index ] 這種操作。

2.如果要搜尋或者訪問某個元素,一定要從頭部開始拜訪(或搜尋)整個串列。
run-time成本相當昂貴,需要O(n)線性時間

3.只能單向訪問,相當於單行道,只能從頭到尾(從左到右)訪問。


節點Node的Python實作

class Node:

  def __init__(self, data):

    # 儲存節點的資料
    self.data = data

    # 指向下一個節點,初始化為空 None
    self.next = None

Singly Linked List的class定義 與 建構子(初始化的函式)

class LinkedList:
def __init__(self):
# 頭部節點初始化為空
self.head = None
# 尾巴節點初始化為空
self.tail = None

# 串列長度初始化為0
self.size = 0

Singly Linked List常見的操作


1.在頭部插入新節點

實作上的細節要留意,串列是空的還是已經有節點存在了。

如果是空的,直接加入即可。

如果已經有節點存在了,插入新節點之後,記得更新head頭部位置。


時間複雜度: O(1) 常數時間

  def insertAtHead(self,data):
new_node = Node(data)

self.size += 1

# If the list is empty
if self.tail is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head = new_node

return

2.在尾巴插入新節點


實作上的細節要留意,串列是空的還是已經有節點存在了。

如果是空的,直接加入即可。

如果已經有節點存在了,插入新節點之後,記得更新tail尾巴位置。


時間複雜度: O(1) 常數時間

  def insertAtTail(self, data):
new_node = Node(data)

self.size += 1

# If the list is empty
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node

return

3.在頭部刪除節點


實作上的細節要留意,串列是空的還是已經有節點存在了。

如果是空的,直接不做事return即可。

如果已經有節點存在了,刪除舊節點之後,記得更新head頭部位置。


時間複雜度: O(1) 常數時間

  def removeAtHead(self):

    if self.head is None:
      return None

    else:
      self.size -= 1

      oldHead = self.head
   
      # Update Linkage
      if self.head == self.tail:
        self.tail = None
        self.head = None

      else:
        self.head = self.head.next

      # Break Linkage
      oldHead.next = None

      return oldHead

4.拜訪整個串列


從頭拜訪整個串列,直到尾巴。

最後順便輸出整個串列長度。


時間複雜度: O(n) 線性時間

  def traverse(self):
cur = self.head

while cur:
print(cur.data, end=' -> ')
cur = cur.next
print("None")

print(f"Size of singly linked list: {self.size} \n", )
return


5.查詢某筆資料是否存在


從頭拜訪整個串列,查詢某筆資料是否存在。

如果存在,返回該節點。

如果不存在,返回None(空)。


時間複雜度: O(n) 線性時間

  def search(self, target):
cur = self.head
while cur:
if cur.data == target:
return cur

cur = cur.next

return None


6.刪除已知節點的下一個節點


實作上的細節要留意。

記得把串列長度減一。

並且串接後面剩下的節點。


時間複雜度: O(1) 常數時間

  def removeAfter(self, node):

    self.size -= 1

    removed = node.next
    the_one_after_removal = node.next.next if node.next else None
    node.next = the_one_after_removal
   

    if removed:
      removed.next = None

    return removed

7.在已知節點的後面新增一個節點


實作上的細節要留意。

記得把串列長度加一。

並且在新節點之後串接上原本後面的節點。


時間複雜度: O(1) 常數時間

  def insertAfter(self, node, new_node):

self.size += 1

the_one_after_insertion = node.next
node.next = new_node
new_node.next = the_one_after_insertion
return

完整的Singly Linked List實作和程式碼

class Node:
def __init__(self, data):
# 儲存節點的資料
self.data = data

# 指向下一個節點,初始化為空 None
self.next = None


class LinkedList:
def __init__(self):
# 頭部節點初始化為空
self.head = None
# 尾巴節點初始化為空
self.tail = None

# 串列長度初始化為0
self.size = 0


def insertAtHead(self,data):
new_node = Node(data)

self.size += 1

# If the list is empty
if self.tail is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
return

def insertAtTail(self, data):
new_node = Node(data)

self.size += 1

# If the list is empty
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node

return

def removeAtHead(self):
if self.head is None:
return None
else:
self.size -= 1

oldHead = self.head

# Update Linkage
if self.head == self.tail:
self.tail = None
self.head = None
else:
self.head = self.head.next

# Break Linkage
oldHead.next = None

return oldHead



def traverse(self):
cur = self.head

while cur:
print(cur.data, end=' -> ')
cur = cur.next
print("None")

print(f"Size of singly linked list: {self.size} \n", )
return

def search(self, target):
cur = self.head
while cur:
if cur.data == target:
return cur

cur = cur.next

return None

def removeAfter(self, node):

self.size -= 1

removed = node.next
the_one_after_removal = node.next.next if node.next else None
node.next = the_one_after_removal

if removed:
removed.next = None
return removed

def insertAfter(self, node, new_node):

self.size += 1

the_one_after_insertion = node.next
node.next = new_node
new_node.next = the_one_after_insertion
return



def test():
print(f"Empty list\n")
linkedlist = LinkedList()
linkedlist.traverse()


print("--------------------")
print(f"Insert 3 on tail\n")
linkedlist.insertAtTail(3)
linkedlist.traverse()


print("--------------------")
print(f"Insert 4 on tail\n")
linkedlist.insertAtTail(4)
linkedlist.traverse()


print("--------------------")
print(f"Insert 5 on tail\n")
linkedlist.insertAtTail(5)
linkedlist.traverse()


print("--------------------")
print(f"Insert 2 on head\n")
linkedlist.insertAtHead(2)
linkedlist.traverse()


print("--------------------")
print(f"Insert 1 on head\n")
linkedlist.insertAtHead(1)
linkedlist.traverse()


print("--------------------")
print(f"Search 3 in linked list\n")
result = linkedlist.search(3)
print( result.data )

print("--------------------")
print(f"Remove node 4, which is after node 3\n")
linkedlist.removeAfter(result)
linkedlist.traverse()


print("--------------------")
node_100 = Node(100)
print(f"Insert node 100 after node 3\n")
linkedlist.insertAfter(result, node_100)
linkedlist.traverse()




print("--------------------")
print(f"Remove 1 on Head\n")
linkedlist.removeAtHead()
linkedlist.traverse()



print("--------------------")
print(f"Remove 2 on Head\n")
linkedlist.removeAtHead()
linkedlist.traverse()


print("--------------------")
print(f"Remove 3 on Head\n")
linkedlist.removeAtHead()
linkedlist.traverse()


print("--------------------")
print(f"Remove 100 on Tail\n")
linkedlist.removeAtHead()
linkedlist.traverse()


print("--------------------")
print(f"Remove 5 on Tail\n")
linkedlist.removeAtHead()
linkedlist.traverse()

return


if __name__ == "__main__":
test()


測試輸出

Empty list

None
Size of singly linked list: 0

--------------------
Insert 3 on tail

3 -> None
Size of singly linked list: 1

--------------------
Insert 4 on tail

3 -> 4 -> None
Size of singly linked list: 2

--------------------
Insert 5 on tail

3 -> 4 -> 5 -> None
Size of singly linked list: 3

--------------------
Insert 2 on head

2 -> 3 -> 4 -> 5 -> None
Size of singly linked list: 4

--------------------
Insert 1 on head

1 -> 2 -> 3 -> 4 -> 5 -> None
Size of singly linked list: 5

--------------------
Search 3 in linked list

3
--------------------
Remove node 4, which is after node 3

1 -> 2 -> 3 -> 5 -> None
Size of singly linked list: 4

--------------------
Insert node 100 after node 3

1 -> 2 -> 3 -> 100 -> 5 -> None
Size of singly linked list: 5

--------------------
Remove 1 on Head

2 -> 3 -> 100 -> 5 -> None
Size of singly linked list: 4

--------------------
Remove 2 on Head

3 -> 100 -> 5 -> None
Size of singly linked list: 3

--------------------
Remove 3 on Head

100 -> 5 -> None
Size of singly linked list: 2

--------------------
Remove 100 on Tail

5 -> None
Size of singly linked list: 1

--------------------
Remove 5 on Tail

None
Size of singly linked list: 0

結語


一開始接觸linked list可能會覺得有點卡卡的,不像array 那樣操作起來那麼直覺。

可以透過紙筆追蹤演算法和程式執行邏輯,測試幾個簡單的小範例
會有更深刻的了解和體會!



Linked List相關的演算法練習題與詳解


經典串列題 合併已排序好的兩條串列 Merge Two Sorted Lists Leetcode #21


串列應用題 移除尾巴數來的第n個節點 Leetcode #19


鍊表應用: 簡化鏈結串列 Remove Zero Sum Nodes_Leetcode #1171


嵌套娃娃 用遞迴解 串列化簡題 Leetcode #2487


串列應用: 合併非零的節點 Merge Nodes in Between Zeros_Leetcode #2181


複製客製化鏈結串列 Copy List w/ Random Pointer_Leetcode #138


一魚多吃 用雙指針找出串列的中點 Middle of Linked list_Leetcode #876


串列應用: 反轉整個串列Reverse Linked List_Leetcode #206_Leetcode 精選75


串列應用: 刪除鏈結串列的中央節點_Leetcode #2095_Leetcode精選75題


鏈結串列中的Twin Sum的最大值_Leetcode #2130_Leetcode 75題精選


重組為奇串列和偶串列 Odd Even Linked List_Leetcode #328 精選75題


合縱連橫: 從鏈結串列應用題 理解 遞回 背後的本質

留言
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/08/13
林燃(創作小說家) 喝咖啡配楓糖鬆餅,剛剛好!😆😆😆
小松鼠-avatar-img
發文者
2024/08/13
動手學python 的引言與目錄提及了這篇文章,趕快過去看看吧!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/10
從Python 內建deque資料結構的角度切入, 同時了解deque 與 FIFO Queue相關的function用法。 collections.deque是一種兩端點皆可進出的雙端佇列 在兩端點高效地在O(1)常數時間內添加和刪除元素。 這使得deque非常適合實現FIFO Queue
Thumbnail
2024/10/10
從Python 內建deque資料結構的角度切入, 同時了解deque 與 FIFO Queue相關的function用法。 collections.deque是一種兩端點皆可進出的雙端佇列 在兩端點高效地在O(1)常數時間內添加和刪除元素。 這使得deque非常適合實現FIFO Queue
Thumbnail
2024/09/27
井字遊戲(OOXX)的遊戲描述 Tic Tac Toe(井字遊戲)是經典的雙人棋盤遊戲,在一個3x3的方格中進行。 每回合兩個玩家輪流選一個位置,先讓自己的符號(是 X 或 O)在 水平線、垂直線或對角線上連成一線的玩家宣告獲勝。
Thumbnail
2024/09/27
井字遊戲(OOXX)的遊戲描述 Tic Tac Toe(井字遊戲)是經典的雙人棋盤遊戲,在一個3x3的方格中進行。 每回合兩個玩家輪流選一個位置,先讓自己的符號(是 X 或 O)在 水平線、垂直線或對角線上連成一線的玩家宣告獲勝。
Thumbnail
2024/09/23
深入探討圖(Graph)的基本概念 及 最短路徑Shortest Path的尋找。 我們專注於廣度優先搜尋(BFS)演算法,以等權圖的最短路徑為例, 詳細說明如何利用BFS從起點擴散到終點,並且提供詳細的程式碼範例。 透過實作,讀者能夠更清楚理解圖論及BFS的應用,並體會水波紋擴散模型的重要性。
Thumbnail
2024/09/23
深入探討圖(Graph)的基本概念 及 最短路徑Shortest Path的尋找。 我們專注於廣度優先搜尋(BFS)演算法,以等權圖的最短路徑為例, 詳細說明如何利用BFS從起點擴散到終點,並且提供詳細的程式碼範例。 透過實作,讀者能夠更清楚理解圖論及BFS的應用,並體會水波紋擴散模型的重要性。
Thumbnail
看更多
你可能也想看
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
在資料結構與演算法裡, 最簡單的線性資料結構除了list之外就是linked list鏈結串列了。 Linked list又有分為單向Singly linked list 和雙向Doubly linked list 在這篇文章,會從最基礎的Singly linked list開始講起。 定義
Thumbnail
在資料結構與演算法裡, 最簡單的線性資料結構除了list之外就是linked list鏈結串列了。 Linked list又有分為單向Singly linked list 和雙向Doubly linked list 在這篇文章,會從最基礎的Singly linked list開始講起。 定義
Thumbnail
Array可以說是各種語言除了基本型別之外,最常用的資料型別與容器之一了。 Array 這種連續格子狀的資料結構,在Python要怎麼表達呢? 建立一個空的陣列 最簡單也最直接的寫法就是 array = [] # Python list [] 就對應到大家熟知的array 陣列型態的資料結
Thumbnail
Array可以說是各種語言除了基本型別之外,最常用的資料型別與容器之一了。 Array 這種連續格子狀的資料結構,在Python要怎麼表達呢? 建立一個空的陣列 最簡單也最直接的寫法就是 array = [] # Python list [] 就對應到大家熟知的array 陣列型態的資料結
Thumbnail
題目敘述 題目會給定我們一條鏈結串列Linked list的起始節點,要求我們刪除Linked List正中央的節點。 註: 正中央的節點,題目定義為索引為floor( 串列長度 / 2 ) 的節點,索引從零(Head Node)出發開始數。 例如 1 -> 2 -> 3 -> 4 鏈結
Thumbnail
題目敘述 題目會給定我們一條鏈結串列Linked list的起始節點,要求我們刪除Linked List正中央的節點。 註: 正中央的節點,題目定義為索引為floor( 串列長度 / 2 ) 的節點,索引從零(Head Node)出發開始數。 例如 1 -> 2 -> 3 -> 4 鏈結
Thumbnail
題目敘述 題目會給我們一個鏈結串列的起點head,要求我們找出這個串列的中點。 註: 如果串列長度是偶數,就回傳中間偏右的那個節點。 例如: 1 -> 2 -> 3 回傳中點為2 1 -> 2 -> 3 -> 4 ->5 -> 6 回傳中點為4 詳細的題目可在這裡看到 測試範例
Thumbnail
題目敘述 題目會給我們一個鏈結串列的起點head,要求我們找出這個串列的中點。 註: 如果串列長度是偶數,就回傳中間偏右的那個節點。 例如: 1 -> 2 -> 3 回傳中點為2 1 -> 2 -> 3 -> 4 ->5 -> 6 回傳中點為4 詳細的題目可在這裡看到 測試範例
Thumbnail
Array 在記憶體中連續分配,而且元素類型是一樣的,長度不變 優點:讀取快,可以使用座標訪問 缺點:新增、刪除慢 記憶體: 📷 範例程式碼: ArrayList 不定長度,在記憶體中連續分配的,元素沒有類型限制,任何元素都是當成object處理,如果是值類型,會有裝箱的操作 優點:讀取快 缺點:
Thumbnail
Array 在記憶體中連續分配,而且元素類型是一樣的,長度不變 優點:讀取快,可以使用座標訪問 缺點:新增、刪除慢 記憶體: 📷 範例程式碼: ArrayList 不定長度,在記憶體中連續分配的,元素沒有類型限制,任何元素都是當成object處理,如果是值類型,會有裝箱的操作 優點:讀取快 缺點:
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News