両方向連結リスト

カバー画像：両方向連結リスト

前回のブログ投稿で片方向連結リストの実装について見てきましたね。今回の投稿では、その兄弟版の両方向連結リストについて詳しく見ていきましょう。

両方向連結リストを理解する

片方向連結リストと同じく、両方向連結リストとはノードの集まりから構成されるデータ構造です。この場合の各ノードは個別のオブジェクトですが、ユニークな点は各ノードが次のノードにだけでなく前のノードにもリンクされていることです。この双方向のリンクにより、両方向への効率的なトラバース（探索）が可能になります。

両方向連結リスト

片方向連結リストが次の要素を指し示すのに対し、両方向連結リストでは各ノードが二つのポインタを持ちます。一つは次の要素を指し、もう一つは前の要素を指します。

ノードの追加

両方向連結リストにノードを追加するのは、片方向連結リストより少し複雑です。prevノードとnextノードの間にcurノードを挿入するとしましょう。これを実現するためには次の手順を踏む必要があります：

prevノードの参照フィールドをcurノードを指すように設定します。
curノードの参照フィールドをnextノードを指すように設定します。
双方向リンクを完成させるために、nextノードの参照フィールドもcurノードを指し戻すように調整します。

両方向連結リストの挿入プロセスも効率が保たれ、prevとnextノードへの参照があればO(1)の時間計算量で新しいノードを挿入できます。

ノードの削除

両方向連結リストでのノード削除も、挿入と同様に、双方向リンクのため少し手間がかかります。削除したいノードcurについて考えましょう：

先にcurノードの前のノードprevと次のノードnextを探します。
curノードからのリンクを断ち切るために、prevノードの参照フィールドをnextノードを指すように調整します。
prevノードを指し戻すためにnextノードの参照フィールドも調整します。

両方向連結リストでは、参照フィールドを使用して次のノードnextを簡単に見つけることができます。しかし、前のノードprevを見つけるのも同様に効率的です。なぜならリストを両方向にトラバースできるからです。ノードを削除する時間計算量もO(1)です。

Pythonを使用した実装

それでは、Pythonでの両方向連結リストの実装を見ていきましょう：

# ListNodeクラスは両方向連結リストのノードを表します。
class ListNode:
    def __init__(self, val):
        self.val = val  # 現在のノードの値
        self.prev = None  # 前のノードへの参照
        self.next = None  # 次のノードへの参照

# MyLinkedListクラスは指定されたメソッドで両方向連結リストを実装します。
class MyLinkedList:
    def __init__(self):
        self.head = None  # 先頭ノード（最初のノード）への参照
        self.tail = None  # 末尾ノード（最後のノード）への参照
        self.size = 0     # 連結リストのノード数

    # 連結リストの指定されたインデックスにあるノードの値を取得します。
    def get(self, index):
        if index < 0 or index >= self.size:
            return -1  # 無効なインデックスには-1を返します

        current = self.head
        for _ in range(index):
            current = current.next

        return current.val

    # 指定された値で新しいノードを連結リストの先頭に追加します。
    def addAtHead(self, val):
        new_node = ListNode(val)
        if self.size == 0:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.size += 1

    # 指定された値で新しいノードを連結リストの末尾に追加します。
    def addAtTail(self, val):
        new_node = ListNode(val)
        if self.size == 0:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    # 指定されたインデックスのノードの前に、与えられた値で新しいノードを追加します。
    def addAtIndex(self, index, val):
        if index < 0 or index > self.size:
            return  # 無効なインデックスの場合は何もしません

        if index == 0:
            self.addAtHead(val)
        elif index == self.size:
            self.addAtTail(val)
        else:
            new_node = ListNode(val)
            current = self.head
            for _ in range(index - 1):
                current = current.next

            new_node.prev = current
            new_node.next = current.next
            current.next.prev = new_node
            current.next = new_node
            self.size += 1

    # 連結リストの指定されたインデックスのノードを削除します。
    def deleteAtIndex(self, index):
        if index < 0 or index >= self.size:
            return  # 無効なインデックスの場合は何もしません

        if self.size == 1:
            self.head = self.tail = None
        elif index == 0:
            self.head = self.head.next
            self.head.prev = None
        elif index == self.size - 1:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            current = self.head
            for _ in range(index):
                current = current.next
            current.prev.next = current.next
            current.next.prev = current.prev

        self.size -= 1

フルスクリーンモードを終える

これで両方向連結リストについての説明はおしまいです。次回もお会いしましょう。それでは、さようなら！

こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。
https://dev.to/iamadhee/doubly-linked-lists-4c8o

両方向連結リスト