Pythonのリンクリスト

2022.10.03

リンクリストは、コンピュータサイエンスで最もよく使われるデータ構造の1つです。

また、最も単純な構造の1つでもあり、スタック、循環バッファ、キューなどの高次構造の基礎にもなっている。

一般にリストは、参照によって接続された単一のデータ要素の集合体です。

C言語プログラマはこれをポインタと呼んでいる。

例えば、データ要素は、アドレスデータ、地理データ、幾何データ、ルーティング情報、またはトランザクションの詳細から構成されることができます。

通常、リンクリストの各要素は、そのリストに固有の同じデータ型を持っています。

1つのリスト要素をノードと呼ぶ。

ノードは、メモリに順次格納される配列のようなものではありません。

その代わり、異なるメモリセグメントで見つけることができ、あるノードから次のノードへのポインタを追うことで見つけることができるようです。

リストの最後をNIL要素でマークするのが一般的で、Pythonでは None で表現されます。

図1: シングルリンク・リスト

リストにはシングルリンクとダブルリンクの2種類があります。

シングルリンクリストのノードはリストの次の要素を指すだけであるが、ダブルリンクリストのノードは前のノードも指す。

このデータ構造では、さらに参照を格納するための変数が必要になるため、より大きなスペースを占めます。

図2：ダブルリンクリスト

単一リンクリストは、先頭から末尾までたどることができるが、後方へのたどるのはそれほど簡単ではない。

これに対し、ダブルリンクリストでは、どのノードから始めても、同じコストで両方向のノードを走査することができる。

また、ノードの追加や削除、シングルリンクリストの分割は2ステップ以内で行われる。

ダブルリンクリストでは4つのポインタを変更する必要があります。

Python言語にはリンクリストのための定義済みのデータ型がありません。

この状況に対処するためには、独自のデータ型を作成するか、そのようなデータ型の実装を提供する追加のPythonモジュールを使用する必要があります。

この記事では、独自のリンクリストのデータ構造を作成する手順を説明します。

まず、ノードに対応するデータ構造を作成します。

次に、シングルリンクリスト、そして最後にダブルリンクリストの両方を実装して使用する方法を学びます。

ステップ1：データ構造としてのノード

データ構造として扱うために、ノードを定義する。

ノードは ListNode という名前のクラスとして実装されています。

このクラスはオブジェクトのインスタンスを生成するための定義を含んでおり、この場合、2つの変数 – ノードの値を保持する data と、リスト内の次のノードへの参照を格納する next – を持ちます。

さらに、ノードは以下のメソッドとプロパティを持っています。

  • __init_(): ノードをデータと共に初期化する。
  • self.data: ノードに格納された値
  • self.next: 次のノードへの参照ポインタ
  • has_value(): 値とノードの値を比較する

これらのメソッドは、ノードを適切に初期化し (__init__()) 、データの抽出と保存 (self.data プロパティを使用) 、接続されたノードへの参照 (self.next プロパティを使用) の両方をカバーすることを保証しています。

メソッド has_value() は、ノードの値を別のノードの値と比較することができます。

リスト 1: ListNode クラス

class ListNode:
    def __init__(self, data):
        "constructor to initiate this object"

        # store data
        self.data = data

        # store reference (next item)
        self.next = None
        return

    def has_value(self, value):
        "method to compare the value with the node data"
        if self.data == value:
            return True
        else:
            return False

ノードの作成はこれと同じくらい簡単で、クラス ListNode のオブジェクトをインスタンス化します。

リスト2: ノードのインスタンス化

node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")

これで ListNode クラスのインスタンスが 3 つできました。

これらのインスタンスは、値 15 (整数)、8.2 (浮動小数点数)、そして “Berlin” (文字列) を含む、3つの独立したノードを表します。

ステップ2: 単一リンクリストのクラスを作成する

第二段階として、リストノードを管理するために必要なメソッドをカバーする SingleLinkedList という名前のクラスを定義します。

このクラスには、以下のメソッドが含まれています。

  • __init__(): オブジェクトを生成する。
  • __init__(): オブジェクトを生成する * list_length(): ノードの数を返す
  • output_list(): ノードの値を出力する。
  • add_list_item(): リストの末尾にノードを追加する。
  • unordered_search(): 指定された値を持つノードをリストから検索する。
  • remove_list_item_by_id(): ノードをその ID に従って削除します。

これらのメソッドを順を追って見ていきましょう。

init()メソッドは、headとtailという名前の 2 つの内部クラス変数を定義しています。

これらはリストの先頭と末尾のノードを表している。

初期状態では、リストが空である限りheadとtailの両方ともNone` という値を持っています。

リスト3: SingleLinkedListクラス (パート1)

class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"

        self.head = None
        self.tail = None
        return

ステップ 3: ノードの追加

リストへのアイテムの追加は add_list_item() で行います。

このメソッドでは、追加のパラメータとしてノードを必要とします。

それが適切なノード (クラス ListNode のインスタンス) であることを確認するために、まず Python の組み込み関数 isinstance() を使ってパラメータが検証されます。

成功すると、そのノードがリストの末尾に追加されます。

もし、 item が ListNode でない場合は、ListNode が生成されます。

リストが（まだ）空の場合、新しいノードがリストの先頭になります。

もし、リストに既にノードがある場合は、tailの値がそれに応じて調整されます。

リスト 4: SingleLinkedList クラス (パート 2)

    def add_list_item(self, item):
        "add an item at the end of the list"

        if not isinstance(item, ListNode):
            item = ListNode(item)


if self.head is None:
            self.head = item
        else:
            self.tail.next = item


self.tail = item

        return

list_length()メソッドはノードをカウントして、リストの長さを返します。

リスト内のあるノードから次のノードに移動するには、ノードプロパティself.next` が使用され、次のノードへのリンクが返されます。

ノードのカウントは、リストの最後に到達しない限り、while ループで行われます。

リスト 5: SingleLinkedList クラス (パート 3)

    def list_length(self):
        "returns the number of list items"

        count = 0
        current_node = self.head

        while current_node is not None:
            # increase counter by one
            count = count + 1

            # jump to the linked node
            current_node = current_node.next

        return count

メソッド output_list() は、ノードプロパティ data を用いてノードの値を出力します。

ここでも、あるノードから次のノードに移動するために、 next プロパティを介して提供されるリンクが使用されます。

リスト6: SingleLinkedListクラス (パート4)

    def output_list(self):
        "outputs the list (the value of the node, actually)"

         current_node = self.head

        while current_node is not None:
            print(current_node.data)

            # jump to the linked node
            current_node = current_node.next

        return

クラス SingleLinkedList に基づいて、リスト 3-6 で既に説明したように、 track という名前の適切なリストを作成して、そのメソッドを使用することができます。

そこで、4つのリストノードを作成し、それらを for ループで評価し、リストの内容を出力します。

リスト7はそのプログラミング方法を示し、リスト8はその出力を示しています。

リスト 7: ノードの作成とリスト出力

# create four single nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
item3 = "Berlin"
node4 = ListNode(15)


track = SingleLinkedList()
print("track length: %i" % track.list_length())


for current_item in [node1, node2, item3, node4]:
    track.add_list_item(current_item)
    print("track length: %i" % track.list_length())
    track.output_list()

出力は以下のようになり、リストがどのように成長していくかを示しています。

リスト 8: リストへのノードの追加

$ python3 simple-list.py
track length: 0
track length: 1
15
track length: 2
15
8.2
track length: 3
15
8.2
Berlin
track length: 4
15
8.2
Berlin
15

ステップ 4: リストを検索する

リスト全体の検索は unordered_search() メソッドで行います。

このメソッドには、検索する値を指定する追加のパラメーターが必要です。

リストの先頭が出発点です。

検索中は、ノードを数えます。

マッチしたことを示すために、対応するノード番号を使用します。

メソッド unordered_search() は、マッチしたノードの番号のリストを返します。

例えば、最初のノードと4番目のノードの両方が値15を含んでいるとします。

15を検索した結果、2つの要素を持つリストが得られます。

Listing 9: 検索メソッド unordered_search()

    def unordered_search (self, value):
        "search the linked list for the node that has this value"

        # define current_node
        current_node = self.head

        # define position
        node_id = 1

        # define list of results
        results = []

        while current_node is not None:
            if current_node.has_value(value):
                results.append(node_id)

            # jump to the linked node
            current_node = current_node.next
            node_id = node_id + 1

        return results

ステップ 5: リストから項目を削除する

リストからノードを削除するには、1つの参照だけを調整する必要があります。

削除されるノードを指す参照は、次のノードを指すようにしなければなりません。

この参照は削除されるノードによって保持されているので、置き換えなければなりません。

バックグラウンドでは、Pythonのガベージコレクタが参照されないオブジェクトの面倒をみて、整理してくれます。

次のメソッドは remove_list_item_by_id() と名付けられています。

パラメータとして、 unordered_search() が返す値と同じようなノードの番号を参照します。

リスト10: ノード番号でノードを削除する

    def remove_list_item_by_id(self, item_id):
        "remove the list item with the item id"

        current_id = 1
        current_node = self.head
        previous_node = None

        while current_node is not None:
            if current_id == item_id:
                # if this is the first node (head)
                if previous_node is not None:
                    previous_node.next = current_node.next
                else:
                    self.head = current_node.next
                    # we don't have to look any further
                    return

            # needed for the next iteration
            previous_node = current_node
            current_node = current_node.next
            current_id = current_id + 1

        return

ステップ6: ダブルリンクリストの作成

ダブルリンクリストを作成するには、前のノードへの参照を追加して ListNode クラスを拡張するのが自然な感じです。

これは、ノードの追加、削除、ソートのメソッドに影響します。

リスト11に示すように、リスト内の前のノードへの参照ポインタを格納するために、 previous という名前の新しいプロパティが追加されました。

ノードの追跡とトラバースにもこのプロパティを使用するようにメソッドを変更します。

リスト 11: 拡張されたリストノードクラス

class ListNode:
    def __init__(self, data):
        "constructor class to initiate this object"


# store data
        self.data = data

        # store reference (next item)
        self.next = None


# store reference (previous item)
        self.previous = None
        return


def has_value(self, value):
        "method to compare the value with the node data"
        if self.data == value:
            return True
        else:
            return False

これで、以下のようにダブルリンクリストを定義できるようになりました。

リスト 12: ダブルリンクリストクラス

class DoubleLinkedList:
    def __init__(self):
        "constructor to initiate this object"


self.head = None
        self.tail = None
        return


def list_length(self):
        "returns the number of list items"

        count = 0
        current_node = self.head


while current_node is not None:
            # increase counter by one
            count = count + 1

            # jump to the linked node
            current_node = current_node.next

        return count


def output_list(self):
        "outputs the list (the value of the node, actually)"
        current_node = self.head


while current_node is not None:
            print(current_node.data)


# jump to the linked node
            current_node = current_node.next

        return


def unordered_search (self, value):
        "search the linked list for the node that has this value"


# define current_node
        current_node = self.head


# define position
        node_id = 1


# define list of results
        results = []


while current_node is not None:
            if current_node.has_value(value):
                results.append(node_id)

            # jump to the linked node
            current_node = current_node.next
            node_id = node_id + 1

        return results

前述したように、ノードを追加するにはもう少し動作が必要です。

リスト 13 はそれを実装する方法を示しています。

リスト 13: ダブルリンクリストにノードを追加する

    def add_list_item(self, item):
        "add an item at the end of the list"


if isinstance(item, ListNode):
            if self.head is None:
                self.head = item
                item.previous = None
                item.next = None
                self.tail = item
            else:
                self.tail.next = item
                item.previous = self.tail
                self.tail = item

        return

リストからアイテムを削除するには、同様のコストを考慮する必要があります。

リスト 14 はその方法を示しています。

リスト14: ダブルリンクリストからアイテムを削除する

    def remove_list_item_by_id(self, item_id):
        "remove the list item with the item id"

        current_id = 1
        current_node = self.head


while current_node is not None:
            previous_node = current_node.previous
            next_node = current_node.next


if current_id == item_id:
                # if this is the first node (head)
                if previous_node is not None:
                    previous_node.next = next_node
                    if next_node is not None:
                        next_node.previous = previous_node
                else:
                    self.head = next_node
                    if next_node is not None:
                        next_node.previous = None
                # we don't have to look any further
                return

            # needed for the next iteration
            current_node = next_node
            current_id = current_id + 1

        return

リスト 15 は、Python プログラムでこのクラスを使用する方法を示しています。

リスト15: ダブルリンクリストを作成する

# create three single nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")
node4 = ListNode(15)


track = DoubleLinkedList()
print("track length: %i" % track.list_length())


for current_node in [node1, node2, node3, node4]:
    track.add_list_item(current_node)
    print("track length: %i" % track.list_length())
    track.output_list()


results = track.unordered_search(15)
print(results)


track.remove_list_item_by_id(4)
track.output_list()

見ての通り、このクラスは単なるシングルリンクリストだったときと全く同じように使うことができます。

唯一の変更は、内部のデータ構造です。

ステップ 7: deque による二重リンクリストの作成

他のエンジニアも同じ問題に直面しているので、私たちは自分たちのために物事を単純化し、利用可能ないくつかの既存の実装のうちの1つを使用することができます。

Pythonでは、 collections モジュールの deque オブジェクトを使用できます。

とあります。

Deques はスタックとキューを一般化したものです（名前は “deck” と発音し、 “double-ended queue” を略したものです）。

Deques はスレッドセーフで、メモリ効率の良い追加とポップを deque のどちら側からでも、ほぼ同じ O(1) の性能でサポートします。

例えば、このオブジェクトは以下のメソッドを含んでいます。

  • append(): リストの右側に項目を追加する (end)
  • append_left(): リストの左側 (head) に項目を追加する。
  • clear(): リストからすべての項目を削除します。
  • count(): ある値を持つアイテムの個数を数える
  • index(): リスト内で最初に現れる値を見つける
  • insert(): リスト内にアイテムを挿入する
  • pop(): リストの右側から項目を削除する (end)
  • popleft(): リスト (head) の左側から項目を削除する
  • remove(): リストから項目を削除する
  • reverse(): リストを反転させる

dequeの基本データ構造は Python のリストであり、ダブルリンクされています。

最初のリストのノードのインデックスは 0 です。

deque を使用することで、 ListNode クラスを大幅に簡略化することができます。

唯一残しているのは、ノードの値を格納するためのクラス変数 data だけです。

リスト16は次のようになります。

リスト16: dequeを使ったListNodeクラス (簡略化)

from collections import deque


class ListNode:
    def __init__(self, data):
        "constructor class to initiate this object"

        # store data
        self.data = data

        return

ノードの定義は変更されず、リスト2と同様です。

この知識を踏まえて、以下のようにノードのリストを作成します。

リスト 17: deque を使ってリストを作成する

track = deque([node1, node2, node3])
print("three items (initial list):")
for item in track:
    print(item.data)

リストの先頭に項目を追加するには、リスト18が示すように append_left() メソッドを使用します。

リスト18: リストの先頭に要素を追加する

# add an item at the beginning
node4 = ListNode(15)
track.append_left(node4)
print("four items (added as the head):")
for item in track:
    print(item.data)

同様に、リスト19が示すように、append()はリストの末尾にノードを追加します。

リスト19: リストの末尾に要素を追加する

# add an item at the end
node5 = ListNode("Moscow")
print("five items (added at the end):")
track.append(node5)
for item in track:
    print(item.data)

結論

データ構造としてのリンクリストは、実装が簡単で、使い方の柔軟性が高い。

これは数行のコードで実現できます。

改良点として、ノードカウンタ（リスト内のノード数を単純に保持するクラス変数）を追加することができます。

さらに詳しい情報や代替の実装については、こちらを参照してください。

  • llist – Python 用のリンクリストのデータ型 (https://pythonhosted.org/llist/)
  • collections – コンテナ型データ型 (https://docs.python.org/3.6/library/collections.html)

謝辞

本論文の作成にあたり，Gerold RupprechtとMandy Neumeyerのサポートとコメントに感謝したい。

タイトルとURLをコピーしました