引言
在上一節中，筆者介紹了線性表的順序存盤結構，但順序存盤需要預先設定存盤空間，且元素插入、洗掉操作的效率不高，本節將介紹一種資料結構——鏈表，它能夠有效緩解上述問題，
鏈表的實作
簡單來說鏈表就是通過指標來鏈接下一個元素，這也是鏈表名稱的來源，鏈接實作線性表的基本思想如下：
- 把表中的元素分別存盤在一批獨立的存盤塊（表結點）中；
- 保證從組成表結構的任意節點可找到與其相關的下一個節點；
- 在前一節點里用鏈接的方式顯示地記錄與下一節點之間的關聯，
單鏈表
單向鏈接表，簡稱單鏈表，它的結點是一個二元組，形式如下圖（圖片來源于鏈表(圖文詳解)，侵刪），其表元素域保存著作為表元素的資料項（或者資料項的關聯資訊），鏈接域保存同一個表里的下一個結點的標識，
在Python中實作一個鏈表十分方便，對于空鏈接，在Python中可以直接設定為None，具體代碼如下：
class ListNode():
def __init__(self, val, next=None):
self.val = val
self.next = next
這個ListNode類中只定義了一個初始化方法，它給物件的資料域和指標域賦值，
單鏈表的基本操作:
- 創建空鏈表：在Python中，直接將頭結點的值和鏈接設定為None即可，
- 洗掉鏈表：將頭結點的值和鏈接設定為None，
- 判斷表是否為空：在Python中，直接檢查頭結點是否為None即可，
- 添加表結點：如果是向頭部插入節點，可以直接創建一個新鏈表，然后將該鏈表表頭的指標指向舊鏈表即可；如果非頭部插入，則需要設定游標來進行表遍歷，到達指定位置后按照斷連存盤后半段——插入——拼接后半段這樣的順序操作即可，
- 洗掉表結點：同理添加結點，
- 求表的長度：遍歷即可求出，
Python實作如下：
class ListNode():
def __init__(self, val, next=None):
self.val = val
self.next = next
class SingleLinkedList():
def __init__(self):
self.head = None
# 判斷鏈表是否為空
def isempty(self):
return self.head is None
# 頭插法
def prepend(self, val):
self.head = ListNode(val, self.head)
# 洗掉鏈表
def delete(self):
self.head = None
# 向鏈表某個位置插入結點
def insert(self, destination, element):
if not self.head:
raise ValueError('self.head 必須非空')
sentinel = ListNode(0) # 設定哨兵
sentinel.next = self.head
cur = sentinel
while destination >= 0:
cur = cur.next
destination -= 1
tmp = cur.next
cur.next = ListNode(element)
cur.next.next = tmp
return sentinel.next
# 計算鏈表長度
def get_length(self):
if not self.head:
return 0
cur = self.head
length = 0
while cur:
length += 1
cur = cur.next
return length
# 洗掉頭節點
def del_firstnode(self):
if not self.head:
raise ValueError('self.head 必須非空')
self.head = self.head.next
# 洗掉某個位置的結點
def del_anynode(self, position):
if not self.head:
raise ValueError('self.head 必須非空')
sentinel = ListNode(0)
sentinel.next = self.head
cur = sentinel
while position > 0:
position -= 1
cur = cur.next
cur.next = cur.next.next
return sentinel.next
if __name__ == '__main__':
def testfunction(node):
nums = []
cur = node
while cur:
nums.append(cur.val)
cur = cur.next
return nums
sample = SingleLinkedList()
sample.isempty()
for i in range(8):
sample.prepend(i)
print(testfunction(sample.head))
sample.insert(2, 3)
print(testfunction(sample.head))
print(sample.get_length())
sample.del_firstnode()
print(testfunction(sample.head))
sample.del_anynode(1)
print(testfunction(sample.head))
sample.delete()
print(testfunction(sample.head))
總結
根據以上鏈表的操作我們可以發現以下幾個特點：
- 單鏈表查找元素的時間復雜度為O(N)；
- 單鏈表插入、洗掉元素的時間復雜度為O(1)；
- 單鏈表占用空間小，實作靈活，
參考資料
- 裘宗燕.資料結構與演算法——Python語言描述[M].北京：機械工業出版社，2015: 79-87，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/166806.html
標籤：其他
上一篇：堆疊的壓入、彈出序列