在上一篇文章中,我們了解了物件導向程式設計並對 Python 的 Magic/Dunder 方法進行了全面概述。

Python 中的物件導向程式設計 (OOP):Python 中的這種範例圍繞著建立可重複使用程式碼。它涉及使用類別作為物件的藍圖。這些物件可以具有定義其行為和交互的屬性(資料)和方法(函數)。

Python 的 Magic/Dunder 方法:Python 中的 Magic 或 Dunder(雙底線)方法是名稱以雙底線開頭和結尾的特殊方法(例如,__init__、__str__、__repr__)。

您可以在這裡閱讀相關內容。 👇

https://dev.to/swirl/python-mastery-pythons-object-oriented-programming-overview-and-fundamentals-22m1

今天,我們將對其進行擴展,並使用物件導向程式設計的知識來理解和建立 Python 中的鍊錶。並會對其執行一些操作。

開源 Python 專案:Swirl

旋流搜尋

如果您對 Python 感興趣,您將會💖 Swirl。 Swirl 是一個開源搜尋平台,它將為您提供以下知識:

  • Python

  • 人工智慧

  • 在任何產品中整合大型語言模型

  • 了解如何開發搜尋平台。

檢查我們的 GitHub 儲存庫:

https://github.com/swirlai/swirl-search

如果您能夠:我們將非常高興:

https://github.com/swirlai/swirl-search

Linked List

連結列表是物件有序的集合。它是一種資料結構,旨在將資料保存在不連續的記憶體區塊中。

與使用連續記憶體區塊的陣列或傳統列表不同,鍊錶儲存在非連續記憶體位置。這種設計允許高效的插入和刪除,而無需重新排列整個資料結構。

這種設計允許高效的插入和刪除,而不需要重新排列整個資料結構。

基本鍊錶

基本鍊錶是一種線性資料結構,其中每個元素(稱為節點)包含兩部分:資料和對清單中下一個節點的引用。這種結構允許有效地插入和刪除元素,因為它不需要移動元素,這與陣列不同。

典型的節點設計:

資料:包含資料,可以是數字、地址、文字等。

Next:指向下一個資料節點或儲存下一個資料節點的位址。

Python 中鍊錶的節點

第一個節點稱為列表的頭,最後一個節點指向 None(在 Python 中)(或在其他語言中為 Null),稱為尾節點。

當你把很多節點收集在一起時,它就變成了一個鍊錶。

Python 中的鍊錶

鍊錶的好處和操作的時間複雜度

連結清單有很多好處,特別是在動態資料操作場景中。以下是一些主要優勢:

  1. 動態大小:與陣列不同,鍊錶可以動態增長或縮小大小,這對於記憶體使用來說是高效的。

  2. 易於插入/刪除:插入或刪除節點相對簡單,因為它通常只涉及更改一些引用,而不需要像陣列中那樣移動元素。

  3. 靈活性:它們可以實現其他資料結構,如堆疊、佇列和圖鄰接表。

運營 時間複雜度
存取 O(n)
搜尋 O(n)
插入 O(1) O(1)
刪除 O(1) O(1)

注意:我們考慮的是單鍊錶。

在 Python 中實作鍊錶。

這是將在 Python 中建立節點的程式碼。如果您對 __repr__ 方法感到困惑,請注意。請查看本系列中的上一篇文章。

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

    def __repr__(self):
        return f"Node({self.data})"

連結列表類別的程式碼。這利用了 Node 類別來建立資料並將它們連接在一起。

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def __repr__(self):
        nodes = []
        current = self.head
        while current:
            nodes.append(repr(current))
            current = current.next
        return "->".join(nodes)

這段程式碼做了兩件事:

  1. 追加:在鍊錶末端追加一個節點。

  2. __repr__ :此方法遍歷鍊錶並以Pythonic方式列印它。

  3. 這也可以使用稱為 traverse 的方法來完成。

_這是呼叫「repr」方法的「print(llist)」的輸出:

在 Python 中列印連結清單

遍歷鍊錶。

遍歷鍊錶就是遍歷每個節點並列印它的過程。

def traverse(linked_list):
    current = linked_list.head
    while current:
        print(current.data)
        current = current.next

llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)

print("Traversing the linked list:")
traverse(llist)

Python中遍歷鍊錶

反轉鍊錶

這個想法是迭代鍊錶,並且對於每個節點,將其“下一個”指標切換為指向前一個節點而不是下一個節點。這將幫助我們反轉鍊錶。

def reverse_linked_list(head):
    previous = None
    current = head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    return previous

llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
print("Original List:", llist)

new_head = reverse_linked_list(llist.head)
llist.head = new_head
print("Reversed List:", llist)

反轉連結清單

在連結清單中插入值

我們已經有一個追加函數,可以將值加到鍊錶的末尾。但是,如果我們想要一個在特定位置加入的方法,並且如果該位置不存在,則將值附加到末尾,該怎麼辦?

class LinkedList:

    def insert_after_value(self, data_after, data_to_insert):
        if self.head is None:
            return

        current = self.head
        while current:
            if current.data == data_after:
                new_node = Node(data_to_insert)
                new_node.next = current.next
                current.next = new_node
                return
            current = current.next

        self.append(data_to_insert)

刪除鍊錶中的節點

若要從鍊錶中刪除節點,請建立一個函數,該函數將鍊錶的頭和要刪除的節點的資料作為參數。並遍歷鍊錶,直到找到資料,然後將其刪除。

class LinkedList:

    def delete_node(self, data):
        current = self.head

        if current is None or current.data == data:
            self.head = current.next if current else None
            return

        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

刪除連結清單中的節點

感謝您閱讀本文。在本系列的後續文章中,我們將討論 Python 和 Python 資料結構的更複雜的細節。

為 [Swirl] 做出貢獻(https://github.com/swirlai/swirl-search)

為 Swirl 做出貢獻

Swirl 是一個開源 Python 專案。為 Swirl 做出貢獻可以幫助您獲得生產級的 Python 知識並提高您的技能。

檢查我們的 GitHub 儲存庫:

https://github.com/swirlai/swirl-search

如果您能夠:我們將非常高興:

https://github.com/swirlai/swirl-search

謝謝閱讀,

你們都令人嘆為觀止。

你太棒了


原文出處:https://dev.to/swirl/python-mastery-overview-of-linked-list-in-python-essential-linked-list-operations-hn3


共有 0 則留言


精選技術文章翻譯,幫助開發者持續吸收新知。