網站首頁 編程語言 正文
鏈表是一系列元素的集合，這些元素的內存是散亂的。
無序鏈表則是一系列邏輯無序元素的集合，只是通過鏈表數據結構連接起來。雖然這些元素整體來看是散亂的，但其中每一個元素都有一個相對于其他元素的位置信息。所以鏈表需要維持元素之間的相對位置，但是也不需要特意在一段內存空間中存儲這些位置信息。
以下圖中的元素集合為例，這些元素的位置看上去都是隨機的。如果可以為每一個元素附加一份信息，即下一個元素的位置，那么這些元素的相對位置就能通過自身指向下一個元素的鏈接來表示。
附加信息后則可表示為：
需要注意的是，使用鏈表時我們必須指明鏈表中第一個元素的位置。一旦知道第一個元素的位置，就能根據其中的鏈接信息訪問第二個元素，接著訪問第三個元素，依此類推。指向鏈表第一個元素的引用被稱作頭?。最后一個元素需要知道自己沒有下一個元素。
認真觀察鏈表，我們將每一個元素視為一個節點，鏈表則是通過他們之間的相對位置關系把這些節點串起來的。每一個節點至少包含了兩個基本屬性，首先就是節點的數據變量，其次就是節點對下一個節點位置的指向關系。
我們首先來構造節點。
節點（Node）是構建鏈表的基本數據結構。每一個節點對象都必須持有至少兩份信息。首先，節點必須包含一個數據元素，我們稱之為節點的數據變量?。其次，節點必須保存指向下一個節點的引用。下面的代碼展示了 Node 類的Python實現。在構建節點時，需要為其提供初始值。Node 類也需要包含訪問和修改數據的方法，以及指向下一 個元素的引用。
class Node:
def __init__(self, initdata):
self.data = initdata # 數據元素
self.next = None # 指向下一節點的引用
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, newdata):
self.data = newdata
def setNext(self, newnext):
self.next = newnext
需要注意的是，None?在 Node 類以及之后的鏈表中起到了重要的作用。節點指向?None?的引用代表著后面沒有新節點。所以，在 Node 的構造方法中我們將 next 的初始值設為?None?。
節點（Node）的類構建完畢后，接下來我們開始構建整個鏈表（LinkList）的類。
如前所述，鏈表是基于節點集合來構建的，每一個節點都通過顯式的引用指向下一個節點。只要知道第一個節點的位置（第一個節點包含第一個元素），其后的每一個元素都能通過對下一個節點的引用找到。因此，LinkList 類必須包含指向第一個節點的引用。下列代碼展示了 LinkList 類的構造方法。
class LinkList:
def __init__(self):
self.head = None
下圖展示了鏈表無節點和有節點的兩種情況：
我們已經有了鏈表頭的創建方法，我們規定鏈表頭的初始指向為None，當鏈表中有內容（節點）時，鏈表頭則指向節點。
那么我們還需要一個方法來判斷鏈表頭的指向。
我們使用 isEmpty 方法檢查鏈表的頭部是否為指向None的引用。布爾表達式?self.head == None?當且僅當鏈表中沒有節點時才為真。由于新的鏈表是空的，因此構造方法必須和檢查是否為空的方法保持一致。這體現了使用 None 表示鏈表末尾的好處。
class LinkList:
def isEmpty(self):
return self.head == None
接下來我們構建鏈表節點的添加方法。
為了將節點添加到鏈表中，我們需要實現?add?方法。但在實現之前，需要解決一個重要問題：新節點要被放在鏈表的哪個位置？由于鏈表是無序元素的集合，因此新元素相對于已有元素的位置并不重要。新的元素可以在任意位置。因此，將新元素放在最簡便的位置是最合理的選擇。 由于鏈表只提供一個入口（頭部），因此其他所有節點都只能通過第一個節點以及?next?鏈接來訪問。這意味著添加新節點最簡便的位置就是頭部，或者說是鏈表的起點位置。我們把新節點作為鏈表的第一個節點，并且把已有的節點鏈接到該元素的后面。
下列代碼展示了 add 方法的實現：
class LinkList:
def add(self, item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
代碼第 3 行創建一個新節點，并且將?item?作為其數據。現在需要將新節點與已有的鏈表結構鏈接起來。這一過程需要兩步，如下圖所示。圖中第 1 步（代碼第 4 行），將新節點的?next?引用指向當前鏈表中的第一個節點。 這樣一來，原來的鏈表就和新節點正確地鏈接在了一起。圖中第 2 步，修改鏈表頭的指向， 使其指向新創建的節點。代碼第 5 行的賦值語句，完成了這一操作。
上述兩步的順序非常重要。如果顛倒代碼第 4 行和第 5 行的順序，會發生什么呢？如果先修改鏈表頭的指向，由于頭節點是唯一指向鏈表節點的外部引用，因此所有的已有節點都將丟失并且無法訪問。
接下來我們要實現的方法還有?length 、search 以及 remove?，這些方法都基于遍歷鏈表。遍歷是指系統地訪問每一個節點，具體做法是額外用一個外部引用從鏈表的頭節點開始訪問。隨著訪問每一個節點，我們將這個外部引用通過“遍歷”下一個引用來指向下一個節點。
實現length方法（計算鏈表中節點的個數/鏈表長度）
class LinkList:
def length(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
為了實現 length 方法，需要遍歷鏈表并且記錄訪問過多少個節點。上述代碼展示了計算鏈表中節點個數的Python代碼。current 就是外部引用，它在第 3 行中被初始化為鏈表頭的引用。此時如果鏈表中沒有節點，current?將指向?None，如果鏈表中有節點，current 此時就是指向鏈表中的第一個結點。
在計算開始時，由于沒有訪問到任何節點，因此 count 被初始化為 0 。第 5~7 行實現遍歷過程。只要 current 指向的不是鏈表的結尾（None），就將它指向下一個節點（第 7 行）。每當current 指向一個新節點時，將count加 1。最終，循環完成后返回 count 。
實現search方法（搜索鏈表中的某個節點）
在鏈表中搜索一個值同樣也會用到遍歷。每當訪問一個節點時，檢查該節點中的元素是否與要搜索的元素相同。在搜索時，可能并不需要完整遍歷鏈表就能找到該元素。事實上，如果遍歷到鏈表的末尾，就意味著要找的元素不在鏈表中。如果在遍歷過程中找到所需的元素，就沒有必要繼續遍歷了。
class LinkList:
def search(self, item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
上述代碼展示了 search 方法的實現。與在 length 方法中相似，遍歷從列表的頭部開始（第3行）。我們使用布爾型變量?found?來標記是否找到所需的元素。由于一開始時并未找到該元素，因此第 4 行將?found 初始化為False?。
第 5 行的循環既考慮了是否到達鏈表末尾，也考慮了是否已經找到目標元素。只要還有未訪問的節點并且還沒有找到目標元素，就繼續檢查下一個節點。第 6 行檢查當前節點中的元素是否為目標元素。如果是，就將 found 設為True。
實現remove方法（移除鏈表中的某個節點）
remove 方法在邏輯上需要分兩步。
第 1 步，遍歷列表并查找要移除的元素(節點)。一旦找到該元素（假設元素在鏈表中），就必須將其移除。第 1 步與 search 非常相似。從一個指向鏈表頭節點的外部引用開始，遍歷整個鏈表，直到遇到需要移除的元素。假設目標元素已經在鏈表中，因此我們預測循環會在?current?抵達?None?之前結束。這意味著可以在判斷條件中使用布爾型變量 found?。
第 2 步，移除元素(節點)。當?found 被設為 True?時，current?將指向需要移除的節點。該如何移除它呢？一種做法是將節點包含的值替換成表示其已被移除的標識值（比如 None 或者 Null，完全可以自定義）。這種做法的問題是，節點的數量和元素的數量不再匹配。更好的做法是移除整個節點。
為了將包含元素的整個節點移除，需要將其前面的節點中的 next 引用指向 current 之后的節點。然而，并沒有反向遍歷鏈表的方法。由于current?已經指向了需要修改的節點之后的節點，此時做修改為時已晚。
這一困境的解決方法就是在遍歷鏈表時使用兩個外部引用。current 與之前一樣，標記在鏈表中的當前位置。新的引用 previous 總是指向 current 上一次訪問的節點。這樣一來，當current 指向需要被移除的節點時，previous 就剛好指向真正需要修改的節點。
class LinkList:
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if current == None:
return found
if previous == None:
self.head = current.getnext()
else:
previous.setNext(current.getNext())
上面的代碼展示了完整的 remove 方法。第 3~4 行對兩個引用進行初始賦值。注意，current 與其他遍歷例子一樣，從鏈表的頭節點開始。由于頭節點之前沒有別的節點，因此?previous 的初始值是None。
第 7~8 行檢查當前節點中的元素是否為要移除的元素。如果是，就設 found 為 True 。 如果不是，則將 previous 和 current 往下一個節點的方向各移動一次。這兩條語句的順序十分重要。必須先將 previous 移動到current 的位置，然后再移動 current。這一過程經常被稱 為“蠕動”，因為?previous 必須在 current 移動之前指向其當前位置。
下圖展示了這一過程：
一旦搜索過程結束，就需要執行移除操作。如移除圖中數據值為 17 的節點，修改過程如下：
有一種特殊情況需要注意，如果被移除的節點正好是鏈表的第一個節點，那么?current?會指向鏈表中的第一個節點，previous 的值則是None?。在這種情況下，需要修改鏈表的頭節點，而不是 previous 指向的節點，如圖所示：
代碼第 13 行檢查是否遇到上述特殊情況。如果?previous?沒有移動，當?found?被設為True 時，它的值仍然是None 。在這種情況下 （第13行），鏈表的頭節點指向被修改成指向當前頭節點的下一個節點，從而達到移除頭節點的效果。但是，如果?previous?的值不是None ，則說明需要移除的節點在鏈表結構中的某個位置。在這種情況下，previous?指向了 next 引用需要被修改的節點。第?16?行使用 previous 的 setNext 方法來完成移除操作。注意，在兩種情況中，修改后的引用都指向current.getNext()?。
代碼匯總
# 構造節點
class Node:
def __init__(self, initdata):
self.data = initdata # 數據元素
self.next = None # 指向下一節點的引用（python變量賦值的本質是引用）
def getData(self): # 獲取節點的數據元素值
return self.data
def getNext(self): # 獲取下一節點的引用 若有節點則直接視作為下一節點
return self.next
def setData(self, newdata): # 給節點的數據元素設置值
self.data = newdata
def setNext(self, newnext): # 給節點設置對下一節點的引用
self.next = newnext
# 構造鏈表
class LinkList:
def __init__(self): # 設置鏈表的頭部指向 無節點時為None
self.head = None
def isEmpty(self): # 判斷鏈表是否為空（是否有節點）
return self.head == None
def add(self, item): # 給鏈表增加新節點（從鏈表頭位置增加）
temp = Node(item) # 創建節點并對新節點數據元素賦值
temp.setNext(self.head) # 新節點指向當前鏈表中的第一個節點
self.head = temp # 鏈表頭指向新節點
def length(self): # 計算鏈表長度（節點個數）
current = self.head # 引入current作為指向標識 指向第一個節點 或者None
count = 0 # 引入count作為計數變量
while current != None: # 當指向標識指向的不是鏈表末尾的None時
count = count + 1 # 節點計數加一
current = current.getNext() # 指向標識向后移動
return count
def search(self, item): # 搜索鏈表中節點
current = self.head # 引入current作為指向標識 指向第一個節點
found = False # 引入found作為尋找狀態標識
while current != None and not found: # 當current沒有指向None 并且 未找到節點
if current.getData() == item: # 如果current當前指向的節點是尋找的節點
found = True # 找到
else: # 否則
current = current.getNext() # 指向標識向后移動
return found
def remove(self, item): # 從鏈表中移除節點
current = self.head # 引入current指向標識指向第一個節點
previous = None # 引入previous指向標識指向current的上一個節點 所以當current指向第一個節點時 previous初始化指向的是None
found = False # 引入尋找狀態標識 尋找需要移除的節點
while not found: # 遍歷節點 以找到為循環結束條件
if current.getData() == item: # 如果當前節點是目標節點
found = True # 找到
else: # 當前節點不是目標節點
previous = current # previous指向當前節點
current = current.getNext() # current指向移動到下一個節點
if current == None: # 如果到最后都沒找到目標節點
return found
# 搜索過程結束
if previous == None: # 如果previous目前指向的是None 代表current指向的是鏈表的第一個節點 也就是說刪除的目標節點就是第一個節點
self.head = current.getnext() # 鏈表頭直接指向None表示刪除第一個節點
else: # 其他情況下
previous.setNext(current.getNext()) # 當前節點的上一個節點指向當前節點的下一個節點
無注釋版：
class Node:
def __init__(self, initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, newdata):
self.data = newdata
def setNext(self, newnext):
self.next = newnext
class LinkList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self, item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def length(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def search(self, item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if current == None:
return found
if previous == None:
self.head = current.getnext()
else:
previous.setNext(current.getNext())
代碼運行結果如下圖：
總結
原文鏈接：https://blog.csdn.net/jiang1126/article/details/123359796
相關推薦
- 2022-09-12 詳解APScheduler如何設置任務不并發_python
- 2022-06-02 C語言基于EasyX庫實現有圖形界面時鐘_C 語言
- 2021-12-15 幾個小技巧幫你實現Golang永久阻塞_Golang
- 2022-10-25 Python繪制loss曲線和準確率曲線實例代碼_python
- 2023-01-31 iOS?底層alloc?init?new?源碼流程示例分析_IOS
- 2022-03-15 antd-mobile 請求時Loading組件
- 2022-07-31 C語言編程基礎char類型轉換示例_C 語言
- 2022-03-22 C++對象與繼承使用中一些問題介紹_C 語言
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速