欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

基于python實(shí)現(xiàn)雙向鏈表

 更新時間:2022年05月25日 13:02:16   作者:旺旺小小超  
這篇文章主要為大家詳細(xì)介紹了基于python實(shí)現(xiàn)雙向鏈表,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

在一些面試或者力扣題中都要求用雙向鏈表來實(shí)現(xiàn),下面是基于python的雙向鏈表實(shí)現(xiàn)。

一、構(gòu)建鏈表節(jié)點(diǎn)

class Node:

? ? def __init__(self, key, value):
? ? ? ? """
? ? ? ? 初始化方法
? ? ? ? :param key:
? ? ? ? :param value:
? ? ? ? """
? ? ? ? self.key = key
? ? ? ? self.value = value
? ? ? ? self.prev = None
? ? ? ? self.next = None

? ? def __str__(self):
? ? ? ? val = '{%s: %s}' % (self.key, self.value)
? ? ? ? return val

? ? def __repr__(self):
? ? ? ? val = '{%s: %s}' % (self.key, self.value)
? ? ? ? return val

除了一些節(jié)點(diǎn)的基礎(chǔ)屬性外還有__str__方法用于自定義print(node)的字符串描述(類似Java的toString()),__repr__用于自定義直接調(diào)用Node類時的字符串描述

二、實(shí)現(xiàn)鏈表類

具體邏輯主要包括頭部添加、尾部添加、頭部刪除、尾部刪除和任意節(jié)點(diǎn)的刪除,所有對雙向鏈表的操作都是基于這幾個方法實(shí)現(xiàn)的,具體流程都寫在注釋中了

class DoubleLinkedList:

? ? def __init__(self, capacity=0xffffffff):
? ? ? ? """
? ? ? ? 雙向鏈表
? ? ? ? :param capacity: 鏈表容量 初始化為int的最大值2^32-1
? ? ? ? :return:
? ? ? ? """
? ? ? ? self.capacity = capacity
? ? ? ? self.size = 0
? ? ? ? self.head = None
? ? ? ? self.tail = None

? ? def __add_head(self, node):
? ? ? ? """
? ? ? ? 向鏈表頭部添加節(jié)點(diǎn)
? ? ? ? ? ? 頭部節(jié)點(diǎn)不存在 新添加節(jié)點(diǎn)為頭部和尾部節(jié)點(diǎn)
? ? ? ? ? ? 頭部節(jié)點(diǎn)已存在 新添加的節(jié)點(diǎn)為新的頭部節(jié)點(diǎn)
? ? ? ? :param node: 要添加的節(jié)點(diǎn)
? ? ? ? :return: 已添加的節(jié)點(diǎn)
? ? ? ? """
? ? ? ? # 頭部節(jié)點(diǎn)為空
? ? ? ? if not self.head:
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.tail = node
? ? ? ? ? ? self.head.next = None
? ? ? ? ? ? self.tail.prev = None
? ? ? ? # 頭部節(jié)點(diǎn)不為空
? ? ? ? else:
? ? ? ? ? ? node.next = self.head
? ? ? ? ? ? self.head.prev = node
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.head.prev = None
? ? ? ? self.size += 1

? ? ? ? return node

? ? def __add_tail(self, node):
? ? ? ? """
? ? ? ? 向鏈表尾部添加節(jié)點(diǎn)
? ? ? ? ? ? 尾部節(jié)點(diǎn)不存在 新添加的節(jié)點(diǎn)為頭部和尾部節(jié)點(diǎn)
? ? ? ? ? ? 尾部節(jié)點(diǎn)已存在 新添加的節(jié)點(diǎn)為新的尾部節(jié)點(diǎn)
? ? ? ? :param node: 添加的節(jié)點(diǎn)
? ? ? ? :return: 已添加的節(jié)點(diǎn)
? ? ? ? """
? ? ? ? # 尾部節(jié)點(diǎn)為空
? ? ? ? if not self.tail:
? ? ? ? ? ? self.tail = node
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.head.next = None
? ? ? ? ? ? self.tail.prev = None
? ? ? ? # 尾部節(jié)點(diǎn)不為空
? ? ? ? else:
? ? ? ? ? ? node.prev = self.tail
? ? ? ? ? ? self.tail.next = node
? ? ? ? ? ? self.tail = node
? ? ? ? ? ? self.tail.next = None
? ? ? ? self.size += 1

? ? ? ? return node

? ? def __remove_head(self):
? ? ? ? """
? ? ? ? 刪除頭部節(jié)點(diǎn)
? ? ? ? ? ? 頭部節(jié)點(diǎn)不存在 返回None
? ? ? ? ? ? 頭部節(jié)點(diǎn)已存在 判斷鏈表節(jié)點(diǎn)數(shù)量 刪除頭部節(jié)點(diǎn)
? ? ? ? :return: 頭部節(jié)點(diǎn)
? ? ? ? """
? ? ? ? # 頭部節(jié)點(diǎn)不存在
? ? ? ? if not self.head:
? ? ? ? ? ? return None

? ? ? ? # 鏈表至少存在兩個節(jié)點(diǎn)
? ? ? ? head = self.head
? ? ? ? if head.next:
? ? ? ? ? ? head.next.prev = None
? ? ? ? ? ? self.head = head.next
? ? ? ? # 只存在頭部節(jié)點(diǎn)
? ? ? ? else:
? ? ? ? ? ? self.head = self.tail = None
? ? ? ? self.size -= 1

? ? ? ? return head

? ? def __remove_tail(self):
? ? ? ? """
? ? ? ? 刪除尾部節(jié)點(diǎn)
? ? ? ? ? ? 尾部節(jié)點(diǎn)不存在 返回None
? ? ? ? ? ? 尾部節(jié)點(diǎn)已存在 判斷鏈表節(jié)點(diǎn)數(shù)量 刪除尾部節(jié)點(diǎn)
? ? ? ? :return: 尾部節(jié)點(diǎn)
? ? ? ? """
? ? ? ? # 尾部節(jié)點(diǎn)不存在
? ? ? ? if not self.tail:
? ? ? ? ? ? return None

? ? ? ? # 鏈表至少存在兩個節(jié)點(diǎn)
? ? ? ? tail = self.tail
? ? ? ? if tail.prev:
? ? ? ? ? ? tail.prev.next = None
? ? ? ? ? ? self.tail = tail.prev
? ? ? ? # 只存在尾部節(jié)點(diǎn)
? ? ? ? else:
? ? ? ? ? ? self.head = self.tail = None
? ? ? ? self.size -= 1

? ? ? ? return tail

? ? def __remove(self, node):
? ? ? ? """
? ? ? ? 刪除任意節(jié)點(diǎn)
? ? ? ? ? ? 被刪除的節(jié)點(diǎn)不存在 默認(rèn)刪除尾部節(jié)點(diǎn)
? ? ? ? ? ? 刪除頭部節(jié)點(diǎn)
? ? ? ? ? ? 刪除尾部節(jié)點(diǎn)
? ? ? ? ? ? 刪除其他節(jié)點(diǎn)
? ? ? ? :param node: 被刪除的節(jié)點(diǎn)
? ? ? ? :return: 被刪除的節(jié)點(diǎn)
? ? ? ? """
? ? ? ? # 被刪除的節(jié)點(diǎn)不存在
? ? ? ? if not node:
? ? ? ? ? ? node = self.tail

? ? ? ? # 刪除的是頭部節(jié)點(diǎn)
? ? ? ? if node == self.head:
? ? ? ? ? ? self.__remove_head()
? ? ? ? # 刪除的是尾部節(jié)點(diǎn)
? ? ? ? elif node == self.tail:
? ? ? ? ? ? self.__remove_tail()
? ? ? ? # 刪除的既不是頭部也不是尾部節(jié)點(diǎn)
? ? ? ? else:
? ? ? ? ? ? node.next.prev = node.prev
? ? ? ? ? ? node.prev.next = node.next
? ? ? ? ? ? self.size -= 1

? ? ? ? return node

? ? def pop(self):
? ? ? ? """
? ? ? ? 彈出頭部節(jié)點(diǎn)
? ? ? ? :return: 頭部節(jié)點(diǎn)
? ? ? ? """
? ? ? ? return self.__remove_head()

? ? def append(self, node):
? ? ? ? """
? ? ? ? 添加尾部節(jié)點(diǎn)
? ? ? ? :param node: 待追加的節(jié)點(diǎn)
? ? ? ? :return: 尾部節(jié)點(diǎn)
? ? ? ? """
? ? ? ? return self.__add_tail(node)

? ? def append_front(self, node):
? ? ? ? """
? ? ? ? 添加頭部節(jié)點(diǎn)
? ? ? ? :param node: 待添加的節(jié)點(diǎn)
? ? ? ? :return: 已添加的節(jié)點(diǎn)
? ? ? ? """
? ? ? ? return self.__add_head(node)

? ? def remove(self, node=None):
? ? ? ? """
? ? ? ? 刪除任意節(jié)點(diǎn)
? ? ? ? :param node: 待刪除的節(jié)點(diǎn)
? ? ? ? :return: 已刪除的節(jié)點(diǎn)
? ? ? ? """
? ? ? ? return self.__remove(node)

? ? def print(self):
? ? ? ? """
? ? ? ? 打印當(dāng)前鏈表
? ? ? ? :return:
? ? ? ? """
? ? ? ? node = self.head
? ? ? ? line = ''
? ? ? ? while node:
? ? ? ? ? ? line += '%s' % node
? ? ? ? ? ? node = node.next
? ? ? ? ? ? if node:
? ? ? ? ? ? ? ? line += '=>'
? ? ? ? print(line)

三、測試邏輯

if __name__ == '__main__':
? ? double_linked_list = DoubleLinkedList(10)
? ? nodes = []
? ? # 構(gòu)建十個節(jié)點(diǎn)的雙向列表
? ? for i in range(10):
? ? ? ? node_item = Node(i, i)
? ? ? ? nodes.append(node_item)

? ? double_linked_list.append(nodes[0])
? ? double_linked_list.print()
? ? double_linked_list.append(nodes[1])
? ? double_linked_list.print()
? ? double_linked_list.pop()
? ? double_linked_list.print()
? ? double_linked_list.append_front(nodes[2])
? ? double_linked_list.print()
? ? double_linked_list.append(nodes[3])
? ? double_linked_list.print()
? ? double_linked_list.remove(nodes[3])
? ? double_linked_list.print()
? ? double_linked_list.remove()
? ? double_linked_list.print()

測試結(jié)果:

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

相關(guān)文章

  • python爬蟲實(shí)戰(zhàn)之最簡單的網(wǎng)頁爬蟲教程

    python爬蟲實(shí)戰(zhàn)之最簡單的網(wǎng)頁爬蟲教程

    在我們?nèi)粘I暇W(wǎng)瀏覽網(wǎng)頁的時候,經(jīng)常會看到一些好看的圖片,我們就希望把這些圖片保存下載,或者用戶用來做桌面壁紙,或者用來做設(shè)計(jì)的素材。下面這篇文章就來給大家介紹了關(guān)于利用python實(shí)現(xiàn)最簡單的網(wǎng)頁爬蟲的相關(guān)資料,需要的朋友可以參考借鑒,下面來一起看看吧。
    2017-08-08
  • Django項(xiàng)目創(chuàng)建及管理實(shí)現(xiàn)流程詳解

    Django項(xiàng)目創(chuàng)建及管理實(shí)現(xiàn)流程詳解

    這篇文章主要介紹了Django項(xiàng)目創(chuàng)建及管理實(shí)現(xiàn)流程詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-10-10
  • 在python中實(shí)現(xiàn)導(dǎo)入一個需要傳參的模塊

    在python中實(shí)現(xiàn)導(dǎo)入一個需要傳參的模塊

    這篇文章主要介紹了在python中實(shí)現(xiàn)導(dǎo)入一個需要傳參的模塊,具有很好的參考價(jià)值,希望可以給大家一個參考,以后在遇到這種的情況的時候,知道如何應(yīng)對
    2021-05-05
  • python中__set_name__的具體使用

    python中__set_name__的具體使用

    在Python中,我們可以通過__set_name__方法來實(shí)現(xiàn)一些特殊的操作,本文主要介紹如何在Python中實(shí)現(xiàn)__set_name__方法,并且給出一些實(shí)際應(yīng)用的示例,感興趣的可以了解一下
    2024-01-01
  • Python運(yùn)行時修改業(yè)務(wù)SQL代碼

    Python運(yùn)行時修改業(yè)務(wù)SQL代碼

    這篇文章主要介紹了Python運(yùn)行時修改業(yè)務(wù)SQL代碼,文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的小伙伴可以參考一下
    2022-06-06
  • Python中的self用法詳解

    Python中的self用法詳解

    在本篇文章里小編給大家整理的是關(guān)于Python中的self用法以及實(shí)例內(nèi)容,需要的朋友們參考下。
    2019-08-08
  • 淺談Python用QQ郵箱發(fā)送郵件時授權(quán)碼的問題

    淺談Python用QQ郵箱發(fā)送郵件時授權(quán)碼的問題

    下面小編就為大家分享一篇淺談Python用QQ郵箱發(fā)送郵件時授權(quán)碼的問題,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-01-01
  • Python 動態(tài)導(dǎo)入對象,importlib.import_module()的使用方法

    Python 動態(tài)導(dǎo)入對象,importlib.import_module()的使用方法

    今天小編就為大家分享一篇Python 動態(tài)導(dǎo)入對象,importlib.import_module()的使用方法,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-08-08
  • python打印文件的前幾行或最后幾行教程

    python打印文件的前幾行或最后幾行教程

    今天小編就為大家分享一篇python打印文件的前幾行或最后幾行教程,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-02-02
  • Python網(wǎng)絡(luò)爬蟲之獲取網(wǎng)絡(luò)數(shù)據(jù)

    Python網(wǎng)絡(luò)爬蟲之獲取網(wǎng)絡(luò)數(shù)據(jù)

    本文介紹了Python中用于獲取網(wǎng)絡(luò)數(shù)據(jù)的重要工具之一——Requests庫,詳細(xì)講解了Requests庫的基本使用方法、請求方法、請求頭、請求參數(shù)、Cookies、Session等內(nèi)容,并結(jié)合實(shí)例代碼展示了Requests庫的應(yīng)用場景
    2023-04-04

最新評論