python實(shí)現(xiàn)雙鏈表
本文實(shí)例為大家分享了python實(shí)現(xiàn)雙鏈表的具體代碼,供大家參考,具體內(nèi)容如下
實(shí)現(xiàn)雙鏈表需要注意的地方
1、如何插入元素,考慮特殊情況:頭節(jié)點(diǎn)位置,尾節(jié)點(diǎn)位置;一般情況:中間位置
2、如何刪除元素,考慮特殊情況:頭結(jié)點(diǎn)位置,尾節(jié)點(diǎn)位置;一般情況:中間位置
代碼實(shí)現(xiàn)
1.構(gòu)造節(jié)點(diǎn)的類和鏈表類
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
以下方法均在鏈表類中實(shí)現(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) ? ? ? ? # 如果鏈表為空,讓頭指針指向當(dāng)前節(jié)點(diǎn) ? ? ? ? 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é)點(diǎn) ? ? ? ? if self.is_empty(): ? ? ? ? ? ? self._head = node ? ? ? ? # 需要找到尾節(jié)點(diǎn),然后讓尾節(jié)點(diǎn)的與新的節(jié)點(diǎn)進(jìn)行連接 ? ? ? ? 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 ? ? ? ? ? ? # 找到了要插入位置的前驅(qū)之后,進(jìn)行如下操作 ? ? ? ? ? ? node.previous = current ? ? ? ? ? ? node.next = current.next ? ? ? ? ? ? current.next.previous = node ? ? ? ? ? ? current.next = node
?# 換一個順序也可以進(jìn)行 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é)點(diǎn)就是目標(biāo)節(jié)點(diǎn),那么需要將下一個節(jié)點(diǎn)的前驅(qū)改為None 然后再將head指向下一個節(jié)點(diǎn) ? ? ? ? ? ? current.next.previous = None ? ? ? ? ? ? self._head = current.next ? ? ? ? else: ? ? ? ? ? ? # 找到要刪除的元素節(jié)點(diǎn) ? ? ? ? ? ? while current is not None and current.data != item: ? ? ? ? ? ? ? ? current = current.next ? ? ? ? ? ? if current is None: ? ? ? ? ? ? ? ? print("not found {0}".format(item)) ? ? ? ? ? ? # 如果尾節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn),讓前驅(qū)節(jié)點(diǎn)指向None ? ? ? ? ? ? elif current.next is None: ? ? ? ? ? ? ? ? current.previous.next = None ? ? ? ? ? ? # 中間位置,因?yàn)槭请p鏈表,可以用前驅(qū)指針操作 ? ? ? ? ? ? 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é)點(diǎn)的元素即是要刪除的元素 ? ? ? ? ? ? ? ? if cur.next is None: ? ? ? ? ? ? ? ? ? ? # 如果鏈表只有這一個節(jié)點(diǎn) ? ? ? ? ? ? ? ? ? ? self._head = None ? ? ? ? ? ? ? ? else: ? ? ? ? ? ? ? ? ? ? # 將第二個節(jié)點(diǎn)的prev設(shè)置為None ? ? ? ? ? ? ? ? ? ? cur.next.prev = None ? ? ? ? ? ? ? ? ? ? # 將_head指向第二個節(jié)點(diǎn) ? ? ? ? ? ? ? ? ? ? self._head = cur.next ? ? ? ? ? ? ? ? return ? ? ? ? ? ? while cur is not None: ? ? ? ? ? ? ? ? if cur.data == item: ? ? ? ? ? ? ? ? ? ? # 將cur的前一個節(jié)點(diǎn)的next指向cur的后一個節(jié)點(diǎn) ? ? ? ? ? ? ? ? ? ? cur.prev.next = cur.next ? ? ? ? ? ? ? ? ? ? # 將cur的后一個節(jié)點(diǎn)的prev指向cur的前一個節(jié)點(diǎn) ? ? ? ? ? ? ? ? ? ? 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)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
python操作xlsx文件的包openpyxl實(shí)例
下面小編就為大家分享一篇python操作xlsx文件的包openpyxl實(shí)例,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2018-05-05Python3.9環(huán)境搭建RobotFramework的詳細(xì)過程
Robot Framework是一個基于Python的,可擴(kuò)展的關(guān)鍵字驅(qū)動的測試自動化框架,用于端到端驗(yàn)收測試和驗(yàn)收測試驅(qū)動開發(fā)(ATDD),這篇文章主要介紹了Python3.9環(huán)境搭建RobotFramework的詳細(xì)過程,需要的朋友可以參考下2023-01-01python字符串拼接.join()和拆分.split()詳解
這篇文章主要為大家介紹了python字符串拼接.join()和拆分.split(),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助2021-11-11python中判斷數(shù)字是否為質(zhì)數(shù)的實(shí)例講解
在本篇文章里小編給大家分享了關(guān)于python中判斷數(shù)字是否為質(zhì)數(shù)的實(shí)例講解內(nèi)容,有興趣的朋友們可以學(xué)習(xí)下。2020-12-12Python操作lxml庫實(shí)戰(zhàn)之Xpath篇
XPath是一門在XML文檔中查找信息的語言,下面這篇文章主要給大家介紹了關(guān)于Python操作lxml庫實(shí)戰(zhàn)之Xpath篇的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-12-12