Pythonの連結リスト：実例で学ぶチュートリアル

連結リストは、データの構造化と管理において重要な役割を果たすデータ構造です。メモリ上のランダムな場所に保存された一連のノードから構成され、効率的なメモリ管理を可能にします。連結リストの各ノードは、データ本体と、次のノードへの参照という2つの主要な要素を持ちます。

最初は複雑に聞こえても、心配はいりません。

連結リストとは何か、なぜ使うのか、そしてどんな利点があるのかを、基礎からわかりやすく説明します.

なぜ連結リストを使うのか？

連結リストは、以下のように、通常のリストや配列にデータを保存する際のさまざまな欠点を克服するために考案されました。

挿入と削除が容易

リストでは、末尾以外の位置に要素を挿入・削除するには、後続の要素をすべてシフトする必要があります。この処理の時間計算量は O(n) で、特にリストが大きくなるにつれてパフォーマンスが大きく低下します。リストの仕組みや実装にまだ慣れていない場合は、Pythonリストのチュートリアルをご覧ください。

一方、連結リストは異なる動きをします。要素は非連続なメモリ領域に保存され、次のノードへのポインタで連結されます。この構造により、リンクの付け替えだけで任意の位置に要素を追加・除去でき、削除対象を迂回させたり新要素を組み込んだりできます。

挿入・削除位置のノードへの直接参照があれば、操作自体は O(1) です。ただしその位置を見つけるには O(n) の走査が必要なため、O(1) の恩恵は、対象ノードへのポインタを既に持っている場合（例：リストの先頭を扱うとき）に限られます。

動的なサイズ

Python のリストは動的配列であり、サイズを柔軟に変更できます。

しかし実際には、より大きなメモリブロックへの再割り当てなど複雑な処理が伴います。この再割り当てでは要素を新しいブロックへコピーし、必要以上の領域が一時的に確保される可能性があるため非効率です。

対照的に、連結リストは再割り当てやリサイズなしに動的に拡張・縮小できます。高い柔軟性が求められるタスクに適しています。

メモリ効率

リストは要素すべてに対して連続したメモリブロックを確保します。初期サイズを超えて拡張が必要になると、新たな大きな連続メモリブロックを確保し、既存要素をすべてコピーしなければなりません。これは特に大規模なリストでは時間がかかり非効率です。逆に初期サイズを過大に見積もると、未使用メモリが無駄になります。

これに対して、連結リストは各要素ごとに個別にメモリを確保します。新しい要素の追加時に必要分だけ確保できるため、メモリの利用効率が高まります。

連結リストを使うべき場面

連結リストは、動的サイズやメモリ効率といった利点がある一方、制約もあります。各要素に次ノードへのポインタを保持する必要があるため、要素あたりのメモリ使用量は増えます。また、データへ直接アクセスすることはできません。要素にアクセスするにはリストの先頭から順にたどる必要があり、探索の時間計算量は O(n) です。

連結リストと配列の選択は、アプリケーションの要件によって異なります。連結リストが特に有用なのは次のような場合です。

• 多くの要素を頻繁に挿入・削除する必要がある
• データサイズが予測しづらく、頻繁に変化する可能性が高い
• 要素へのランダムアクセスが不要である
• データセットが大きな要素や構造体で構成される

連結リストの種類

連結リストには3つの種類があり、用途に応じて異なる利点があります。以下のとおりです。

単方向連結リスト

単方向連結リスト

単方向連結リストは最も単純な形式で、各ノードはデータと、次のノードへの参照を持ちます。走査は一方向にのみ可能で、先頭（最初のノード）から末尾（最後のノード）へ進みます。

単方向連結リストの各ノードは通常、次の2つの部分から構成されます。

• データ: ノードに格納される実際の情報。
• 次ポインタ: 次のノードへの参照。最後のノードの次ポインタは通常 null に設定されます。

このデータ構造は一方向にしか走査できないため、値やインデックスで特定の要素にアクセスするには、先頭から順に目的のノードまで移動する必要があります。この操作の時間計算量は O(n) であり、大きなリストでは非効率です。

一方で、先頭への挿入・削除は時間計算量 O(1) で非常に効率的です。ただし、中間や末尾での挿入・削除は、その位置まで走査が必要となるため O(n) になります。

この設計から、単方向連結リストは先頭付近での操作が多い場合に有用なデータ構造です。

双方向連結リスト

双方向連結リスト

単方向連結リストの欠点は、一方向にしか走査できず、必要に応じて前のノードへ戻れないことです。この制約は、双方向の移動を要する操作を困難にします。

双方向連結リストは、各ノードに追加のポインタを持たせることで、この問題を解決します。これにより、リストを前後両方向に走査できます。双方向連結リストの各ノードは、データ、次のノードへのポインタ、前のノードへのポインタの3要素を持ちます。

循環連結リスト

循環連結リスト

循環連結リストは、最後のノードが最初のノードを指す特殊な連結リストで、円環状の構造を成します。つまり、これまで見てきた単方向・双方向連結リストと異なり、循環連結リストには終端がなく、ぐるぐると回り続けます。

この循環性は、最後の要素から最初の要素へ戻る処理が必要な場面に向いています。例えば、プレイヤーを順番に回すボードゲームや、ラウンドロビン・スケジューリングなどの計算機アルゴリズムです。

時間計算量のまとめ

連結リストと Python リストの違いを一目で把握しましょう。

ポイントは次のとおりです。連結リストは先頭での挿入・削除（O(1)）では優位ですが、それ以外では不利です。データ構造の先頭で頻繁に要素を追加・削除しないのであれば、通常の Python リストのほうが適している可能性が高いでしょう。

Python で連結リストを作る方法

連結リストの概要、使う理由、バリエーションがわかったところで、Python で実装していきましょう。本チュートリアルのノートブックはこの DataLab ワークブックにもあります。コピーを作成すれば、コードを編集・実行できます。自分の環境でコードが動かない場合にも便利です。

ノードの初期化

前述のとおり、ノードは連結リスト内の要素で、データと次ノードへの参照を保存します。Python でのノード定義は以下のとおりです。

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

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

上のコードは、主に2つの処理でノードを初期化します。まず、ノードの「data」属性に、そのノードが保持すべき実データを設定します。次に、「next」属性は次ノードのアドレスを表し、現時点では None に設定されています。これは、まだ他のノードとリンクしていないことを意味します。連結リストに新たなノードを追加していくと、この属性は後続のノードを指すように更新されます。

連結リストクラスの作成

次に、連結リストのクラスを作成します。これは、挿入や削除といったノード管理の操作をカプセル化するものです。まずは連結リストの初期化から始めます。

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head as None提供：

self.head を None に設定することで、連結リストが空であり、指すべきノードが現時点では存在しないことを表します。ここからノードを挿入してリストを構築していきます。

連結リストの先頭にノードを挿入する

LinkedList クラス内に、新しいノードを作成してリストの先頭に配置するメソッドを追加します。

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node提供：

このメソッドを呼び出すたびに、指定したデータを持つ新しいノードが作成されます。新ノードの next ポインタは現在の先頭を指すように設定され、このノードが既存ノードの前に配置されます。最後に、新しく作成したノードをリストの先頭に設定します。

挿入動作をよりよく理解するため、いくつかの単語でリストを構築してみましょう。まず、リストを走査して内容を出力するメソッドを作成します。

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line提供：

このメソッドは連結リストの内容を出力します。では、定義したメソッドを使って「the quick brown fox」という一連の単語でリストを構築しましょう。

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()提供：

上のコードは、次のような出力になります。

"the quick brown fox"

連結リストの末尾にノードを挿入する

LinkedList クラスに insertAtEnd というメソッドを作成し、末尾に新しいノードを追加します。リストが空の場合は新ノードを先頭にします。そうでなければ、現在の最後のノードに連結します。実装を見てみましょう。

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node提供：

このメソッドはまず新しいノードを作成します。次にリストが空かを確認し、空であれば新ノードを先頭に設定します。空でなければ、最後のノードを見つけるまで走査し、そのノードのポインタを新ノードに設定します。

このメソッドを LinkedList クラスに追加し、リストの末尾に単語を挿入してみます。メイン関数を次のように変更してください。

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()提供：

ここでは、insertAtEnd を呼び出して、末尾に「jumps」を追加しています。出力は次のとおりです。

"the quick brown fox jumps"

連結リストの先頭からノードを削除する

連結リストの最初のノードを削除するのは簡単で、先頭を2番目のノードへ向け直すだけです。これで最初のノードはリストの一部ではなくなります。次のメソッドを LinkedList クラスに追加してください。

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head提供：

連結リストの末尾からノードを削除する

連結リストの最後のノードを削除するには、2番目に最後のノードを見つけ、その next ポインタを None に変更します。これで最後のノードはリストから外れます。以下のメソッドを LinkedList クラスに追加してください。

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None提供：

このメソッドは、まず連結リストが空かどうかを確認し、空ならメッセージを返します。要素が1つだけなら、そのノードを削除します。複数ノードがある場合は、2番目に最後のノードを見つけ、その next 参照を None に更新します。

では、メイン関数を更新し、連結リストの先頭と末尾から要素を削除してみます。

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()提供：

このコードは、削除前後のリストを表示し、連結リストでの挿入・削除の動作を確認できます。実行すると次のように表示されるはずです。

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox提供：

特定の値を連結リストから検索する

最後に学ぶ操作は、連結リスト内の特定の値の取得です。これには、先頭から開始して各ノードを順に確認し、ノードのデータが検索値と一致するかをチェックします。実装例は次のとおりです。

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 提供：

作成した連結リストで特定の値を探すため、先ほどの検索メソッドをメイン関数に組み込みます。

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find提供：

このコードは次の出力になります。

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list提供：

「quick」はリストの最初の位置に存在するため、正常に検出されています。一方、「lazy」はリストに含まれていないため、見つかりません。

まとめ

ここまで読んだ方はおめでとうございます。連結リストの基本原理、その構造、種類、要素の追加・削除、走査方法についてしっかり理解できたはずです。

しかし、ここが終着点ではありません。連結リストはデータ構造とアルゴリズムの世界の入り口に過ぎません。理解をさらに深めるための次のステップをいくつか紹介します。

自分のプロジェクトを作る

連結リストを実際に使って、コーディングやデータサイエンスのプロジェクトに組み込んでみてください。連結リストは、ファイルシステムの構築、ハッシュテーブルの作成、GPS ナビゲーションやボードゲームの実装などに使われます。プロジェクトを始めるには、Python、R、SQL で実世界の課題解決を学べる無料のガイド付きデータサイエンスプロジェクトをご覧ください。

データ構造とアルゴリズムを学ぶ

木、スタック、キューといった他のデータ構造を学ぶのは、連結リストの理解の延長として自然な流れです。これらの構造は連結リストの原理を土台にしており、より幅広い計算問題を効率的に解けるようになります。例えば木構造や二分探索木は、連結リストの概念を階層的に拡張し、各ノードが複数の要素へ接続できるようにします。

これらの概念に馴染みがなくても大丈夫です。Datacamp には Python で学ぶデータ構造とアルゴリズムのコースがあり、より詳しく解説します。スタック、木、ハッシュテーブル、キュー、グラフといったデータ構造から学び始め、コースを進めるにつれて探索・ソートアルゴリズムを理解し、より効率的なプログラマ兼問題解決者になる手助けをします。

連結リストの発展的トピック

本チュートリアルでは単方向連結リストを実装し、挿入・削除・走査といった操作を扱いました。

これを土台に、双方向連結リストや循環連結リストの実装を学ぶとさらに理解が深まります。スキップリストは、要素へのアクセスを高速化して探索を高速にする、連結リストの拡張構造です。

こうした発展的データ構造を学ぶことで技術力が向上し、プログラミング能力が大きく伸びます。データサイエンス、ソフトウェア開発、機械学習エンジニアリングといった分野で、より複雑な課題に取り組む準備が整うでしょう。

高度なトピックに進む前に、より入門的なプログラミングの導入を希望する場合は、Python Programming スキルトラックをご覧ください。言語の基礎を学べる一連のコースを提供しています。