快捷導(dǎo)航

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

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

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

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

Python實(shí)現(xiàn)單鏈表

關(guān)于鏈表

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

單鏈表的實(shí)現(xiàn)

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

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

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

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

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

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

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

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

指定位置后面插入節(jié)點(diǎn)：
- 這里方法接受兩個(gè)位置參數(shù)，index插入位置和value插入值
- 依舊創(chuàng)建新節(jié)點(diǎn)對(duì)象
- 判斷是否為空
- 在鏈表不為空的條件下：
  - 首先定義一個(gè)變量表示當(dāng)前節(jié)點(diǎn)，以及一個(gè)index索引比較數(shù)i
  - 使用while循環(huán)，索引比較數(shù)i != index時(shí)，更新當(dāng)前節(jié)點(diǎn)
  - 找到索引位置節(jié)點(diǎn)后，首先讓插入節(jié)點(diǎn)指向索引位置節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
  - 然后讓索引位置節(jié)點(diǎn)指向插入節(jié)點(diǎn)
  - 鏈表長(zhǎng)度+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é)點(diǎn)：

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

def iter_node(self):
  cur_node = self.head.next	#當(dāng)前節(jié)點(diǎn)
  while cur_node.next != None:	# 對(duì)除最后一個(gè)節(jié)點(diǎn)進(jìn)行可迭代化處理
    yield cur_node
    cur_node = curnode.next
  if cur_node.next == None:	# 對(duì)尾節(jié)點(diǎn)進(jìn)行可迭代化處理
    yield cur_node

重寫特殊方法–iter–，用來(lái)聲明這個(gè)類是一個(gè)迭代器

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

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

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

完整代碼：

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


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

  def __len__(self):
    return self.length

  def __iter__(self): # 遍歷列表節(jié)點(diǎn)
    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é)點(diǎn)存儲(chǔ)到tmp_head
      self.head.next = node # 新head指針指向node
      node.next = tmp_head # 新插入節(jié)點(diǎn)指向原頭指針節(jié)點(diǎn)
    self.length += 1

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

  def append(self, value):  # 鏈表尾部添加結(jié)點(diǎn)
    # 創(chuàng)建新插入的結(jié)點(diǎn)對(duì)象
    node = Node(value)
    if self.length == 0:
      self.head.next = node  # 只有一個(gè)節(jié)點(diǎn)，指針指向自己
    else:
      curnode = self.head.next  # 變量curnode存放指針
      while curnode.next != None:
        curnode = curnode.next
      curnode.next = node # 當(dāng)為最后一個(gè)節(jié)點(diǎn)時(shí)，指針指向新插入節(jié)點(diǎn)
    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é)點(diǎn)值等于index，則插入到nd后
          tmp_node = nd.next # 將nd的指針存放到中間變量
          nd.next = node # nd節(jié)點(diǎn)指向插入節(jié)點(diǎn)
          node.next = tmp_node  # 插入節(jié)點(diǎn)指向原nd.next節(jié)點(diǎn)
          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é)點(diǎn)數(shù)量(存在節(jié)點(diǎn)值相同情況)
    else:
      return False  # 替換失敗，未找到替換值

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



# 測(cè)試
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("當(dāng)前鏈表長(zhǎng)度：%s" %l.length)
#print("刪除頭結(jié)點(diǎn)為：%d"% l.head_del())
print("當(dāng)前鏈表長(zhǎng)度：%s" %l.length)
i = 1
#l.delete_node(7)
for node in l:
  print("第%d個(gè)鏈表節(jié)點(diǎn)的值: %d"%(i, node))
  i += 1

運(yùn)行結(jié)果：

當(dāng)前鏈表長(zhǎng)度：7
當(dāng)前鏈表長(zhǎng)度：7
第1個(gè)鏈表節(jié)點(diǎn)的值: 3
第2個(gè)鏈表節(jié)點(diǎn)的值: 1
第3個(gè)鏈表節(jié)點(diǎn)的值: 2
第4個(gè)鏈表節(jié)點(diǎn)的值: 7
第5個(gè)鏈表節(jié)點(diǎn)的值: 5
第6個(gè)鏈表節(jié)點(diǎn)的值: 6
第7個(gè)鏈表節(jié)點(diǎn)的值: 7