基于python實現(xiàn)雙向鏈表
在一些面試或者力扣題中都要求用雙向鏈表來實現(xiàn),下面是基于python的雙向鏈表實現(xiàn)。
一、構建鏈表節(jié)點
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é)點的基礎屬性外還有__str__方法用于自定義print(node)的字符串描述(類似Java的toString()),__repr__用于自定義直接調用Node類時的字符串描述
二、實現(xiàn)鏈表類
具體邏輯主要包括頭部添加、尾部添加、頭部刪除、尾部刪除和任意節(jié)點的刪除,所有對雙向鏈表的操作都是基于這幾個方法實現(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é)點 ? ? ? ? ? ? 頭部節(jié)點不存在 新添加節(jié)點為頭部和尾部節(jié)點 ? ? ? ? ? ? 頭部節(jié)點已存在 新添加的節(jié)點為新的頭部節(jié)點 ? ? ? ? :param node: 要添加的節(jié)點 ? ? ? ? :return: 已添加的節(jié)點 ? ? ? ? """ ? ? ? ? # 頭部節(jié)點為空 ? ? ? ? if not self.head: ? ? ? ? ? ? self.head = node ? ? ? ? ? ? self.tail = node ? ? ? ? ? ? self.head.next = None ? ? ? ? ? ? self.tail.prev = None ? ? ? ? # 頭部節(jié)點不為空 ? ? ? ? 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é)點 ? ? ? ? ? ? 尾部節(jié)點不存在 新添加的節(jié)點為頭部和尾部節(jié)點 ? ? ? ? ? ? 尾部節(jié)點已存在 新添加的節(jié)點為新的尾部節(jié)點 ? ? ? ? :param node: 添加的節(jié)點 ? ? ? ? :return: 已添加的節(jié)點 ? ? ? ? """ ? ? ? ? # 尾部節(jié)點為空 ? ? ? ? if not self.tail: ? ? ? ? ? ? self.tail = node ? ? ? ? ? ? self.head = node ? ? ? ? ? ? self.head.next = None ? ? ? ? ? ? self.tail.prev = None ? ? ? ? # 尾部節(jié)點不為空 ? ? ? ? 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é)點 ? ? ? ? ? ? 頭部節(jié)點不存在 返回None ? ? ? ? ? ? 頭部節(jié)點已存在 判斷鏈表節(jié)點數(shù)量 刪除頭部節(jié)點 ? ? ? ? :return: 頭部節(jié)點 ? ? ? ? """ ? ? ? ? # 頭部節(jié)點不存在 ? ? ? ? if not self.head: ? ? ? ? ? ? return None ? ? ? ? # 鏈表至少存在兩個節(jié)點 ? ? ? ? head = self.head ? ? ? ? if head.next: ? ? ? ? ? ? head.next.prev = None ? ? ? ? ? ? self.head = head.next ? ? ? ? # 只存在頭部節(jié)點 ? ? ? ? else: ? ? ? ? ? ? self.head = self.tail = None ? ? ? ? self.size -= 1 ? ? ? ? return head ? ? def __remove_tail(self): ? ? ? ? """ ? ? ? ? 刪除尾部節(jié)點 ? ? ? ? ? ? 尾部節(jié)點不存在 返回None ? ? ? ? ? ? 尾部節(jié)點已存在 判斷鏈表節(jié)點數(shù)量 刪除尾部節(jié)點 ? ? ? ? :return: 尾部節(jié)點 ? ? ? ? """ ? ? ? ? # 尾部節(jié)點不存在 ? ? ? ? if not self.tail: ? ? ? ? ? ? return None ? ? ? ? # 鏈表至少存在兩個節(jié)點 ? ? ? ? tail = self.tail ? ? ? ? if tail.prev: ? ? ? ? ? ? tail.prev.next = None ? ? ? ? ? ? self.tail = tail.prev ? ? ? ? # 只存在尾部節(jié)點 ? ? ? ? else: ? ? ? ? ? ? self.head = self.tail = None ? ? ? ? self.size -= 1 ? ? ? ? return tail ? ? def __remove(self, node): ? ? ? ? """ ? ? ? ? 刪除任意節(jié)點 ? ? ? ? ? ? 被刪除的節(jié)點不存在 默認刪除尾部節(jié)點 ? ? ? ? ? ? 刪除頭部節(jié)點 ? ? ? ? ? ? 刪除尾部節(jié)點 ? ? ? ? ? ? 刪除其他節(jié)點 ? ? ? ? :param node: 被刪除的節(jié)點 ? ? ? ? :return: 被刪除的節(jié)點 ? ? ? ? """ ? ? ? ? # 被刪除的節(jié)點不存在 ? ? ? ? if not node: ? ? ? ? ? ? node = self.tail ? ? ? ? # 刪除的是頭部節(jié)點 ? ? ? ? if node == self.head: ? ? ? ? ? ? self.__remove_head() ? ? ? ? # 刪除的是尾部節(jié)點 ? ? ? ? elif node == self.tail: ? ? ? ? ? ? self.__remove_tail() ? ? ? ? # 刪除的既不是頭部也不是尾部節(jié)點 ? ? ? ? else: ? ? ? ? ? ? node.next.prev = node.prev ? ? ? ? ? ? node.prev.next = node.next ? ? ? ? ? ? self.size -= 1 ? ? ? ? return node ? ? def pop(self): ? ? ? ? """ ? ? ? ? 彈出頭部節(jié)點 ? ? ? ? :return: 頭部節(jié)點 ? ? ? ? """ ? ? ? ? return self.__remove_head() ? ? def append(self, node): ? ? ? ? """ ? ? ? ? 添加尾部節(jié)點 ? ? ? ? :param node: 待追加的節(jié)點 ? ? ? ? :return: 尾部節(jié)點 ? ? ? ? """ ? ? ? ? return self.__add_tail(node) ? ? def append_front(self, node): ? ? ? ? """ ? ? ? ? 添加頭部節(jié)點 ? ? ? ? :param node: 待添加的節(jié)點 ? ? ? ? :return: 已添加的節(jié)點 ? ? ? ? """ ? ? ? ? return self.__add_head(node) ? ? def remove(self, node=None): ? ? ? ? """ ? ? ? ? 刪除任意節(jié)點 ? ? ? ? :param node: 待刪除的節(jié)點 ? ? ? ? :return: 已刪除的節(jié)點 ? ? ? ? """ ? ? ? ? return self.__remove(node) ? ? def print(self): ? ? ? ? """ ? ? ? ? 打印當前鏈表 ? ? ? ? :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 = [] ? ? # 構建十個節(jié)點的雙向列表 ? ? 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()
測試結果:
以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關文章
python爬蟲實戰(zhàn)之最簡單的網(wǎng)頁爬蟲教程
在我們日常上網(wǎng)瀏覽網(wǎng)頁的時候,經常會看到一些好看的圖片,我們就希望把這些圖片保存下載,或者用戶用來做桌面壁紙,或者用來做設計的素材。下面這篇文章就來給大家介紹了關于利用python實現(xiàn)最簡單的網(wǎng)頁爬蟲的相關資料,需要的朋友可以參考借鑒,下面來一起看看吧。2017-08-08Django項目創(chuàng)建及管理實現(xiàn)流程詳解
這篇文章主要介紹了Django項目創(chuàng)建及管理實現(xiàn)流程詳解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-10-10Python 動態(tài)導入對象,importlib.import_module()的使用方法
今天小編就為大家分享一篇Python 動態(tài)導入對象,importlib.import_module()的使用方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-08-08Python網(wǎng)絡爬蟲之獲取網(wǎng)絡數(shù)據(jù)
本文介紹了Python中用于獲取網(wǎng)絡數(shù)據(jù)的重要工具之一——Requests庫,詳細講解了Requests庫的基本使用方法、請求方法、請求頭、請求參數(shù)、Cookies、Session等內容,并結合實例代碼展示了Requests庫的應用場景2023-04-04