小編精選 - 技術文章翻譯 · 11月15日

【Python 🐍精通】Python Linked List 及基本 Linked List 操作🛠️

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

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

Python 的 Magic/Dunder 方法：Python 中的 Magic 或 Dunder（雙底線）方法是名稱以雙底線開頭和結尾的特殊方法（例如，__init__、__str__、__repr__）。

今天，我們將對其進行擴展，並使用物件導向程式設計的知識來理解和建立 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 中的鍊錶

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

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

動態大小：與陣列不同，鍊錶可以動態增長或縮小大小，這對於記憶體使用來說是高效的。
易於插入/刪除：插入或刪除節點相對簡單，因為它通常只涉及更改一些引用，而不需要像陣列中那樣移動元素。
靈活性：它們可以實現其他資料結構，如堆疊、佇列和圖鄰接表。

運營	時間複雜度
存取	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)

這段程式碼做了兩件事：

追加：在鍊錶末端追加一個節點。
__repr__ ：此方法遍歷鍊錶並以Pythonic方式列印它。
這也可以使用稱為 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

刪除連結清單中的節點