Python の単一リンクリストの実装

Python で単一リンクリストを実装する方法を学びます。動的なメモリ割り当て、ノード操作、挿入、トラバーサル、削除を調べます。

エディターで試してみる

概要

リンクリストは、要素が連続したメモリ位置に格納されない線形データ構造です。代わりに、各要素 (ノードと呼ばれます) は、シーケンス内の次のノードへの参照を含む個別のオブジェクトです。

従来の配列に対するリンクリストの主な利点は、動的サイジングと、最初に定数 O(1) 時間で要素を挿入または削除できることです。ただし、インデックスによって要素にアクセスするには線形トラバースが必要であり、O(n) 時間がかかります。

Python では、データと参照ポインターを格納する Node クラスと、ヘッドノード、先頭または末尾での挿入、および削除を管理する LinkedList クラスを定義することによって、リンクリストを実装します。

コードと実行の出力

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

段階的な実装

テキストエディタに元に戻す/やり直し機能を実装する
グラフ、スタック、キューなどの複雑なデータ構造の構築
検索アクションよりも挿入と削除の頻度が多いリストの管理

よくある質問

単一リンクリストと二重リンクリストの違いは何ですか?

単一リンクリストでは、各ノードは次のノードのみを指します。二重リンクリストでは、各ノードに次のノードと前のノードの両方への参照が含まれるため、追加のメモリを消費して双方向のトラバーサルが可能になります。

Python には組み込みの LinkedList クラスがないのはなぜですか?

Python の配列 (リスト) は動的配列として実装されます。 Python のメモリ管理とCPythonの最適化により、標準リストはほとんどのタスクで非常に高速かつ効率的であるため、組み込みのリンクリストの実際の必要性が減ります。