Python Singly Linked List Implementation

了解如何在 Python 中實作單鍊錶。探索動態記憶體分配、節點操作、插入、遍歷和刪除。

概述

A linked list is a linear data structure where elements are not stored in contiguous memory locations.相反，每个元素（称为节点）都是一个单独的对象，其中包含对序列中下一个节点的引用。

The primary benefit of a linked list over a traditional array is its dynamic sizing and the ability to insert or delete elements in constant O(1) time at the beginning.然而，通过索引访问元素需要线性遍历，这需要 O(n) 时间。

In Python, we implement a linked list by defining a Node class to store the data and reference pointer, and a LinkedList class to manage the head node, insertions at the head or tail, and deletions.

程式碼和執行輸出

Python 中的單鍊錶實現，展示節點建立、追加和列表遍歷。

linked_list.py

在編輯器中嘗試

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

class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        
    def delete(self, key):
        curr = self.head
        if curr and curr.data == key:
            self.head = curr.next
            curr = None
            return
        prev = None
        while curr and curr.data != key:
            prev = curr
            curr = curr.next
        if not curr:
            return
        prev.next = curr.next
        curr = None
        
    def display(self):
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements) + " -> None")

# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()

print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()

端子輸出

Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> None

逐步實施

Implementing undo-redo functionality in text editors
建構複雜的資料結構，例如圖、堆疊和佇列
管理插入和刪除頻率超過查找操作的列表

常見問題解答

單鍊錶和雙鍊錶有什麼差別？

在單向鍊錶中，每個節點僅指向下一個節點。 In a Doubly Linked List, each node contains references to both the next and the previous node, allowing bidirectional traversal at the cost of extra memory.

為什麼Python沒有內建的LinkedList類別？

Python 數組（列表）被實作為動態數組。 Because of Python's memory management andCPythonoptimizations, standard lists are extremely fast and efficient for most tasks, reducing the practical need for a built-in linked list.