Python で双方向リンク リストを作成する

この記事では、Python プログラミング言語を使用して双方向リンク リストを作成する方法について説明します。

Python で双方向リンク リストを作成する

双方向リンク リストとは、ノードと呼ばれる一連のレコードが連続してリンクされた、リンクされたデータ構造を指します。 各ノードには、前のポインター、次のポインター、およびデータ フィールドが含まれます。

前のポインタと次のポインタは、前のノードと次のノードを指します。 最初のノードの前のポインターと最後のノードの次のポインターは None を指します。

双方向リンクリストの特定のノードの前後に新しいノードを挿入できます。 また、双方向にリンクされたリストを前後にトラバースできます。

ただし、すべての双方向リンク リスト ノードには、前のポインター用の余分なスペースが必要です。

ノードクラスは次のように作成されます。 デフォルトでは、ポインターとデータ値は None です。

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

次に、双方向リンク リストに使用するクラスを作成します。 self.head はリストの先頭を示し、最初は None です。

add_to_end 関数を使用して、二重リンク リストの最後に新しいノードを追加します。 まず、new_node 変数を使用して Node クラスのインスタンスを作成します。

new_node はリストの最後の値になるため、次のポインターを None に設定します。 new_node を追加するノードを見つけるために last 変数を定義します。

まず、この変数は双方向リンク リストの先頭です (最初に追加されたノードの場合、この先頭は None になります)。

if ブロックで self.head が None かどうかを確認します。 その場合、リストにはノードがなく、リストの先頭は新しく追加されたノードになります。

while ブロックでは、last 変数の next ポインターをチェックして、リストの最後の値を見つけます。 None が得られるまで、last 変数を last.next に置き換えます。

last.next の値が None であるノードが見つかったら、リストを終了します。

new_node を指すことがわかった last ノード値の next ポインターを設定します。 最後に、new_node 変数の previous ポインタを last 変数に設定します。

したがって、new_node ノードは双方向リンク リストの最後に追加されます。

以下のコードを参照してください。

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

    def add_to_end(self, new_node):

        new_node = Node(data=new_node)
        new_node.next = None
        last = self.head

        if self.head is None:
            new_node.previous = None
            self.head = new_node
            return

        while last.next is not None:
            last = last.next

        last.next = new_node
        new_node.previous = last

add_to_beginning 関数を使用して、双方向リンク リストの先頭にノードを追加できます。 このプロセスはより簡単です。

まず、new_node 変数の next ポインターを self.head に設定し、previous ポインターを None に設定します。 したがって、古いリストの最初の値である先頭の値は、new_node が指す次の値になります。

if ブロックでは、リストが空の場合、self.head の値が None かどうかを確認します。 この値が定義されているか、先頭に対応するノードがある場合、このノードの previous ポインターを new_node に変更します。

最後に、self.head を new_node に変更します。 したがって、new_node が双方向リンク リストの先頭に追加されます。

以下のコードのデモを参照してください。

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

    def add_to_end(self, new_node):
        # previous function
        pass

    def add_to_beginning(self, new_node):

        new_node = Node(data=new_node)
        new_node.next = self.head
        new_node.previous = None

        if self.head is not None:
            self.head.previous = new_node

        self.head = new_node

以下の例では、double_linked_list 変数が最初に作成されます。 この変数は DoublyLinkedList クラスのインスタンスです。

次に、リストの最後に 1 と 3 を、先頭に 5 をそれぞれ追加します。 リストの最終状態は、5 -> 1 -> 3 -> None です。

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.add_to_end(1)
doubly_linked_list.add_to_end(3)
doubly_linked_list.add_to_beginning(5)