小編給大家分享一下python如何實(shí)現(xiàn)單向鏈表，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
鏈表顧名思義就是～鏈
鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，他的特點(diǎn)是用一組任意的存儲(chǔ)單元存放數(shù)據(jù)元素。鏈表中每一個(gè)元素成為“結(jié)點(diǎn)”，每一個(gè)結(jié)點(diǎn)都是由數(shù)據(jù)域和指針域組成的。跟數(shù)組不同鏈表不用預(yù)先定義大小，而且硬件支持的話(huà)可以無(wú)限擴(kuò)展。
數(shù)組需要預(yù)先定義大小，無(wú)法適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減，數(shù)據(jù)小于定義的長(zhǎng)度會(huì)浪費(fèi)內(nèi)存，數(shù)據(jù)超過(guò)預(yù)定義的長(zhǎng)度無(wú)法插入。而鏈表是動(dòng)態(tài)增刪數(shù)據(jù)，可以隨意增加。
數(shù)組適用于獲取元素的操作，直接get索引即可，鏈表對(duì)于獲取元素比較麻煩需要從頭一直尋找，但是適用與增刪，直接修改節(jié)點(diǎn)的指向即可，但是對(duì)于數(shù)組就比較麻煩了，例如［1，2，3，4］需要在下標(biāo)為1的位置插入－2，則需要將［2，3，4］后移，賦值ls[1]=-2
數(shù)組從棧中分配空間, 對(duì)于程序員方便快速,但自由度小。鏈表從堆中分配空間, 自由度大但申請(qǐng)管理比較麻煩.
"""節(jié)點(diǎn)類(lèi)""" class Node(object): def __init__(self, data): self.data = data self.nex = None def __init__(self): """初始化鏈表""" self.head = None
def __len__(self): pre = self.head length = 0 while pre: length += 1 pre = pre.nex return length
追加節(jié)點(diǎn)還是比較簡(jiǎn)單的,如果head節(jié)點(diǎn)不存在，則當(dāng)前節(jié)點(diǎn)為head節(jié)點(diǎn)，否則的話(huà)找到尾節(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
獲取節(jié)點(diǎn)也是比較容易的，無(wú)非就是判斷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
找到當(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
插入節(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
刪除節(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
反轉(zhuǎn)鏈表的實(shí)現(xiàn)有多種方式，比較簡(jiǎn)單的就是生成一個(gè)新的鏈表－－》可以用數(shù)組存儲(chǔ)所有節(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)?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)
將頭賦為空就好
"""清空鏈表""" def clear(self): self.head = None
以上是“python如何實(shí)現(xiàn)單向鏈表”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計(jì)公司行業(yè)資訊頻道！
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線(xiàn)，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。
重慶分公司
重慶分公司
