コンテンツにスキップ
CodeMDD.io | Coding Tutorials

Pythonでのリンクリストの使い方を簡単に解説します

CodeMDD.io

リンクリストとは

リンクリストは、順序付けられたオブジェクトのコレクションです。通常のリストとの違いは何でしょうか？リンクリストは、要素をメモリに保存する方法がリストと異なります。通常、リストはデータへの参照を連続したメモリブロックとして保存しますが、リンクリストは参照を各要素の一部として保存します。

メインの概念

リンクリストについてより詳しく学ぶ前に、リンクリストの構造について先に学ぶ必要があります。リンクリストの各要素は「ノード」と呼ばれ、それぞれのノードには2つの異なるフィールドがあります。

  1. Data（データ）：ノードに格納される値です。
  2. Next（次）：リスト内の次のノードへの参照です。

以下は、典型的なノードの例です。

ノードの画像

リンクリストの構造の例

リンクリストの構造について学んだので、いくつかの実用的な用途を見てみましょう。

実用的な応用例

リンクリストは、現実世界でさまざまな目的に使用されます。以下にいくつかの具体的な例を示します。

  • キューやスタックの実装
  • 連結されたデータ構造の表現
  • グラフデータ構造の表現
  • メモリ管理
  • プレイリストの作成
  • コードエディタの履歴の管理など

これらはリンクリストの一部ではありますが、さらに多くの利用方法があります。次は、リンクリストと通常のリストのパフォーマンスの比較について説明します。

パフォーマンス比較: リスト vs リンクリスト

リンクリストと通常のリスト（配列）を比較するとき、それぞれのデータ構造の利点と欠点が明らかになります。

リンクリストの利点:

  • リンクリストは、データの挿入や削除が効率的です。ノードの参照を変更するだけで済むため、他の要素に影響を与える必要がありません。
  • メモリの使用量が柔軟です。必要に応じて、ノードを追加または削除できます。

リンクリストの欠点:

  • ランダムなアクセスは効率が悪くなります。特定の要素にアクセスするために、リストの最初から順番にアクセスする必要があります。
  • 追加のメモリオーバヘッドが発生します。各ノードにはデータとノードへの参照が含まれているため、メモリ使用量が増えます。

通常のリストの利点:

  • ランダムなアクセスが高速です。インデックスを使用して直接要素にアクセスできます。
  • メモリの使用が効率的です。データのみを格納するため、データ量に比例したメモリ使用量です。

通常のリストの欠点:

  • データの挿入や削除が効率が悪くなります。要素を追加または削除するたびに、他の要素を再配置する必要があります。

これらの利点と欠点は、データの追加、削除、アクセスの頻度やボリュームによって異なります。スペースの制約やアクセスパフォーマンスの要件に応じて、適切なデータ構造を選択する必要があります。

リンクリストの基本的な概念とパフォーマンスについて学んだので、Pythonでリンクリストを使用する方法について学んでいきましょう。

collections.dequeの紹介

Pythonでは、組み込みのcollectionsモジュールにdequeというデータ構造が提供されています。dequeはダブルエンドキューとしても知られており、リンクリストのような機能を持っています。

dequeを使うと、リンクリストと同様のデータ操作が可能になります。具体的には、データの追加と削除が高速であり、先頭と末尾の両方に要素を操作できます。

collections.dequeの使い方

dequeを使用するには、まずcollectionsモジュールをインポートします。

from collections import deque

dequeオブジェクトは、次のようにして作成することができます。

linked_list = deque()

以下は、dequeオブジェクトの主な操作方法です。

  • append(item): リンクリストの末尾に要素を追加します。
  • appendleft(item): リンクリストの先頭に要素を追加します。
  • pop(): リンクリストの末尾から要素を削除します。
  • popleft(): リンクリストの先頭から要素を削除します。

以下は、dequeの使用例です。

from collections import deque


linked_list = deque()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.appendleft(0)


print(linked_list)  # Output: deque([0, 1, 2, 3])


linked_list.pop()
linked_list.popleft()


print(linked_list)  # Output: deque([1, 2])

dequeを使用することで、リンクリストのようなデータ構造を簡単に作成および操作することができます。

自分自身でリンクリストを実装する

Pythonでは、リンクリストを自分で実装することもできます。以下は、リンクリストを作成する方法です。

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


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

ノードは、データと次のノードへの参照を持つように定義されています。リンクリストは、ヘッド（最初のノード）を持つように定義されています。

リンクリストにノードを追加するには、次のようにします。

new_node = Node(data)

リストの最初にノードを追加するには、次のようにします。

new_node.next = linked_list.head
linked_list.head = new_node

以下は、自分で実装したリンクリストを使用する例です。

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


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


    def add_node(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node


linked_list = LinkedList()
linked_list.add_node(1)
linked_list.add_node(2)
linked_list.add_node(3)


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

この例では、リンクリストを作成し、ノードを追加して出力しています。

高度なリンクリストの使用

リンクリストには様々な種類があります。以下は、いくつかの例です。

二重リンクリストの使用方法

二重リンクリストは、各ノードが前のノードと次のノードの両方への参照を持っているリンクリストです。これにより、前後のノードへの移動が簡単になります。

二重リンクリストを使用するためには、Nodeクラスを次のように変更します。

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

前のノードへの参照を追加しました。これにより、ノードを前後に移動することができます。

循環リンクリストの使用方法

循環リンクリストは、最後のノードが最初のノードを指すリンクリストです。これにより、リスト内のノードを繰り返し操作することができます。

循環リストを使用するためには、LinkedListクラスを次のように変更します。

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


    def add_node(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            self.tail.next = self.head
        else:
            new_node.next = self.head
            self.tail.next = new_node
            self.tail = new_node

最後のノードは先頭のノードを指すようになります。これにより、リストを繰り返し操作することができます。

以上が、高度なリンクリストの使用方法の例です。

まとめ

この記事では、Pythonでのリンクリストの基本的な概念と使用方法について学びました。リンクリストはデータの挿入と削除が容易であり、様々な応用があります。また、collections.dequeを使用することで、Pythonで簡単にリンクリストの操作ができます。さらに、自分でリンクリストを実装する方法と、高度なリンクリストの使用方法についても学びました。

リンクリストは、適切な状況で非常に役立つデータ構造です。Pythonでのプログラミングやデータ構造の学習において、リンクリストを活用してみてください。