無序清單 - 連結清單

無序清單的實作, 也是主要了解指針移動過程即可, 這些線性結構都是相似的.

# 簡單地解釋一下, 然後重點是上代碼即可.

  1 """
  2 無序清單-連結清單
  3     被構造項的集合, 每個項保持相對于其他項的相對位置, 鍊式存儲
  4 
  5 結構:
  6     節點: 包含 資料區 和指針區 (存儲下一個元素的位置, 或指向下元素)
  7     鍊式存儲: 節點之間, 通過指針進行連接配接
  8 
  9 思路:
 10     節點: 既然包含多種成分, 自然想到用 Class 去封裝呀
 11     指針: Python中沒有指針的概念, 其實 "=" 就是"指向"的概念;
 12     即, Python中的變量, 就是 C 語言中的指針, 存的不是值, 而是指向變量的位址
 13     是以 Python 的變量不需要聲明, 直接指向即可, 因為它并沒有存值,而是存指針
 14 
 15 """
 16 
 17 
 18 class Node:
 19     """節點類"""
 20 
 21     def __init__(self, init_data):
 22         self.data = init_data
 23         self.next = None
 24 
 25 
 26 class UnorderedList:
 27     def __init__(self):
 28         self.head = None
 29 
 30     def is_empty(self):
 31         return self.head is None
 32 
 33     def add(self, item):
 34         """連結清單頭部插入元素節點"""
 35         node = Node(item)
 36         # 建議畫圖來了解指針 連接配接 和 斷鍊 過程
 37 
 38         # 1. 先讓 node的指針next 指向 head
 39         node.next = self.head
 40         # 2. 再讓 head 指向node
 41         self.head = node
 42 
 43     def size(self):
 44         """周遊節點,并統計節點個數"""
 45         count = 0
 46         # 建構一個遊标 current ,初始指向頭節點, 然後依次往後移
 47         current = self.head
 48         while current is not None:
 49             count += 1
 50             current = current.next  # 遊标移動
 51 
 52         return count
 53 
 54     def search(self, item):
 55         """檢測元素是否在連結清單中"""
 56         current = self.head
 57         while current is not None:
 58             # 每移動一次遊标, 就取該節點值與判斷值進行比較
 59             if current.data == item:
 60                 return True
 61             current = current.next  # 遊标往後移動
 62 
 63         return False
 64 
 65     def remove(self, item):
 66         """删除節點"""
 67         current = self.head
 68         prior = None  # 跟随current, 指向其前一個節點
 69 
 70         found = False  # 标記是否找到
 71         while not found:
 72             # 移動遊标, 然後查找到了就退出循環
 73             if current.data == item:
 74                 found = True
 75             else:
 76                 # 沒有找到則, prior先指向 current, 然後每當current 先移動一次,piror也跟着移一次
 77                 prior = current
 78                 current = current.next
 79 
 80         # 如果要删除的是 頭節點, 則将頭結點指向,被删的下一個節點
 81         if prior is None:
 82             self.head = current.next
 83         else:
 84             # 直接讓 prior 去指向 current.next 就删了
 85             prior.next = current.next
 86 
 87 
 88 
 89 
 90 if __name__ == '__main__':
 91     # test
 92     my_list = UnorderedList()
 93 
 94     my_list.add(666)
 95     my_list.add(999)
 96     my_list.add(888)
 97 
 98     print(my_list.size())
 99     print(my_list.search(999))
100 
101     my_list.remove(999)
102     print(my_list.search(999))      

輸出: 

3

True

False

這塊相對簡單, 也僅是做個記錄而已, 主要是怕自己突然給忘記了.