用最容易的方式學會單鏈表（Python實現）

  • 2019 年 10 月 30 日
  • 筆記

單鏈表與數組

在本部落格中，我們介紹單鏈表這種數據結構，鏈表結構為基於數組的序列提供了另一種選擇（例如Python列表）。

基於數組的序列也會有如下缺點：

  1. 一個動態數組的長度可能超過實際存儲數組元素所需的長度
  2. 在實時系統中對操作的攤銷邊界是不可接受的
  3. 在一個數組內部執行插入和刪除操作的代價太高

基於數組的序列和鏈表都能夠對其中的元素保持一定的順序，但採用的方式截然不同。

  • 數組是採用一整塊的記憶體，能夠為許多元素提供存儲和引用。
  • 鏈表則是用更為分散的結構，採用稱為節點的輕量級對象，分配給每一個元素。每個節點維護一個指向它的元素的引用，並含一個或多個指向相鄰節點的引用。

鏈式結構

什麼是線性表的鏈式存儲，即採用一組任意的存儲單元存放線性表的元素，這組存儲元素可以是連續的，也可以是不連續的。連續的我們當然好理解，那如果不連續呢？就可以通過一條鏈來連接，什麼是鏈？最直觀的感受如下圖：

chains_1251px_1205993_easyicon.net.png

我們知道，C語言中有指針，指針通過地址來找到它的目標。如此說來，一個節點不僅僅有它的元素，還需要有一個它的下一個元素的地址。這兩部分構成的存儲結構稱為節點（node），即節點包含兩個域：數據域和指針域，結構的結構圖如下：

節點.png

Python中的引用

那麼，這裡需要指針和地址，我們在學習基礎的時候沒聽說Python有C或C++中的指針啊，Python中指針是什麼？我們先把這個概念放一放，一提到指針可能初學C和C++的人都害怕（本人也害怕），先來理解一下Python裡面變數的本質。

>>> a = 100  >>> b = 100  >>> id(a)  4343720720  >>> id(b)  4343720720  >>>

我們能看到id(a) == id(b)，為什麼a和b的ID是一樣的呢？我們來看一下這個圖：

id.png

我們利用上圖來打一個比喻，可能不是很準確方便我們進行理解。如果電腦中當成是一棟房屋，那麼記憶體地址（4343720720）就應該是其中的一個房子，這個房子可以存儲數據（100，也可以存10），而房名就是變數名（a、b）。房子被小a買走了（利用起來），小a就指向這個房子，同理，小b也指向這個房子。房子里存儲的數據都是100，所以雖然a和b的名字不同，但他們住同一房子。

我們再來看一下下面這個程式碼：

>>> a, b = 10, 20  >>> id(a)  4343717840  >>> id(b)  4343718160  >>> a, b = b, a  >>> id(a)  4343718160  >>> id(b)  4343717840  >>>

2.png

是不是也非常好理解了，小a和小b買了不同的房子（4343717840和4343718160），存著不同的數據（a=10, b=20）。最後他們交換了房子，同時交換了房裡的數據。

變數本身就存儲的一個地址，交換他們的值就是把自己的指向更改。Python中沒有指針，所以實際編程一般用引用來代替。這裡對Python引用的介紹不是很詳細，如果讀者還是不明白，可以通過其他的資料進行深入了解。

節點定義與Python程式碼實現

節點，用於構建單鏈表的一部分，有兩個成員：元素成員、指針域成員。

元素成員：引用一個任意的對象，該對象是序列中的一個元素，下圖中的a1、a2、…、an

指針域成員：指向單鏈表的後繼節點，如果沒有後繼節點，則為空

timg.jpeg

熟悉完鏈式結構，我們就能很好的寫出節點的Python程式碼了。

class Node(object):      """聲明節點"""        def __init__(self, element):          self.element = element  # 給定一個元素          self.next = None  # 初始設置下一節點為空

那麼，什麼是單鏈表

單鏈表 最簡單的形式就是由多個節點的集合共同構成一個線性序列。每個節點存儲一個對象的引用，這個引用指向序列中的一個元素，即存儲指向列表的下一個節點。

單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。鏈表中的數據是以結點來表示的，每個結點的構成：元素(數據元素的映象) + 指針(指示後繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。

其實，上面的術語用生活中的大白話來解釋，就是我們現在有三個人——我、你、他。當我用手指指向你（注意：因為是單鏈表，所以你不能指向我），你用手指指向他，這樣就形成了一個單鏈表。手指就是一個引用，而「我、你、他」就是序列中的元素。「我->你->他」方式就是一個簡單單鏈表，不知道你理解了沒有？

  • 頭結點：鏈表的第一個節點

  • 尾節點：鏈表的最後一個節點

    從頭節點開始，通過每個節點的「next」引用，可以從一個節點移動到另一個節點，從而最終到達列表的尾節點。

    若當前節點的「next」引用指向空時，我們可以確定該節點為尾節點。這一過程，我們通過叫做遍歷鏈表。

單鏈表有哪些操作

鏈表的操作並不是很難，只要明白節點的結構：數據域element和指針域next。而各種操作其實就是對指針的操作，不論是增刪改查，都是先找指針，再取元素。具體有哪些基礎操作是我實現的呢？如下（當然，還有更多的操作可能使我沒想到的，希望你能在評論中提出來。）

增

  • 頭插法
  • 尾插法
  • 指定位置將元素插入

刪

  • 刪除頭結點
  • 刪除尾節點
  • 刪除指定元素

改

  • 修改指定位置上的元素

查

  • 遍歷整個單鏈表

  • 查詢指定元素是否存在

其他操作

  • 鏈表判空
  • 求鏈表長度
  • 反轉整個鏈表（面試高頻考點）

Python實現單鏈表的上述操作

# -*- coding: utf-8 -*-  # @Time      : 2019-10-30 15:50  # @Author    : yuzhou_1su  # @ContactMe : https://blog.csdn.net/yuzhou_1shu  # @File      : singly_linked_list.py  # @Software  : PyCharm      class Node(object):      """聲明節點"""        def __init__(self, element):          self.element = element  # 給定一個元素          self.next = None  # 初始設置下一節點為空      class Singly_linked_list:      """Python實現單鏈表"""        def __init__(self):          self.__head = None  # head設置為私有屬性，禁止外部訪問        def is_empty(self):          """判斷鏈表是否為空"""          return self.__head is None        def length(self):          """返回鏈表長度"""          cur = self.__head  # cur游標，用來移動遍歷節點          count = 0  # count記錄節點數量          while cur is not None:              count += 1              cur = cur.next          return count        def travel_list(self):          """遍歷整個鏈表，列印每個節點的數據"""          cur = self.__head          while cur is not None:              print(cur.element, end=" ")              cur = cur.next          print("n")        def insert_head(self, element):          """頭插法：在單鏈表頭部插入一個節點"""          newest = Node(element)  # 創建一個新節點          if self.__head is not None:  # 如果初始不為空，就將新節點的"next"指針指向head              newest.next = self.__head          self.__head = newest  # 把新節點設置為head        def insert_tail(self, element):          """尾插法：在單鏈表尾部增加一個節點"""          if self.__head is None:              self.insert_head(element)  # 如果這是第一個節點，調用insert_head函數          else:              cur = self.__head              while cur.next is not None:  # 遍歷到最後一個節點                  cur = cur.next              cur.next = Node(element)  # 創建新節點並連接到最後        def insert(self, pos, element):          """指定位置插入元素"""            # 如果位置在0或者之前，調用頭插法          if pos < 0:              self.insert_head(element)          # 如果位置在原鏈表長度之後，調用尾插法          elif pos > self.length() - 1:              self.insert_tail(element)          else:              cur = self.__head              count = 0              while count < pos - 1:                  count += 1                  cur = cur.next              newest = Node(element)              newest.next = cur.next              cur.next = newest        def delete_head(self):          """刪除頭結點"""          cur = self.__head          if self.__head != Node:              self.__head = self.__head.next              cur.next = None          return cur        def delete_tail(self):          """刪除尾節點"""          cur = self.__head          if self.__head is not None:              if self.__head.next is None:  # 如果頭結點是唯一的節點                  self.__head = None              else:                  while cur.next.next is not None:                      cur = cur.next                  cur.next, cur = (None, cur.next)          return cur        def remove(self, element):          """刪除指定元素"""          cur, prev = self.__head, None          while cur is not None:              if cur.element == element:                  if cur == self.__head:  # 如果該節點是頭結點                      self.__head = cur.next                  else:                      prev.next = cur.next                  break              else:                  prev, cur = cur, cur.next          return cur.element        def modify(self, pos, element):          """修改指定位置的元素"""          cur = self.__head          if pos < 0 or pos > self.length():              return False          for i in range(pos - 1):              cur = cur.next          cur.element = element          return cur        def search(self, element):          """查找節點是否存在"""          cur = self.__head          while cur:              if cur.element == element:                  return True              else:                  cur = cur.next          return False        def reverse_list(self):          """反轉整個鏈表"""          cur, prev = self.__head, None          while cur:              cur.next, prev, cur = prev, cur, cur.next          self.__head = prev      def main():      List1 = Singly_linked_list()      print("鏈表是否為空", List1.is_empty())        List1.insert_head(1)      List1.insert_head(2)      List1.insert_tail(3)      List1.insert_tail(4)      List1.insert_tail(5)        length_of_list1 = List1.length()      print("插入節點後，List1 的長度為：", length_of_list1)        print("遍歷並列印整個鏈表: ")      List1.travel_list()        print("反轉整個鏈表: ")      List1.reverse_list()      List1.travel_list()        print("刪除頭節點: ")      List1.delete_head()      List1.travel_list()        print("刪除尾節點: ")      List1.delete_tail()      List1.travel_list()        print("在第二個位置插入5: ")      List1.insert(1, 5)      List1.travel_list()        print("在第-1個位置插入100：")      List1.insert(-1, 100)      List1.travel_list()        print("在第100個位置插入2：")      List1.insert(100, 2)      List1.travel_list()        print("刪除元素5：")      print(List1.remove(5))      List1.travel_list()        print("修改第5個位置的元素為7: ")      List1.modify(5, 7)      List1.travel_list()        print("查找元素1:")      print(List1.search(1))      if __name__ == "__main__":      main()

輸出的測試結果

鏈表是否為空 True  插入節點後，List1 的長度為： 5  遍歷並列印整個鏈表:  2 1 3 4 5    反轉整個鏈表:  5 4 3 1 2    刪除頭節點:  4 3 1 2    刪除尾節點:  4 3 1    在第二個位置插入5:  4 5 3 1    在第-1個位置插入100：  100 4 5 3 1    在第100個位置插入2：  100 4 5 3 1 2    刪除元素5：  5  100 4 3 1 2    修改第5個位置的元素為7:  100 4 3 1 7    查找元素1:  True

總結

在我們對這些基礎操作熟練之後，我推薦的學習方法就是對網上（比如LeetCode）上與單鏈表相關的習題進行練習。具體有哪些好的習題呢？等後面寫部落格找一些經典的題並把思路寫出來，如果你找到了好的題歡迎分享給我，一起學習探討。

VirMach 便宜 VPS

QNews

QNews