本文研究的主要是Python中實現單向鏈表的相關內容，具體如下。
鏈表顧名思義就是～鏈
鏈表是一種動態數據結構，他的特點是用一組任意的存儲單元存放數據元素。鏈表中每一個元素成為“結點”，每一個結點都是由數據域和指針域組成的。跟數組不同鏈表不用預先定義大小，而且硬件支持的話可以無限擴展。
數組需要預先定義大小，無法適應數據動態地增減，數據小于定義的長度會浪費內存，數據超過預定義的長度無法插入。而鏈表是動態增刪數據，可以隨意增加。
數組適用于獲取元素的操作，直接get索引即可，鏈表對于獲取元素比較麻煩需要從頭一直尋找，但是適用與增刪，直接修改節點的指向即可，但是對于數組就比較麻煩了，例如［1，2，3，4］需要在下標為1的位置插入－2，則需要將［2，3，4］后移，賦值ls[1]=-2
數組從棧中分配空間, 對于程序員方便快速,但自由度小。鏈表從堆中分配空間, 自由度大但申請管理比較麻煩.
"""節點類"""class Node(object): def __init__(self, data): self.data = data self.nex = Nonedef __init__(self): """初始化鏈表""" self.head = None
def __len__(self): pre = self.head length = 0 while pre: length += 1 pre = pre.nex return length
追加節點還是比較簡單的,如果head節點不存在，則當前節點為head節點，否則的話找到尾節點，將尾節點的next指向當前節點（可以添加head和tail兩個節點，就不用遞歸尋找尾節點了）
"""追加節點"""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
獲取節點也是比較容易的，無非就是判斷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
找到當前節點賦值即可
"""設置節點"""def set(self, index, data): node = self.get(index) if node: node.data = data return node
插入節點需要找到插入節點的前一個節點pre_node（索引index的正負，前一節點不同，需要判斷一下），然后將pre_node.nex指向當前節點。同時將當前節點的nex指向pre_node.nex.nex
"""插入節點"""def insert(self, index, data): """ 1.index 插入節點位置包括正負數 2.找到index-1-->pre_node的節點 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
刪除節點，也要區分一下索引的正負。找到當前節點的前一個節點pre_node和后一個節點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
反轉鏈表的實現有多種方式，比較簡單的就是生成一個新的鏈表－－》可以用數組存儲所有節點讓后倒序生成新的鏈表
在這里用下面這種方式生產：
反轉鏈表就是將node.nex–>pre_node 遞歸實現即可，然后讓tail賦值為head
"""反轉鏈表"""def __reversed__(self): """ 1.pre-->next 轉變為 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/271779.html">python/272736.html">python實現單向鏈表詳解的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
新聞熱點
疑難解答
