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