建站
咨詢
售后
建站咨詢
新聞中心
小編給大家分享一下python如何實現(xiàn)單向鏈表，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
什么是鏈表
鏈表顧名思義就是～鏈
鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，他的特點是用一組任意的存儲單元存放數(shù)據(jù)元素。鏈表中每一個元素成為“結(jié)點”，每一個結(jié)點都是由數(shù)據(jù)域和指針域組成的。跟數(shù)組不同鏈表不用預(yù)先定義大小，而且硬件支持的話可以無限擴展。
鏈表與數(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)?nbsp;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
以上是“python如何實現(xiàn)單向鏈表”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計公司行業(yè)資訊頻道！
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
分享名稱：python如何實現(xiàn)單向鏈表-創(chuàng)新互聯(lián)
標(biāo)題來源：http://www.dlmjj.cn/article/jdocp.html
