python實現(xiàn)雙鏈表

更新時間：2022年05月25日 08:16:38 作者：我的加奈

這篇文章主要為大家詳細介紹了python實現(xiàn)雙鏈表，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了python實現(xiàn)雙鏈表的具體代碼，供大家參考，具體內(nèi)容如下

實現(xiàn)雙鏈表需要注意的地方

1、如何插入元素，考慮特殊情況：頭節(jié)點位置，尾節(jié)點位置；一般情況：中間位置
2、如何刪除元素，考慮特殊情況：頭結點位置，尾節(jié)點位置；一般情況：中間位置

代碼實現(xiàn)

1.構造節(jié)點的類和鏈表類

class Node:
? ? def __init__(self, data):
? ? ? ? self.data = data
? ? ? ? self.next = None
? ? ? ? self.previous = None


class DoubleLinkList:
? ? '''雙鏈表'''

? ? def __init__(self, node=None):
? ? ? ? self._head = node

以下方法均在鏈表類中實現(xiàn)

2. 判斷鏈表是否為空

def is_empty(self):
? ? ? ? return self._head is None

3. 輸出鏈表的長度

def length(self):
? ? ? ? count = 0
? ? ? ? if self.is_empty():
? ? ? ? ? ? return count
? ? ? ? else:
? ? ? ? ? ? current = self._head
? ? ? ? ? ? while current is not None:
? ? ? ? ? ? ? ? count += 1
? ? ? ? ? ? ? ? current = current.next
? ? ? ? return count

4. 遍歷鏈表

def travel(self):
? ? ? ? current = self._head
? ? ? ? while current is not None:
? ? ? ? ? ? print("{0}".format(current.data), end=" ")
? ? ? ? ? ? current = current.next
? ? ? ? print("")

5.頭插法增加新元素

def add(self, item):
? ? ? ? node = Node(item)

? ? ? ? # 如果鏈表為空，讓頭指針指向當前節(jié)點
? ? ? ? if self.is_empty():
? ? ? ? ? ? self._head = node

? ? ? ? # 注意插入的順序，
? ? ? ? else:
? ? ? ? ? ? node.next = self._head
? ? ? ? ? ? self._head.previous = node
? ? ? ? ? ? self._head = node

6. 尾插法增加新元素

def append(self, item):
? ? ? ? node = Node(item)

? ? ? ? # 如果鏈表為空，則直接讓頭指針指向該節(jié)點
? ? ? ? if self.is_empty():
? ? ? ? ? ? self._head = node

? ? ? ? # 需要找到尾節(jié)點，然后讓尾節(jié)點的與新的節(jié)點進行連接
? ? ? ? else:
? ? ? ? ? ? current = self._head
? ? ? ? ? ? while current.next is not None:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? current.next = node
? ? ? ? ? ? node.previous = current

7. 查找元素是否存在鏈表中

def search(self, item):
? ? ? ? current = self._head
? ? ? ? found = False
? ? ? ? while current is not None and not found:
? ? ? ? ? ? if current.data == item:
? ? ? ? ? ? ? ? found = True
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? return found

8. 在某個位置中插入元素

def insert(self, item, pos):

? ? ? ? # 特殊位置，在第一個位置的時候，頭插法
? ? ? ? if pos <= 0:
? ? ? ? ? ? self.add(item)

? ? ? ? # 在尾部的時候，使用尾插法
? ? ? ? elif pos > self.length() - 1:
? ? ? ? ? ? self.append(item)

? ? ? ? # 中間位置
? ? ? ? else:
? ? ? ? ? ? node = Node(item)
? ? ? ? ? ? current = self._head
? ? ? ? ? ? count = 0
? ? ? ? ? ? while count < pos - 1:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? ? ? count += 1

? ? ? ? ? ? # 找到了要插入位置的前驅之后，進行如下操作
? ? ? ? ? ? node.previous = current
? ? ? ? ? ? node.next = current.next
? ? ? ? ? ? current.next.previous = node
? ? ? ? ? ? current.next = node

?# 換一個順序也可以進行
def insert2(self, item, pos):
? ? ? ? if pos <= 0:
? ? ? ? ? ? self.add(item)
? ? ? ? elif pos > self.length() - 1:
? ? ? ? ? ? self.append(item)
? ? ? ? else:
? ? ? ? ? ? node = Node(item)
? ? ? ? ? ? current = self._head
? ? ? ? ? ? count = 0
? ? ? ? ? ? while count < pos:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? ? ? count += 1

? ? ? ? ? ? node.next = current
? ? ? ? ? ? node.previous = current.previous
? ? ? ? ? ? current.previous.next = node
? ? ? ? ? ? current.previous = node

9. 刪除元素

def remove(self, item):
? ? ? ? current = self._head
? ? ? ? if self.is_empty():
? ? ? ? ? ? return
? ? ? ? elif current.data == item:
? ? ? ? ? ? # 第一個節(jié)點就是目標節(jié)點，那么需要將下一個節(jié)點的前驅改為None 然后再將head指向下一個節(jié)點
? ? ? ? ? ? current.next.previous = None
? ? ? ? ? ? self._head = current.next
? ? ? ? else:

? ? ? ? ? ? # 找到要刪除的元素節(jié)點
? ? ? ? ? ? while current is not None and current.data != item:
? ? ? ? ? ? ? ? current = current.next
? ? ? ? ? ? if current is None:
? ? ? ? ? ? ? ? print("not found {0}".format(item))

? ? ? ? ? ? # 如果尾節(jié)點是目標節(jié)點，讓前驅節(jié)點指向None
? ? ? ? ? ? elif current.next is None:
? ? ? ? ? ? ? ? current.previous.next = None

? ? ? ? ? ? # 中間位置，因為是雙鏈表，可以用前驅指針操作
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? current.previous.next = current.next
? ? ? ? ? ? ? ? current.next.previous = current.previous

# 第二種寫法
? ? def remove2(self, item):
? ? ? ? """刪除元素"""
? ? ? ? if self.is_empty():
? ? ? ? ? ? return
? ? ? ? else:
? ? ? ? ? ? cur = self._head
? ? ? ? ? ? if cur.data == item:
? ? ? ? ? ? ? ? # 如果首節(jié)點的元素即是要刪除的元素
? ? ? ? ? ? ? ? if cur.next is None:
? ? ? ? ? ? ? ? ? ? # 如果鏈表只有這一個節(jié)點
? ? ? ? ? ? ? ? ? ? self._head = None
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? # 將第二個節(jié)點的prev設置為None
? ? ? ? ? ? ? ? ? ? cur.next.prev = None
? ? ? ? ? ? ? ? ? ? # 將_head指向第二個節(jié)點
? ? ? ? ? ? ? ? ? ? self._head = cur.next
? ? ? ? ? ? ? ? return
? ? ? ? ? ? while cur is not None:
? ? ? ? ? ? ? ? if cur.data == item:
? ? ? ? ? ? ? ? ? ? # 將cur的前一個節(jié)點的next指向cur的后一個節(jié)點
? ? ? ? ? ? ? ? ? ? cur.prev.next = cur.next
? ? ? ? ? ? ? ? ? ? # 將cur的后一個節(jié)點的prev指向cur的前一個節(jié)點
? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev
? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? cur = cur.next

10. 演示

my_list = DoubleLinkList()


print("add操作")
my_list.add(98)
my_list.add(99)
my_list.add(100)
my_list.travel()
print("{:#^50}".format(""))

print("append操作")
my_list.append(86)
my_list.append(85)
my_list.append(88)
my_list.travel()
print("{:#^50}".format(""))

print("insert2操作")
my_list.insert2(66, 3)
my_list.insert2(77, 0)
my_list.insert2(55, 10)
my_list.travel()
print("{:#^50}".format(""))


print("insert操作")
my_list.insert(90, 4)
my_list.insert(123, 5)
my_list.travel()
print("{:#^50}".format(""))

print("search操作")
print(my_list.search(100))
print(my_list.search(1998))
print("{:#^50}".format(""))

print("remove操作")
my_list.remove(56)
my_list.remove(123)
my_list.remove(77)
my_list.remove(55)
my_list.travel()
print("{:#^50}".format(""))

print("remove2操作")
my_list.travel()
my_list.remove2(100)
my_list.remove2(99)
my_list.remove2(98)
my_list.travel()

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

python編寫簡單爬蟲資料匯總
本文給大家匯總介紹了下幾種使用Python編寫簡單爬蟲的方法和代碼，非常的不錯，這里分享給大家，希望大家能夠喜歡。
2016-03-03
Python3.9又更新了:dict內(nèi)置新功能
這篇文章主要介紹了Python3.9又更新了:dict內(nèi)置新功能，從文檔中，我們可以看到官方透露的對 dict、math 等組件增加的新特性，以及下一步的開發(fā)進展
2020-02-02
python自動發(fā)微信監(jiān)控報警
這篇文章主要為大家詳細介紹了python自動發(fā)微信監(jiān)控報警，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2019-09-09
python通過apply使用元祖和列表調用函數(shù)實例
這篇文章主要介紹了python通過apply使用元祖和列表調用函數(shù),實例分析了python中apply方法的使用技巧,需要的朋友可以參考下
2015-05-05
Python+wxPython實現(xiàn)文件名批量處理
在日常的文件管理中,我們經(jīng)常需要對文件進行批量處理以符合特定的命名規(guī)則或需求,本文主要介紹了如何使用wxPython進行文件夾中文件名的批量處理,需要的可以參考下
2024-04-04
python機器學習實戰(zhàn)之最近鄰kNN分類器
這篇文章主要介紹了python機器學習實戰(zhàn)之最近鄰kNN分類器，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2017-12-12
Python人臉檢測實戰(zhàn)之疲勞檢測
本文主要介紹了實現(xiàn)疲勞檢測：如果眼睛已經(jīng)閉上了一段時間，我們會認為他們開始打瞌睡并發(fā)出警報來喚醒他們并引起他們的注意。感興趣的朋友可以了解一下
2021-12-12
Python3解決棋盤覆蓋問題的方法示例
這篇文章主要介紹了Python3解決棋盤覆蓋問題的方法,簡單描述了棋盤覆蓋問題的概念、原理及Python相關操作技巧,需要的朋友可以參考下
2017-12-12
Python基于wxPython和FFmpeg開發(fā)一個視頻標簽工具
在當今數(shù)字媒體時代,視頻內(nèi)容的管理和標記變得越來越重要,無論是研究人員需要對實驗視頻進行時間點標記,還是個人用戶希望對家庭視頻進行分類整理,一個高效的視頻標簽工具都是不可或缺的,本文將詳細分析一個基于Python、wxPython和FFmpeg開發(fā)的視頻標簽工具
2025-04-04
pycharm 設置項目的根目錄教程
今天小編就為大家分享一篇pycharm 設置項目的根目錄教程，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2020-02-02