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