python實現(xiàn)單向鏈表詳解
本文研究的主要是Python中實現(xiàn)單向鏈表的相關(guān)內(nèi)容，具體如下。
什么是鏈表
鏈表顧名思義就是～鏈
鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，他的特點是用一組任意的存儲單元存放數(shù)據(jù)元素。鏈表中每一個元素成為“結(jié)點”，每一個結(jié)點都是由數(shù)據(jù)域和指針域組成的。跟數(shù)組不同鏈表不用預(yù)先定義大小，而且硬件支持的話可以無限擴(kuò)展。
鏈表與數(shù)組的不同點：
數(shù)組需要預(yù)先定義大小，無法適應(yīng)數(shù)據(jù)動態(tài)地增減，數(shù)據(jù)小于定義的長度會浪費內(nèi)存，數(shù)據(jù)超過預(yù)定義的長度無法插入。而鏈表是動態(tài)增刪數(shù)據(jù)，可以隨意增加。
數(shù)組適用于獲取元素的操作，直接get索引即可，鏈表對于獲取元素比較麻煩需要從頭一直尋找，但是適用與增刪，直接修改節(jié)點的指向即可，但是對于數(shù)組就比較麻煩了，例如［1，2，3，4］需要在下標(biāo)為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é)點不存在，則當(dāng)前節(jié)點為head節(jié)點，否則的話找到尾節(jié)點，將尾節(jié)點的next指向當(dāng)前節(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值的正負(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é)點
找到當(dāng)前節(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的正負(fù)，前一節(jié)點不同，需要判斷一下），然后將pre_node.nex指向當(dāng)前節(jié)點。同時將當(dāng)前節(jié)點的nex指向pre_node.nex.nex
"""插入節(jié)點"""
def insert(self, index, data):
"""
1.index 插入節(jié)點位置包括正負(fù)數(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ū)分一下索引的正負(fù)。找到當(dāng)前節(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)文章
Numpy中矩陣matrix讀取一列的方法及數(shù)組和矩陣的相互轉(zhuǎn)換實例
今天小編就為大家分享一篇Numpy中矩陣matrix讀取一列的方法及數(shù)組和矩陣的相互轉(zhuǎn)換實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
這篇文章主要為大家詳細(xì)介紹了Python實現(xiàn)隨機(jī)選擇元素功能，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-09-09
python串口如何讀取byte類型數(shù)據(jù)并訪問
這篇文章主要介紹了python串口如何讀取byte類型數(shù)據(jù)并訪問方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-09-09
Python自動化短視頻生成腳本實現(xiàn)熱門視頻流水線生產(chǎn)
有粉絲和說，最近在網(wǎng)上看到一些視頻營銷號一天能發(fā)布幾百條短視頻， 感覺是批量生成的，能不能用Python做個自動化短視頻生成腳本呢？今天就帶大家一起實現(xiàn)熱門視頻批量流水線生產(chǎn)2021-09-09
今天小編就為大家分享一篇用Python畫小女孩放風(fēng)箏的示例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-11-11
Python 分布式緩存之Reids數(shù)據(jù)類型操作詳解
這篇文章主要介紹了Python 分布式緩存之Reids數(shù)據(jù)類型操作詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06
這篇文章主要為大家詳細(xì)介紹了python3大文件解壓和基本操作，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-12-12
僅用50行Python代碼實現(xiàn)一個簡單的代理服務(wù)器
這篇文章主要介紹了僅用50行Python代碼實現(xiàn)一個簡單的代理服務(wù)器,利用最簡單的client->proxy->forward原理在socket模塊下編寫,需要的朋友可以參考下2015-04-04
Python入門案例之找出文件中出現(xiàn)次數(shù)最多的10個單詞
這篇文章主要為大家?guī)硪粋€簡單的Python入門案例——找出文件中出現(xiàn)次數(shù)最多的10個單詞，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2023-02-02
python列表插入append(), extend(), insert()用法詳解
在本篇文章里小編給大家整理了關(guān)于python列表插入append(), extend(), insert()用法以及相關(guān)知識點，有需要的朋友們參考下。2019-09-09