下一篇：Python實作單向鏈表（下）：整合式實作增刪改查操作
鏈表簡介
鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，
鏈表和陣列區別：鏈表不需要一系列連續的記憶體
鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成，每個結點包括兩個部分：
- 一個是存盤資料元素的資料域
（在下面代碼中用data存盤）； - 另一個是存盤下一個結點地址的指標域
（在下面代碼中用next存盤）
鏈表優點
-
鏈表最明顯的好處就是，常規陣列排列關聯專案的方式可能不同于這些資料專案在記憶體或磁盤上順序，資料的存取往往要在不同的排列順序中轉換，鏈表允許插入和移除表上任意位置上的節點，但是不允許隨機存取，
-
鏈表克服了陣列鏈表需要預先知道資料大小的缺點，鏈表結構可以充分利用計算機記憶體空間，實作靈活的記憶體動態管理，
鏈表缺點
- 失去了陣列隨機讀取的優點
- 鏈表由于增加了結點的指標域，空間開銷比較大，
單向鏈表
結點的指向是單向的，從前一個結點指向后一個結點
碎碎念：是節點還是結點？
轉自：《【資料結構】節點和結點，到底怎么區分？》
一篇文章徹底把區別說清楚了，感激涕零
節點呢，被認為是一個物體，有處理能力，比如，網路上的一臺計算機；而結點則只是一個交叉點，像“結繩記事”，打個結，做個標記，僅此而已，還有就是，要記住：一般演算法中點的都是結點，
大體思路
需要寫兩個類：
- Node類：用于創建結點，并將結點以（人類）能看懂的字串形式輸出，而不是顯示記憶體地址
- LinkedList類：用于將各結點連成鏈表，并實作對鏈表進行操作的一些方法
代碼
創建Node類：
class Node:
def __init__(self, data, next=None):
self.data = data # 資料，當前結點的元素
self.next = None # 指標，指向下一個結點
def __repr__(self): # 把結點表示為一個字串
return "NodeValue({})".format(self.data)
呼叫測驗：
n = Node(1)
print(n) # 因為寫了__repr__方法，所以輸出的是Node(1)，而不是記憶體地址
創建LinkedList類：
準備作業：初始化方法 & 列印字串方法
想要達到的輸出效果類似于：
NodeValue(1) --> NodeValue(3) --> NodeValue(4) --> END
class LinkedList:
def __init__(self):
self.head = None # 初始化頭結點
## 列印鏈表
def __repr__(self):
cursor = self.head
string_repr = ""
while cursor:
string_repr += f"{cursor} --> "
cursor = cursor.next
return string_repr + "END"
「查」：方法
1. is_empty() 判斷鏈表是否為空
def is_empty(self):
return self.head == None
2. length() 回傳鏈表長度
def length(self):
if self.head is None:
return 0
cursor = self.head
count = 0
while cursor:
count += 1
cursor = cursor.next
return count
3. exist(data) 判斷結點是否存在
def exist(self, data):
"""
:return: True or False
:rtype: Boolean
"""
cursor = self.head
while cursor:
if cursor.data == data:
return True
else:
cursor = cursor.next
return False
4. travel() 遍歷整個鏈表
def travel(self):
if self.head is None:
return None
cursor = self.head
while cursor:
print(cursor)
cursor = cursor.next
5. getitem(index) 根據索引，得到鏈表中該位置的值
def getitem(self, index):
current = self.head
if current is None:
raise IndexError("This is an empty linked list.")
for i in range(1, index):
# 目標超過鏈表范圍
if current.next is None:
raise IndexError("Index out of range")
current = current.next
return current
6. search(data) 回傳該結點出現的左數第一個的位置，不存在回傳-1
def search(self, data):
if self.exist(data) == False:
return -1
else:
cursor = self.head
count = 0
while cursor:
count += 1
if cursor.data == data:
return count
else:
cursor = cursor.next
「增」：方法
7. insert_head(data) 在鏈表頭部添加元素
def insert_head(self, data):
new_node = Node(data) # 創建一個新結點
if self.head: # 如果已存在頭部結點
# 讓新創建的結點的next指向原本的頭結點
# 也就是說，新結點成為了原本的頭結點的上一個結點
new_node.next = self.head
self.head = new_node # 重置頭結點
8. append(data) 在鏈表尾部添加元素
def append(self, data):
if self.head is None:
# 如果鏈表目前為空，則在頭結點添加該元素
self.insert_head(data)
else:
cursor = self.head
while cursor.next: # 遍歷鏈表
cursor = cursor.next
# 創建一個新結點添加到鏈表尾部
cursor.next = Node(data)
9. insert(pos, data) 在鏈表中的指定位置添加元素
def insert(self, pos, data):
"""
:param pos: 要插入結點的位置，從0開始，
pos > 0，代表是從左開始數的位置
pos = 0，代表在頭部添加
pos < 0，代表是從右開始數的位置，倒數從-1開始
也就是說 鏈表長度 + 倒數下標 = 正數下標
:type pos: int
:param data: 要插入的結點值
:type data: int
"""
if pos > 0:
if self.head is None:
# 如果鏈表目前為空，則在頭結點添加該元素
self.insert_head(data)
else:
new_node = Node(data) # 創建一個新結點
# 通過回圈，得到新結點的上一個結點
pre = self.head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 讓新結點指向原本該位置的結點
new_node.next = pre.next
# 讓上一個結點指向新結點
pre.next = new_node
elif pos == 0:
self.insert_head(data)
elif pos < 0:
if self.head is None:
# 如果鏈表目前為空，則在頭結點添加該元素
self.insert_head(data)
else:
new_node = Node(data)
# 通過回圈，得到新結點正數順序的上一個結點
leftpos = self.length() + pos
pre = self.head
count = 0
while count < (leftpos - 1):
count += 1
pre = pre.next
# 讓新結點指向原本該位置的結點
new_node.next = pre.next
# 讓上一個結點指向新結點
pre.next = new_node
「刪」：方法
10. delete_head() 洗掉頭結點
def delete_head(self):
temp = self.head
if self.head:
self.head = temp.next
temp.next = None
11. delete_tail() 洗掉尾結點
cursor = self.head
if self.head:
if self.head.next is None:
self.head = None
else:
while cursor.next.next:
cursor = cursor.next
cursor.next, cursor = None, cursor.next
elif self.head == None:
return "This is an empty linked list."
12. remove(data) 洗掉結點，若存在值相等的結點，僅洗掉左起第一個
def remove(self, data):
"""
:return: 回傳洗掉結點后的鏈表；若傳入的資料在鏈表中不存在，則回傳原鏈表
"""
if self.exist(data) == False:
return self
else:
pre = self.head
cursor = pre.next
count = 0
while cursor:
if cursor.data == data:
# 洗掉，也就是讓該結點的上一結點直接連到該結點的下一結點
pre.next = cursor.next
cursor.next = None
return self
else:
pre = pre.next
cursor = cursor.next
13. removeall(data) 洗掉結點，若存在值相等的結點，洗掉所有
def removeall(self, data):
"""
:return: 回傳洗掉結點后的鏈表；若傳入的資料在鏈表中不存在，則回傳原鏈表
"""
while self.exist(data):
self.remove(data)
return self
「改」：方法
14. setitem(index, data) 根據索引，為鏈表中該位置的值重新賦值
def setitem(self, index, data):
current = self.head
if current is None:
raise IndexError("This is an empty linked list.")
for i in range(1, index):
# 目標超過鏈表范圍
if current.next is None:
raise IndexError("Index out of range")
current = current.next
current.data = data
其他方法
15. linklist(object) 傳入物件，一次性將序列中的所有元素構建成一個鏈表
def linklist(self, object):
self.head = Node(object[0])
temp = self.head
for i in object[1:]:
node = Node(i)
# 將上一個結點指向下一個結點
temp.next = node
temp = temp.next
下一篇：Python實作單向鏈表（下）：整合式實作增刪改查操作
-
Info
- Author: Shanshan Yan
- Wechat: shanshan700224
- Copyright: All rights reserved
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/163566.html
標籤：其他