python如何實(shí)現(xiàn)單向鏈表

小編給大家分享一下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ù)先定義大小，而且硬件支持的話可以無限擴(kuò)展。

鏈表與數(shù)組的不同點(diǎn)：

數(shù)組需要預(yù)先定義大小，無法適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減，數(shù)據(jù)小于定義的長度會(huì)浪費(fèi)內(nèi)存，數(shù)據(jù)超過預(yù)定義的長度無法插入。而鏈表是動(dòng)態(tài)增刪數(shù)據(jù)，可以隨意增加。

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

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

鏈表基本方法實(shí)現(xiàn)（Python）

1. 初始化鏈表

"""節(jié)點(diǎn)類"""


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é)點(diǎn)

追加節(jié)點(diǎn)還是比較簡單的,如果head節(jié)點(diǎn)不存在，則當(dāng)前節(jié)點(diǎn)為head節(jié)點(diǎn)，否則的話找到尾節(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

4. 獲取節(jié)點(diǎn)

獲取節(jié)點(diǎn)也是比較容易的，無非就是判斷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é)點(diǎn)

找到當(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

6. 插入節(jié)點(diǎn)

插入節(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

7. 刪除節(jié)點(diǎn)

刪除節(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

8. 反轉(zhuǎn)鏈表

反轉(zhuǎn)鏈表的實(shí)現(xià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)

9. 清空鏈表

將頭賦為空就好

"""清空鏈表"""

def clear(self):
  self.head = None

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