python如何實現單向鏈表

小編給大家分享一下python如何實現單向鏈表，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

什么是鏈表

鏈表顧名思義就是～鏈

鏈表是一種動態數據結構，他的特點是用一組任意的存儲單元存放數據元素。鏈表中每一個元素成為“結點”，每一個結點都是由數據域和指針域組成的。跟數組不同鏈表不用預先定義大小，而且硬件支持的話可以無限擴展。

鏈表與數組的不同點：

數組需要預先定義大小，無法適應數據動態地增減，數據小于定義的長度會浪費內存，數據超過預定義的長度無法插入。而鏈表是動態增刪數據，可以隨意增加。

數組適用于獲取元素的操作，直接get索引即可，鏈表對于獲取元素比較麻煩需要從頭一直尋找，但是適用與增刪，直接修改節點的指向即可，但是對于數組就比較麻煩了，例如［1，2，3，4］需要在下標為1的位置插入－2，則需要將［2，3，4］后移，賦值ls[1]=-2

數組從棧中分配空間, 對于程序員方便快速,但自由度小。鏈表從堆中分配空間, 自由度大但申請管理比較麻煩.

鏈表基本方法實現（Python）

1. 初始化鏈表

"""節點類"""


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. 追加節點

追加節點還是比較簡單的,如果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

4. 獲取節點

獲取節點也是比較容易的，無非就是判斷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. 設置節點

找到當前節點賦值即可

"""設置節點"""

def set(self, index, data):
  node = self.get(index)
  if node:
    node.data = data
  return node

6. 插入節點

插入節點需要找到插入節點的前一個節點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

7. 刪除節點

刪除節點，也要區分一下索引的正負。找到當前節點的前一個節點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

8. 反轉鏈表

反轉鏈表的實現有多種方式，比較簡單的就是生成一個新的鏈表－－》可以用數組存儲所有節點讓后倒序生成新的鏈表
在這里用下面這種方式生產：
反轉鏈表就是將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)

9. 清空鏈表

將頭賦為空就好

"""清空鏈表"""

def clear(self):
  self.head = None

以上是“python如何實現單向鏈表”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！