目錄
前言
前篇介紹 【Python】Stack(堆疊) 資料結構實作 後,接著要來談談「鏈結串列」(Linked List)
只要在大學修過資料結構之後都知道鏈結串列就是到Tree之前一定要懂的DS,主要是因為Tree也是 Node 的概念儲存 data 和 指到下一個 Node 的 pointer

藉由每個Node的pointer指向下一個Node可以將多個Node串連起來,形成 「位址Address不連續但一樣可以找到下一個資料的結構」
簡介 Linked List
什麼是Linked List?
Linked list(鏈結串列) 是一個有相似資料型態序列的nodes,每個node儲存一個data物件 與 指向下一個node位址的pointer

Linked List: 特點
- 節點資料的type、記憶體大小不用相同
- 不支援如Stack的隨機存取(Random Access),只能做循序存取 (Sequential access)
- 需額外 1. head 2. tail 3.current 空間
- head: 指向第一個node
- tail: 指向最後一個node
- current: 在循序搜尋時current會指向當前的node
Linked List: Big-O
operation | Big-O | |
search | 搜尋 | O(N) |
insert | 插入第一項 | O(1) |
append | 插入最後一項 | O(N) |
remove | 移除第一項 | O(1) |
removeLast | 移除最後一項 | O(N) |
用Python實作Linked List
首先我們先建立 class
Node
data
存資料next
指向下一個node
class Node:
def __init__(self ,data=None, next=None):
self.data = data
self.next = next
接著建立 class Node
- head 指向第一個資料
- tail 指向最後一個資料
因為一開時串列沒有資料,所以初始head和tail設為None
class SingleLinkedList:
def __init__(self):
self.head = None
self.tail = None
以下就來開始實作功能拉
append: 從tail新增資料
從tail加入資料,也就是類似於list的append
在呼叫append(self, data) 傳入data之後會先建立一個Node的instance
註:利用建構子 (constructor) 建立的物件被稱為實體 (instance)
接著判斷head是否為None
- self.head == None
- 代表這個Linked list為空,因此head 跟tail同時指向 new_node
- self.head != None
- 代表這個Linked list沒有為空,所以將tail.next指向new_node,tail就變成指向new_node



def append(self, data):
#建立 class Node 的instance(實體)
new_node = Node(data)
# 如果head == None 代表為第一個Node
if self.head == None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = self.tail.next
delete: 從tail刪除資料
可能比較直覺的會認為說刪除tail資料不是從tail直接刪掉就好了嗎?答案是NONONO,最大的原因在於這是「單向」鏈結串列,因此我們沒pointer指回前一個node,所以我們要靠重新尋訪的方式來處理

def delete(self):
if self.head == None:
return print("This list is empty")
else:
if len(self) == 1:
self.head = None
else:
#請參圖6
current_node = self.head
while current_node.next != None:
self.tail = current_node
current_node = current_node.next
self.tail.next = None
insert: 從特定node插入資料
在insert(self, index, data)我們需要傳入index 和data
- index: 第幾個node
- data: 要新增的data

當 index == 1
插入第一個node會影響到head的指標所以分開處理

else



def insert(self, index , data):
'''
To insert the data to the specific index
'''
if self.head == None:
print("You can only insert the data to a not empty list")
if not 1 <= index <= len(self):
print("{} is not in range".format(index))
elif index == 1:
#圖8
new_node = Node(data)
new_node.next = self.head
self.head = new_node
else:
#圖9
cur_idx = 1
new_node = Node(data)
current_node = self.head
while cur_idx+1 != index:
current_node = current_node.next
cur_idx += 1
new_node.next = current_node.next #圖10
current_node.next = new_node #圖11
delete_node_by_index: 刪除特定的node
if index == 1 and len(self) > 1:

index == 1 and len(self) == 1

def delete_node_by_index(self, index):
'''
To delete the specific node
'''
if self.head == None:
print("You can only delete the data from a not empty list")
#圖12
if index == 1 and len(self) > 1:
self.head = self.head.next
#圖13
elif index == 1 and len(self) == 1:
self.head = None
self.tail = None
elif 1 < index < len(self):
cur_idx = 1
current_node = self.head
while cur_idx != index:
previous_node = current_node
current_node = current_node.next
cur_idx += 1
previous_node.next = current_node.next
elif index == len(self):
cur_idx = 1
current_node = self.head
while cur_idx != index:
previous_node = current_node
current_node = current_node.next
cur_idx += 1
previous_node.next = None
self.tail = previous_node
else:
print("index out of range")
reverse: 反轉鏈結串列
反轉前

反轉後

def reverse(self):
# reverse the order of the list
previous_node = None
current_node = self.head
self.tail = current_node
next_node = current_node.next
while next_node is not None:
current_node.next = previous_node
previous_node = current_node
current_node = next_node
next_node = next_node.next
current_node.next = previous_node
self.head = current_node
return
Linked List 完整程式碼
'''
Welcome to use my SingleLinkedList
The following line is the ouput of the SingleLinkedList
[1]1 --> [2]2 --> [3]3 --> [4]5
[index]: means the index of the node
And the following number/string of [index] is the data of the Node
'''
import os
class Node:
def __init__(self ,data=None, next=None):
self.data = data
self.next = next
class SingleLinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, data):
new_node = Node(data)
if self.head == None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = self.tail.next
#重寫
def delete(self):
if self.head == None:
return print("This list is empty")
else:
if len(self) == 1:
self.head = None
else:
current_node = self.head
while current_node.next != None:
self.tail = current_node
current_node = current_node.next
self.tail.next = None
def insert(self, index , data):
'''
To insert the data to the specific index
'''
if self.head == None:
print("You can only insert the data to a not empty list")
if not 1 <= index <= len(self):
print("{} is not in range".format(index))
elif index == 1:
new_node = Node(data)
new_node.next = self.head
self.head = new_node
else:
cur_idx = 1
new_node = Node(data)
current_node = self.head
while cur_idx+1 != index:
current_node = current_node.next
cur_idx += 1
new_node.next = current_node.next
current_node.next = new_node
def delete_node_by_index(self, index):
'''
To delete the specific node
'''
if self.head == None:
print("You can only delete the data from a not empty list")
if index == 1 and len(self) > 1:
self.head = self.head.next
elif index == 1 and len(self) == 1:
self.head = None
self.tail = None
elif 1 < index < len(self):
cur_idx = 1
current_node = self.head
while cur_idx != index:
previous_node = current_node
current_node = current_node.next
cur_idx += 1
previous_node.next = current_node.next
elif index == len(self):
cur_idx = 1
current_node = self.head
while cur_idx != index:
previous_node = current_node
current_node = current_node.next
cur_idx += 1
previous_node.next = None
self.tail = previous_node
else:
print("index out of range")
def reverse(self):
# reverse the order of the list
previous_node = None
current_node = self.head
self.tail = current_node
next_node = current_node.next
while next_node is not None:
current_node.next = previous_node
previous_node = current_node
current_node = next_node
next_node = next_node.next
current_node.next = previous_node
self.head = current_node
return
def __len__(self):
length = 0
current_node = self.head
while current_node != None:
length += 1
current_node = current_node.next
return length
def __str__(self):
current_node = self.head
chain = []
index = 1
while current_node != None:
chain.append("["+str(index)+"]"+str(current_node.data))
index += 1
current_node = current_node.next
return " --> ".join(chain)
def main():
l = SingleLinkedList()
while True:
os.system('cls' if os.name == 'nt' else 'clear')
print(__doc__)
print(l)
print("這個鏈結串列的長度為:"+ str(len(l)))
print("-"*20)
opt = input("1. 加入資料\n2. 刪除資料\n3. 插入資料\n4. 刪除特定資料\n5. 反轉串列\n0. 結束程式\n 請輸入要使用的功能:")
if opt == "1":
data = input("請輸入要加入的資料:")
l.append(data)
print(l)
elif opt == "2":
l.delete()
print(l)
elif opt == "3":
index = input("請輸入要插入的資料的index:")
data = input("請輸入要插入的資料:")
l.insert(int(index), data)
print(l)
elif opt == "4":
index = int(input("請輸入要刪除的資料的index:"))
l.delete_node_by_index(int(index))
print(l)
elif opt == "5":
l.reverse()
print(l)
elif opt == "0":
print("The Final result is: {}".format(l))
return False
else:
print("請輸入合法指令")
if __name__ == '__main__':
main()
Showcase

如果對文章內容有任何問題,歡迎在底下留言讓我知道。 如果你喜歡我的文章,可以分享我的文章,讓更多的人看見我的文章。 追蹤我的Instagram,看我分享 #愛喝咖啡 #咖啡程式 #咖啡程式吱喳 #咖啡程式白日夢 如果這篇文章對你有幫助, 可以幫我在下方按 5 個Like 讓我得到一些回饋, 支持我繼續寫出更多好文章
- 【SSH】製作SSH key教學
- 【快速架站】什麼是Hexo? 5分鐘快速架站教學
- 【Python】Quick Sort 快速排序|演算法介紹、新手快速入門
- 【Python】Insertion Sort 插入排序|演算法介紹、新手快速入門
- 【Python】Selection Sort 選擇排序|演算法介紹、新手快速入門
- 【Python】Bubble Sort 泡沫排序|演算法介紹、新手快速入門
- 【Python】Binary Search 二分搜尋|演算法介紹、新手快速入門
- 【Python】linear search 線性搜尋|演算法介紹、新手快速入門
- 【Python】什麼是演算法?|演算法介紹、新手快速入門
- 【教學】使用Sourcetree將專案push到Github|GitHub Token 產製與用法
作者寫得真的很清楚,我一看就懂,謝謝分享~~~
Thanks for your blog, nice to read. Do not stop.