データ構造とアルゴリズム：Doubly Linked List（双方向リンクリスト ）

単方向連結リストはnextのみを管理していたが、双方向は名前の通り双方向の連結を管理している。

---

解説

単方向との違いは

class Node(object):
    def __init__(self, data: Any, next_node: Node = None, prev_node: Node = None):
        super().__init__()
        self.data = data
        self.next = next_node
        self.prev = prev_node

と、Nodeクラスのイニシャライズの部分でself.prev = prev_nodeとして、previousデータも一緒に管理できるようにしているところで、これがappendメソッドの中でself.prevにひとつ前のデータを入れることで可能にしている。

こうすることで、インスタンス.nextとすることで次のノードが取得でき、インスタンス.prevとすることで一つ前のノードが管理されているので一つ前ののーどが取得できる。

その次に双方向連結リストのクラスを作っていくのだが、最初の部分はself.headとして単方向連結リストと同様にする。

class DoublyLinkedList(object):

    def __init__(self, head: Node = None) -> None:
        self.head = head

---

append: リストの最後に追加

その次はappendする処理を書く。 appendは新しくnodeをクラスから作成するときにHEADになるパターンとHEAD以降に作られるパターンがあるので、その部分を考えて作成する必要がある。

new_nodeをNodeクラスから作成して、self.headがNoneの場合は一番最初のノードとなるためnew_node_wo self.headにして終了。

そうでなければcurrent_nodeという変数に一度self.headを入れてwhile文でcurrent_node.nextがfalseになる（nextがないので最後のノード）までcurrent_node = current_node.nextでcurrent_nodeを書き換えて最後のノードをcurrent_nodeに入れるまで回す。

最後のノードがどれかわかったので、current_node.next = new_nodeとして新しく作ったノードを最後のノードのnextに管理させる。また、new_nodeにはnew_node.prev = current_nodeとして最後だったノードを新しく更新された最後のノードの一つ前のノードとして管理させることで双方向に連結できる。

def append(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node 
        new_node.prev = current_node

このようにappendする際には

current_node.next = new_node 
new_node.prev = current_node

最後のこの部分でcurrent_nodeの次に新しいデータ、現在のデータは新しいデータの一つ前になるのでnew_node.prev = current_nodeとすることで前と後ろ両方を管理することができる。

完成形：

def append(self, data: Any ) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node
        new_node.prev = current_node

---

insert: リストの先頭に追加

まだリスト内に何もない状態はappendのhead = noneと同じものを使えるのでそのまま、

def insert(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

とする

リスト内に既に何かある場合は、リストのheadに新しいノードを追加して、それまでheadだったノードを新しく追加したhead(new_node)の次に配置してあげればいいので、

self.head.prev = new_node
new_node.next = self.head
self.head = new_node

というような処理を書く。 １行目のself.head.prev = new_nodeで今までのheadの一つ前に新しいノードを配置（headにnew_nodeをprevとして入れることで管理させる。） ２行目で、new_node.nextに今までのheadのノードを管理させる。 最後にリスト自体のインスタンスheadにnew_nodeを配置する必要があるので、self.head = new_nodeとして完成

完成形：

def insert(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

参考：

---

remove: 削除

完成形：

def remove(self, data: Any) -> Node:
        # 先頭のものを削除する場合
        current_node = self.head
        if current_node and current_node.data == data:
            if current_node.next is None:
                current_node = None
                self.head = None
                return
            else:
                next_node = current_node.next
                next_node.prev = None
                current_node = None
                self.head = next_node
                return

まずは先頭のものを削除する場合を考える。 if current_node and current_node.data == data:で先頭の場合のifを作り、その次のifの部分でcurrent_node.nextがなかった場合はcurrent_node = None, self.head = Noneとしてリストから全てを消す。

その次のelseの部分ではnext_node = current_node.nextとして一旦今あるself.headの次のノードを保存してあげて、next_node.prev = Noneでhead部分を削除。self.head = next_nodeでheadを元のheadの次のノードに書き換えて終了。

# 先頭のものを削除する場合
        current_node = self.head
        if current_node and current_node.data == data:
            if current_node.next is None:
                current_node = None
                self.head = None
                return
            else:
                next_node = current_node.next
                next_node.prev = None
                current_node = None
                self.head = next_node
                return

remove 実行

d = DoublyLinkedList()
d.append(0)
d.append(1)
d.append(2)
d.append(3)
d.print()
print('############# REMOVE')
d.remove(0)
d.print()
========================結果========================
0
1
2
3
############# REMOVE
1
2
3

リストの先頭以外にある項目を削除する場合 - 赤枠の箇所で一番後ろにある要素を削除 - 青枠の箇所で中間にある項目を削除している

赤枠： current_node.next == Noneであれば次はないということなのでこれは最後の項目になる。 current_nodeの一つ前を取得してきて、prev.nextとcurrent_node = Noneとすることで最後の要素な全てNoneになるので削除完了

青枠： 一つ前の項目と一つ後の項目をつなげる必要があるので、next_node, prev_nodeをそれぞれ取得してきて、prev_node.nextを直接next_nodeにつなげることでcurrent_nodeが配列から消える。最後にcurrent_node = Noneとして終わり。

実装

prevで前のデータも取得できている

from __future__ import annotations
from typing import Any, Optional


class Node(object):
    def __init__(self, data: Any, next_node: Node = None, prev_node: Node = None) -> None:
        self.data = data
        self.next = next_node
        self.prev = prev_node


class DoublyLinkedList(object):

    def __init__(self, head: Node = None) -> None:
        self.head = head

    def append(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node
        new_node.prev = current_node

    def insert(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

    def print(self) -> None:
        current_node = self.head
        while current_node:
            print(current_node.data)
            current_node = current_node.next

    def remove(self, data: Any) -> Node:
        current_node = self.head
        if current_node and current_node.data == data:
            if current_node.next is None:
                current_node = None
                self.head = None
                return
            else:
                next_node = current_node.next
                next_node.prev = None
                current_node = None
                self.head = next_node
                return

        while current_node and current_node.data != data:
            current_node = current_node.next

        if current_node is None:
            return

        if current_node.next is None:
            prev = current_node.prev
            prev.next = None
            current_node = None
            return
        else:
            next_node = current_node.next
            prev_node = current_node.prev
            prev_node.next = next_node
            next_node.prev = prev_node
            current_node = None
            return



if __name__ == '__main__':
    d = DoublyLinkedList()
    d.append(1)
    d.append(2)
    d.append(3)
    d.insert(0)
    d.print()
    print("######## Remove")
    d.remove(3)
    d.print()

0
1
2
3
######## Remove
0
1
2

1
2
3
2
1