python實(shí)現(xiàn)單向鏈表詳解
本文研究的主要是Python中實(shí)現(xiàn)單向鏈表的相關(guān)內(nèi)容，具體如下。
什么是鏈表
鏈表顧名思義就是～鏈
鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，他的特點(diǎn)是用一組任意的存儲單元存放數(shù)據(jù)元素。鏈表中每一個(gè)元素成為“結(jié)點(diǎn)”，每一個(gè)結(jié)點(diǎn)都是由數(shù)據(jù)域和指針域組成的。跟數(shù)組不同鏈表不用預(yù)先定義大小，而且硬件支持的話可以無限擴(kuò)展。
鏈表與數(shù)組的不同點(diǎn)：
數(shù)組需要預(yù)先定義大小，無法適應(yīng)數(shù)據(jù)動態(tài)地增減，數(shù)據(jù)小于定義的長度會浪費(fèi)內(nèi)存，數(shù)據(jù)超過預(yù)定義的長度無法插入。而鏈表是動態(tài)增刪數(shù)據(jù)，可以隨意增加。
數(shù)組適用于獲取元素的操作，直接get索引即可，鏈表對于獲取元素比較麻煩需要從頭一直尋找，但是適用與增刪，直接修改節(jié)點(diǎn)的指向即可，但是對于數(shù)組就比較麻煩了，例如［1，2，3，4］需要在下標(biāo)為1的位置插入－2，則需要將［2，3，4］后移，賦值ls[1]=-2
數(shù)組從棧中分配空間, 對于程序員方便快速,但自由度小。鏈表從堆中分配空間, 自由度大但申請管理比較麻煩.
鏈表基本方法實(shí)現(xiàn)（Python）
1. 初始化鏈表
"""節(jié)點(diǎn)類"""
class Node(object):
def __init__(self, data):
self.data = data
self.nex = None
def __init__(self):
"""初始化鏈表"""
self.head = None
2. 獲取鏈表長度
def __len__(self):
pre = self.head
length = 0
while pre:
length += 1
pre = pre.nex
return length
3. 追加節(jié)點(diǎn)
追加節(jié)點(diǎn)還是比較簡單的,如果head節(jié)點(diǎn)不存在，則當(dāng)前節(jié)點(diǎn)為head節(jié)點(diǎn)，否則的話找到尾節(jié)點(diǎn)，將尾節(jié)點(diǎn)的next指向當(dāng)前節(jié)點(diǎn)（可以添加head和tail兩個(gè)節(jié)點(diǎn)，就不用遞歸尋找尾節(jié)點(diǎn)了）
"""追加節(jié)點(diǎn)"""
def append(self, data):
"""
1.head 為none :head-->node
2.tail.nex-->node
:param data:
:return:
"""
node = Node(data)
if self.head is None:
self.head = node
else:
pre = self.head
while pre.nex:
pre = pre.nex
pre.nex = node
4. 獲取節(jié)點(diǎn)
獲取節(jié)點(diǎn)也是比較容易的，無非就是判斷index值的正負(fù)
def get(self, index):
"""
:param index:
:return:
"""
index = index if index >= 0 else len(self) + index
if len(self) < index or index < 0:
return None
pre = self.head
while index:
pre = pre.nex
index -= 1
return pre
5. 設(shè)置節(jié)點(diǎn)
找到當(dāng)前節(jié)點(diǎn)賦值即可
"""設(shè)置節(jié)點(diǎn)"""
def set(self, index, data):
node = self.get(index)
if node:
node.data = data
return node
6. 插入節(jié)點(diǎn)
插入節(jié)點(diǎn)需要找到插入節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)pre_node（索引index的正負(fù)，前一節(jié)點(diǎn)不同，需要判斷一下），然后將pre_node.nex指向當(dāng)前節(jié)點(diǎn)。同時(shí)將當(dāng)前節(jié)點(diǎn)的nex指向pre_node.nex.nex
"""插入節(jié)點(diǎn)"""
def insert(self, index, data):
"""
1.index 插入節(jié)點(diǎn)位置包括正負(fù)數(shù)
2.找到index-1-->pre_node的節(jié)點(diǎn)
3.pre_node.next-->node
node.next-->pre_node.next.next
4.head
:param index:
:param data:
:return:
"""
node = Node(data)
if abs(index + 1) > len(self):
return False
index = index if index >= 0 else len(self) + index + 1
if index == 0:
node.nex = self.head
self.head = node
else:
pre = self.get(index - 1)
if pre:
nex = pre.nex
pre.nex = node
node.nex = nex
else:
return False
return node
7. 刪除節(jié)點(diǎn)
刪除節(jié)點(diǎn)，也要區(qū)分一下索引的正負(fù)。找到當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)pre_node和后一個(gè)節(jié)點(diǎn)next_node，將pre_node.nex–>next_node即可
"""刪除某個(gè)元素"""
def delete(self, index):
f = index if index > 0 else abs(index + 1)
if len(self) <= f:
return False
pre = self.head
index = index if index >= 0 else len(self) + index
prep = None
while index:
prep = pre
pre = pre.nex
index -= 1
if not prep:
self.head = pre.nex
else:
prep.nex = pre.nex
return pre.data
8. 反轉(zhuǎn)鏈表
反轉(zhuǎn)鏈表的實(shí)現(xiàn)有多種方式，比較簡單的就是生成一個(gè)新的鏈表－－》可以用數(shù)組存儲所有節(jié)點(diǎn)讓后倒序生成新的鏈表
在這里用下面這種方式生產(chǎn)：
反轉(zhuǎn)鏈表就是將node.nex–>pre_node 遞歸實(shí)現(xiàn)即可，然后讓tail賦值為head
"""反轉(zhuǎn)鏈表"""
def __reversed__(self):
"""
1.pre-->next 轉(zhuǎn)變?yōu)?next-->pre
2.pre 若是head 則把 pre.nex --> None
3.tail-->self.head
:return:
"""
def reverse(pre_node, node):
if pre_node is self.head:
pre_node.nex = None
if node:
next_node = node.nex
node.nex = pre_node
return reverse(node, next_node)
else:
self.head = pre_node
return reverse(self.head, self.head.nex)
9. 清空鏈表
將頭賦為空就好
"""清空鏈表""" def clear(self): self.head = None
總結(jié)
以上就是本文關(guān)于python實(shí)現(xiàn)單向鏈表詳解的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
相關(guān)文章
Python實(shí)現(xiàn)公歷(陽歷)轉(zhuǎn)農(nóng)歷(陰歷)的方法示例
這篇文章主要介紹了Python實(shí)現(xiàn)公歷(陽歷)轉(zhuǎn)農(nóng)歷(陰歷)的方法,涉及農(nóng)歷算法原理及Python日期運(yùn)算相關(guān)操作技巧,需要的朋友可以參考下2017-08-08
樹莓派上利用python+opencv+dlib實(shí)現(xiàn)嘴唇檢測的實(shí)現(xiàn)
本文主要介紹了樹莓派上利用python+opencv+dlib實(shí)現(xiàn)嘴唇檢測的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
在Python中實(shí)現(xiàn)單例模式,意味著一個(gè)類只能創(chuàng)建一個(gè)實(shí)例,單例模式在某些場景下非常有用,比如當(dāng)你需要控制資源的訪問,或者當(dāng)你想確保全局只有一個(gè)對象實(shí)例時(shí),本文給大家介紹了幾種在Python中實(shí)現(xiàn)單例模式的方法,需要的朋友可以參考下2024-03-03
yield?from?是Python3.3?后新加的語言結(jié)構(gòu),可用于簡化yield表達(dá)式的使用,這篇文章主要為大家詳細(xì)介紹了yield?from的用法,需要的可以了解一下2023-12-12
python實(shí)現(xiàn)代碼審查自動回復(fù)消息
這篇文章主要介紹了python實(shí)現(xiàn)代碼審查回復(fù)消息生成的示例，幫助大家更好的理解和學(xué)習(xí)python，感興趣的朋友可以了解下2021-02-02
Python編程實(shí)現(xiàn)二叉樹及七種遍歷方法詳解
這篇文章主要介紹了Python編程實(shí)現(xiàn)二叉樹及七種遍歷方法,結(jié)合實(shí)例形式詳細(xì)分析了Python二叉樹的定義及常用遍歷操作技巧,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了Python中plot函數(shù)語法的相關(guān)資料,文章詳細(xì)介紹了MATLAB中的plot()函數(shù),包括其語法、如何繪制二維線圖、設(shè)置線型、標(biāo)記符號和顏色以及如何繪制多組二維線圖等,需要的朋友可以參考下2024-11-11
Python基于opencv的簡單圖像輪廓形狀識別(全網(wǎng)最簡單最少代碼)
這篇文章主要介紹了基于opencv的簡單圖像輪廓形狀識別(全網(wǎng)最簡單最少代碼)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
這篇文章主要介紹了Python自定義簡單圖軸簡單實(shí)例，具有一定借鑒價(jià)值,需要的朋友可以參考下2018-01-01
Django中使用CORS實(shí)現(xiàn)跨域請求過程解析
這篇文章主要介紹了Django中使用CORS實(shí)現(xiàn)跨域請求過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-08-08