Python單鏈表原理與實現(xiàn)方法詳解

更新時間：2020年02月22日 09:37:47 作者：授我以驢

這篇文章主要介紹了Python單鏈表原理與實現(xiàn)方法,結合實例形式詳細分析了Python單鏈表的具體概念、原理、實現(xiàn)方法與操作注意事項,需要的朋友可以參考下

本文實例講述了Python單鏈表原理與實現(xiàn)方法。分享給大家供大家參考，具體如下：

Python實現(xiàn)單鏈表

關于鏈表

鏈表（Linked List）是由許多相同數(shù)據(jù)類型的數(shù)據(jù)項按照特定順序排列而成的線性表。
鏈表中個數(shù)據(jù)項在計算機內存中的位置是不連續(xù)且隨機的，數(shù)組在內存中是連續(xù)的。
鏈表數(shù)據(jù)的插入和刪除很方便，但查找數(shù)據(jù)效率低下，不能像數(shù)組一樣隨機讀取數(shù)據(jù)。

單鏈表的實現(xiàn)

一個單向鏈表的節(jié)點由數(shù)據(jù)字段和指針組成，指針指向下一個元素所在內存地址
定義一個鏈表節(jié)點類,self.value實例屬性表示節(jié)點數(shù)據(jù)字段；self.next表示指針；初始化值為None

class Node(object):
  def __init__(self, value=None, next=None):
    self.value = value
    self.next = next

在單鏈表中第一個節(jié)點為頭(head)指針節(jié)點(即頭指針指向的節(jié)點為單鏈表第一個節(jié)點，后續(xù)簡稱頭指針節(jié)點)，從頭指針節(jié)點出發(fā)可以遍歷整個鏈表，進行元素查找，插入和刪除，非常重要。一般不移動head頭指針。
單鏈表中最后一個節(jié)點為尾節(jié)點，其指針為None，表示結束。
建立單鏈表我們首先需要創(chuàng)建頭指針節(jié)點（引入頭指針是為了方便操作單鏈表，對于頭指針節(jié)點，只有指針域指向鏈表第一個節(jié)點，不含實際值）

class linkedList(object):
  def __init__(self):
    self.head = Node()	# 創(chuàng)建頭指針結點
    self.length = 0	# 初始鏈表長度，頭指針節(jié)點不計入長度
  def __len__(self):	# 重寫特殊方法返回self.length
    return self.length

鏈表初始化之后，開始定義鏈表方法
鏈表頭部插入節(jié)點：
- 調用Node()傳入待插入的值value創(chuàng)建待插入節(jié)點
- 判斷當前鏈表是否為空鏈表，鏈表為空：
  - 插入節(jié)點既是鏈表頭指針指向的節(jié)點也是尾節(jié)點(指向None)
- 鏈表不為空：
  - 待插入節(jié)點指向原頭指針節(jié)點，頭指針重新指向待插入節(jié)點
  - 首先需要將原頭指針結點，存放到臨時變量中(防止head指針變更時，指針斷裂導致數(shù)據(jù)丟失，鏈表中指針就是連接的紐帶，其中某個紐帶斷裂(即指針指向其他)則后續(xù)數(shù)據(jù)都將丟失)
  - 將頭指針指向新插入節(jié)點
  - 新插入節(jié)點指針指向原頭指針節(jié)點
  - 長度+1
- ```
  def head_insert(self, value): # 鏈表頭部插入
    node = Node(value)
    if self.head.next == None:
      self.head.next = node
      node.next = None
    else:
      # 插入元素指針域指向原h(huán)ead元素
      tmp_head = self.head.next # 原頭指針節(jié)點存儲到tmp_head
      self.head.next = node # 新head指針指向node
      node.next = tmp_head # 新插入節(jié)點指向原頭指針節(jié)點
    self.length += 1
```
鏈表頭部刪除節(jié)點：
- 依舊是先判斷鏈表是否為空，為空則返回False
- 鏈表不為空時：
  - 頭指針指針域(指針域存放下一節(jié)點的內存地址，即頭指針節(jié)點)指向頭指針，也就是說鏈表第一個節(jié)點變成了頭指針head，由于head不計入鏈表，所以就相當于刪除了第一個節(jié)點(有點繞)
  - 同時返回刪除的值
- ```
  def head_del(self): # 刪除頭結點,返回頭結點的值
    if self.head.next == None:
      return False
    else:
      # 頭指針指針域指向自己
      self.head = self.head.next
      self.length -= 1
      return self.head.value
```

鏈表尾部添加節(jié)點：

創(chuàng)建待插入節(jié)點對象
判斷鏈表是否為空，為空則頭指針節(jié)點就是待插入節(jié)點，也是尾節(jié)點
鏈表不為空：
- 首先通過while循環(huán)(循環(huán)條件為節(jié)點指針是否為None)找到當前鏈表的最后一個元素
- 然后將當前最后一個元素指向待插入節(jié)點
- 長度+1

  def append(self, value):  # 鏈表尾部添加結點
    # 創(chuàng)建新插入的結點對象
    node = Node(value)
    if self.length == 0:
      self.head.next = node  # 只有一個節(jié)點，指針指向自己
    else:
      curnode = self.head.next  # 變量curnode存放指針
      while curnode.next != None:
        curnode = curnode.next
      curnode.next = node # 當為最后一個節(jié)點時，指針指向新插入節(jié)點
    self.length += 1

指定位置后面插入節(jié)點：
- 這里方法接受兩個位置參數(shù)，index插入位置和value插入值
- 依舊創(chuàng)建新節(jié)點對象
- 判斷是否為空
- 在鏈表不為空的條件下：
  - 首先定義一個變量表示當前節(jié)點，以及一個index索引比較數(shù)i
  - 使用while循環(huán)，索引比較數(shù)i != index時，更新當前節(jié)點
  - 找到索引位置節(jié)點后，首先讓插入節(jié)點指向索引位置節(jié)點的下一個節(jié)點
  - 然后讓索引位置節(jié)點指向插入節(jié)點
  - 鏈表長度+1
- ```
def insert(self, index, value):
	node = Node(value)
  if self.length == 0:
    self.head.next = node
  else:
    i = 0
    cur_node = self.head.next
    while i != index:
      cur_node = cur_node.next
      i += 1
    node.next = cur_node.next
    cur_node.next = node
  self.length += 1
```

給定值刪除該值節(jié)點：

刪除鏈表中給定的值我們需要遍歷整個鏈表，因此需要創(chuàng)建一個可迭代對象
定義節(jié)點迭代方法

def iter_node(self):
  cur_node = self.head.next	#當前節(jié)點
  while cur_node.next != None:	# 對除最后一個節(jié)點進行可迭代化處理
    yield cur_node
    cur_node = curnode.next
  if cur_node.next == None:	# 對尾節(jié)點進行可迭代化處理
    yield cur_node

重寫特殊方法–iter–，用來聲明這個類是一個迭代器

def __iter__(self): # 遍歷列表節(jié)點
  for node in self.iter_node():
     yield node.value

首先定義一個Flag變量(默認為False)，用來表示刪除狀態(tài)
依舊判斷鏈表是否為空
鏈表不為空時：
- 設置一個前驅節(jié)點(當找到需要刪除的節(jié)點時，先讓前驅節(jié)點指向刪除節(jié)點的后繼節(jié)點)
- for循環(huán)遍歷鏈表
  - 找到符合條件的值就讓前驅節(jié)點指向，刪除節(jié)點的后繼節(jié)點，然后del刪除node，F(xiàn)lag更改為True
  - 沒找到符合條件的值，就更新前驅節(jié)點，繼續(xù)遍歷

  def delete_node(self, value):
    Flag = False
    if self.length == 0:
      return False
    else:
      previous_node = self.head  # 初始化前置節(jié)點為頭結點
      for node in self.iter_node():
        if node.value == value:
          previous_node.next = node.next # 前置節(jié)點指針指向當前節(jié)點的后繼節(jié)點
          del node
          self.length -= 1
          Flag = True
        else:
          previous_node = node  # 更新前置節(jié)點的值
      return Flag

完整代碼：

# 定義鏈表節(jié)點類
class Node(object):
  def __init__(self, value=None, next=None):
    self.value = value # 節(jié)點元素
    self.next = next  # 指針


# 單鏈表類
class LinkedList(object):
  def __init__(self):
    self.head = Node() # 創(chuàng)建頭結點
    self.length = 0 # 初始化鏈表長度

  def __len__(self):
    return self.length

  def __iter__(self): # 遍歷列表節(jié)點
    for node in self.iter_node():
      yield node.value

  def iter_node(self):
    curnode = self.head.next
    while curnode.next != None:
      yield curnode
      curnode = curnode.next
    if curnode.next == None:
      yield curnode

  def head_insert(self, value): # 鏈表頭部插入
    node = Node(value)
    if self.head.next == None:
      self.head.next = node
      node.next = None
    else:
      # 插入元素指針域指向原h(huán)ead元素
      tmp_head = self.head.next # 原頭指針節(jié)點存儲到tmp_head
      self.head.next = node # 新head指針指向node
      node.next = tmp_head # 新插入節(jié)點指向原頭指針節(jié)點
    self.length += 1

  def head_del(self): # 刪除頭結點,返回頭結點的值
    if self.head.next == None:
      return False
    else:
      # 頭指針指針域指向自己
      self.head = self.head.next
      self.length -= 1
      return self.head.value

  def append(self, value):  # 鏈表尾部添加結點
    # 創(chuàng)建新插入的結點對象
    node = Node(value)
    if self.length == 0:
      self.head.next = node  # 只有一個節(jié)點，指針指向自己
    else:
      curnode = self.head.next  # 變量curnode存放指針
      while curnode.next != None:
        curnode = curnode.next
      curnode.next = node # 當為最后一個節(jié)點時，指針指向新插入節(jié)點
    self.length += 1
	
  # 這里的insert是指定值后面插入不是指定位置
  def insert(self, index, value):
    node = Node(value)
    if self.length == 0:
      self.head.next = node
      self.length += 1
    else:
      for nd in self.iter_node():
        if nd.value == index:  # 如果nd節(jié)點值等于index，則插入到nd后
          tmp_node = nd.next # 將nd的指針存放到中間變量
          nd.next = node # nd節(jié)點指向插入節(jié)點
          node.next = tmp_node  # 插入節(jié)點指向原nd.next節(jié)點
          self.length += 1
          return True
      return False

  def replace(self, old_value, new_value):
    index = 0
    if self.length == 0:
      return False
    else:
      for node in self.iter_node():
        if node == old_value:
          node.value = new_value
          index += 1
    if index != 0:
      return index # 替換節(jié)點數(shù)量(存在節(jié)點值相同情況)
    else:
      return False  # 替換失敗，未找到替換值

  def delete_node(self, value):
    Flag = False
    if self.length == 0:
      return False
    else:
      previous_node = self.head  # 初始化前置節(jié)點為頭結點
      for node in self.iter_node():
        if node.value == value:
          previous_node.next = node.next # 前置節(jié)點指針指向當前節(jié)點的后繼節(jié)點
          del node
          self.length -= 1
          Flag = True
        else:
          previous_node = node  # 更新前置節(jié)點的值
      return Flag



# 測試
l = LinkedList()
l.append(1)
l.append(2)
l.append(7)
l.append(5)
l.append(6)
l.append(7)
l.head_insert(3)
print("當前鏈表長度：%s" %l.length)
#print("刪除頭結點為：%d"% l.head_del())
print("當前鏈表長度：%s" %l.length)
i = 1
#l.delete_node(7)
for node in l:
  print("第%d個鏈表節(jié)點的值: %d"%(i, node))
  i += 1

運行結果：