【Python】循環・重連結リスト【アルゴリズム】

2023年1月12日

Pythonでアルゴリズムの循環リスト、重連結リスト、循環・重連結リストの解説をします。

循環リスト

循環リスト(circular list)は線形リストの末尾ノードに先頭ノードを参照するポインタを加えたものです。

そのため末尾ノードの後続ポインタはNoneではなく、先頭ノードへのポインタになっています。

それ以外は線形リストと同じ構造です。

図を見てもわかるように環状になっているのが特徴です。

重連結リスト

重連結リスト(doubly list)は線形リストに先行ノードを参照するポインタを加えたものです。

よって重連結リストでは先行ノードを参照するポインタと後続ノードを参照するポインタの両方が備わります。

これにより線形リストでは困難だった先行ノードを見つけるのが簡単になります。

循環リストとは違い環状になっていないので、先頭ノードの先行ポインタと末尾ノードの後続ポインタの値はNoneです。

なお重連結リストは双方向リスト(bidirectional linked list)とも呼ばれています。

循環・重連結リスト

循環リストと重連結リストを合わせたものが循環・重連結リスト(circular doubly linked list)です。

個々のノードの構造は重連結リストと同じく先行ノードを参照するポインタと後続ノードを参照するポインタとデータの3つです。

ただし先頭ノードの先行ポインタは末尾ノード、末尾ノードの後続ポインタは先行ノードをそれぞれ参照します。

そのため先行ポインタも後続ポインタも循環リストのように環状になっています。

この循環・重連結リストをプログラムで表すことを考えます。

ノードクラスNode

# 循環・重連結リスト

from __future__ import annotations
from typing import Any, Type

class Node:
    """循環・重連結リスト用ノードクラス"""

    def __init__(self, data: Any = None, prev: Node = None,
                 next: Node = None) -> None:
        """初期化"""
        self.data = data         # データ
        self.prev = prev or self # 先行ポインタ
        self.next = next or self # 後続ポインタ

フィールド

ノードクラスNodeには3つのフィールドがあります。

フィー
ルド名		 内容

型
data データ

任意
prev 先行ポインタ

Node型
next 後続ポインタ

Node型

線形リストではdataとnextのみでしたが、循環・重連結リストではprevが追加されます。

ノードの構造については下の通りで、データと先行ポインタと後続ポインタの3つで構成されています。

__init__メソッド

__init__メソッドでは仮引数dataとprevとnextを対応するフィールドに代入して初期化します。

仮引数prevやnextがNoneを受け取った場合は、先行ポインタprevや後続ポインタnextはselfが代入されます。

その結果、先行ポインタと後続ポインタは自身のインスタンスを参照するようになります。

prevやnextの代入にはor演算子が使われていて、Noneであるかどうかによって代入する値を変えます。

prevやnextが真(Noneではない)であればself.prev = prev、self.next = nextが代入、

prevやnextが偽(Noneである)であればself.prev = self、self.next = selfが代入されます。

循環・重連結リストクラスCircularDoublyLinkedList

class CircularDoublyLinkedList:
    """循環・重連結リストクラス"""

    def __init__(self) -> None:
        """初期化"""
        self.head = self.current = Node() # ダミーノードを作成
        self.no = 0

フィールド

循環・重連結リストクラスCircularDoublyLinkedListには3つのフィールドがあります。

フィー
ルド名		 内容
no リスト上のノードの個数
head 先頭ノードへの参照
current 現在着目しているノードへの参照
(着目ポインタ)

__init__メソッド

__init__メソッドではノードが0個の空の循環・重連結リストを生成します。

その際にノードの挿入や削除などを行いやすくするようにデータのないノードを1個作ります。

このノードはダミーノードといい、リストの個数に関係なく先頭に置き続けます。

クラスNodeの__init__メソッドにより、Node()で生成されたprevとnextは自身のノードを参照するようになります。

headとcurrentの参照先はダミーノードにしています。

上の図はダミーノードのみが生成された空の循環・重連結リストを表しています。

リストのノードの個数を返却__len__メソッド

def __len__(self) -> int:
        """リスト上のノード数を返却"""
        return self.no

__len__メソッドでは循環・重連結リストのノード数を、noの値で返却します。

リストが空であるかis_empty

def is_empty(self) -> bool:
        """リストは空か"""
        return self.head.next is self.head

is_emptyメソッドではリストが空かどうかを判定しています。

リストが空ということはダミーノードのみ存在するということになります。

そこでheadの参照先であるダミーノードの後続ポインタhead.nextがhead(ダミーノード)を参照していれば空になります。

リストが空であればTrue、空でなければFalseを返却します。

ノードの探索search

def search(self, data: Any) -> Any:
    """dataと等価なノードを探索"""
    cnt = 0
    ptr = self.head.next        # 現在走査中のノード(先頭ノード)
    while ptr is not self.head:
        if data == ptr.data:
            self.current = ptr
            return cnt          # 探索成功
        cnt += 1
        ptr = ptr.next          # 後続ノードに着目
    return -1                   # 探索失敗

searchメソッドでは引数として与えられたデータdataと等しいノードを探索します。

先頭から末尾まで後続ポインタをたどっていって見つけるのは線形リストと同じです。

ただ循環・重連結リストの先頭にあるのはダミーノードであり探索対象にはなりません。

なのでダミーノードの後続ノードであるhead.nextが実質的な先頭ノードになり、ここから探索が始まります。

下の図のようにダミーノードはhead、先頭ノードはhead.next、末尾ノードはhead.prevと表されます。

while文では等しい値のノードを見つけると探索成功になります。

着目ポインタcurrentをそのノードの位置にして、カウンタ変数cntを返却して場所を知らせます。

等しくないときはcntをインクリメントしてptrをptr.nextつまり後続ノードに着目させるようにします。

等しい値が見つからずに一巡してダミーノードheadに戻ってきたときは探索失敗を表す-1を返却します。

なおsearchは空のリストの場合は必ず探索失敗します。

まず最初にptrに代入されるhead.nextは自分自身であるダミーノードheadになります。

このためwhile文の判定式ptr is not self.headは偽になるので探索失敗を表す-1を返却します。

着目ノードの表示print_current_node

def print_current_node(self) -> None:
    """着目ノードを表示"""
    if self.is_empty():
        print('着目ノードがありません。')
    else:
        print(self.current.data)

print_current_nodeメソッドでは現在着目しているノードのデータcurrent.dataを表示します。

ただしリストが空であれば「着目ノードがありません。」と表示します。

リストが空かどうかの判定はis_emptyメソッドを使っています。

全ノードの表示print

def print(self) -> None:
    """全ノードを表示"""
    ptr = self.head.next        # ダミーノードの後続ノード(実質的先頭ノード)
    while ptr is not self.head:
        print(ptr.data)
        ptr = ptr.next

printメソッドではリストの全ノードを先頭から末尾まで順に表示します。

head.nextから開始して後続ポインタをたどりながらノードのデータを表示していきます。

一巡してダミーノードheadに戻ったらwhile文を抜けて終了します。

下の図はノードが5個のリストに適応したもので赤い矢印の線がptrの移動経路です。

上の図のリストであれば①→②→③→④→⑤→⑥とptrが移動します。

ただし表示されるのは①の移動先のhead.nextで最後に表示されるのは⑥の移動前のhead.prevです。

全ノードの逆順表示print_reverse

def print_reverse(self) -> None:
    """全ノードを逆順に表示"""
    ptr = self.head.prev        # ダミーノードの先行ノード(末尾ノード)
    while ptr is not self.head:
        print(ptr.data)
        ptr = ptr.prev

print_reverseメソッドではリストの全ノードを末尾から逆順に表示します。

ダミーノードの先行ノードつまり末尾ノードhead.prevから開始して先行ポインタをたどりながらノードのデータを表示していきます。

一巡してダミーノードheadに戻ったらwhile文を抜けて終了します。

下の図はノードが5個のリストに適応したもので赤い矢印の線がptrの移動経路です。

上の図のリストであれば①→②→③→④→⑤→⑥とptrが移動します。

ただし表示されるのは①の移動先のhead.prevで最後に表示されるのは⑥の移動前のhead.nextです。

着目ノードを後方に進めるnext

def next(self) -> bool:
    """着目ノードを一つ後方に進める"""
    if self.is_empty() or self.current.next is self.head:
        return False    # 進めることができなかった
    self.current = self.current.next
    return True

nextメソッドでは着目ノードを一つ後方に進めます。

ただしこのメソッドが実行されるのはリストが空でなく、着目ノードに後続ノードが存在するときのみです。

currnetの後続ノードがダミーノードでないということは着目ノードに後続ノードが存在するということになります。

currentをcurrent.nextにすることで着目ノードを一つ後方に移動させます。

進めたときはTrue、進めなかったときはFalseを返却します。

着目ノードを前方に進めるprev

def prev(self) -> bool:
    """着目ノードを一つ前方に進める"""
    if self.is_empty() or self.current.prev is self.head:
        return False    # 進めることができなかった
    self.current = self.current.prev
    return True

prevメソッドでは着目ノードを一つ前方に進めます。

ただしこのメソッドが実行されるのはリストが空でなく、着目ノードに先行ノードが存在するときのみです。

currnetの先行ノードがダミーノードでないということは着目ノードに先行ノードが存在するということになります。

currentをcurrent.prevにすることで着目ノードを一つ前方に移動させます。

進めたときはTrue、進めなかったときはFalseを返却します。

ノードを挿入add

def add(self, data: Any) -> None:
    """着目ノードの直後にノードを挿入"""
    node = Node(data, self.current, self.current.next)
    self.current.next.prev = node
    self.current.next = node
    self.current = node
    self.no += 1

addメソッドでは着目ノードの直後にノードを挿入します。

下の図のようにノードA、B、Cがあるとします。

ノードBが着目ノードcurrentのとき、ノードAはcurrent.prev、ノードCはcurrent.nextとなります。

このときにaddメソッドでノードDを挿入する手順は次の通りです。

挿入するノードをNode(data, current, current.next)で生成します。

これで挿入ノードはデータがdata、先行ポインタの参照先はノードB(current)、後続ポインタの参照先はノードC(current.next)となります。

次にノードBの後続ポインタ(current.next)とノードCの先行ポインタ(current.next.prev)の参照先を挿入ノードnodeにします。

その結果挿入ノードDはノードBとノードCの間に入ります。

最後に着目ポインタcurrentが挿入したノードを参照するようにして、ノードの個数を増やせば完了です。

先頭へのノードの挿入add_first

def add_first(self, data: Any) -> None:
    """先頭にノードを挿入"""
    self.current = self.head       # ダミーノードheadの直後に挿入
    self.add(data)

add_firstメソッドではリストの先頭にノードを挿入します。

ただし線形リストと違う点としてリストの先頭には必ずダミーノードが存在します。

なのでリストの先頭に挿入といっても実際に行うのはダミーノードの直後にノードを挿入します。

そのため線形リストのときのようにリストの先頭への挿入を特別扱いする必要はありません。

挿入方法は着目ポインタcurrentの参照先をダミーノードheadにします。

この状態でメソッドaddを呼び出すことでダミーノードの直後にノードが挿入され、実質的な先頭ノードとなります。

末尾へのノードの挿入add_last

def add_last(self, data: Any) -> None:
    """末尾にノードを挿入"""
    self.current = self.head.prev  # 末尾ノードhead.prevの直後に挿入
    self.add(data)

add_lastメソッドではリストの末尾にノードを挿入します。

挿入方法は着目ポインタcurrentの参照先を末尾ノードつまりダミーノードの先行ポインタの参照先head.prevにします。

この状態でメソッドaddを呼び出すことでリストの末尾にノードが挿入されます。

着目ノードの削除remove_current_node

def remove_current_node(self) -> None:
    """着目ノードを削除"""
    if not self.is_empty():
        self.current.prev.next = self.current.next
        self.current.next.prev = self.current.prev
        self.current = self.current.prev
        self.no -= 1
        if self.current is self.head:
            self.current = self.head.next

remove_current_nodeメソッドでは着目ノードを削除します。

ダミーノードを削除するのを避けるためリストが空でないかの確認を行い、空でないときに削除します。

下の図のようにノードA、B、Cがあるとします。

ノードBが着目ノードcurrentのとき、ノードAはcurrent.prev、ノードCはcurrent.nextとなります。

このときにremove_current_nodeメソッドでノードBを削除する手順は次の通りです。

まずノードAの後続ポインタcurrent.prev.nextがノードCであるcurrent.nextを参照するようにします。

次にノードCの先行ポインタcurrent.next.prevがノードAであるcurrent.prevを参照するようにします。

こうすることでノードBはどこからも参照されなくなり、ノードAの後続ノードがノードCとなります。

着目ポインタcurrentが削除したノードの先行ノードAを参照するようにして、リストのノード数を1減らせば完了です。

任意のノードの削除remove

def remove(self, p: Node) -> None:
    """ノードpを削除"""
    ptr = self.head.next

    while ptr is not self.head:
        if ptr is p:         # pを見つけた
            self.current = p
            self.remove_current_node()
            break
        ptr = ptr.next

removeメソッドでは引数として与えられたノードpを削除します。

ただし削除するのはリストが空でなくノードpが存在するときのみです。

ptrをダミーノードの後続の実質的な先頭ノードhead.nextで初期化します。

while文ではptrが先頭ノードから順に走査していきます。

ノードpを見つけると着目ポインタをpにしてremove_current_nodeメソッドで削除します。

ptrが一巡してダミーノードにたどり着くと削除処理はされず終了します。

先頭ノードの削除remove_first

def remove_first(self) -> None:
    """先頭ノードを削除"""
    self.current = self.head.next  # 先頭ノードhead.nextを削除
    self.remove_current_node()

remove_firstメソッドではリストの先頭ノードを削除します。

ただし削除するのはダミーノードheadでなく、その後続にある実質的な先頭ノードhead.nextです。

そのため着目ポインタcurrentをhead.nextにしています。

削除処理はremove_current_nodeメソッドが行います。

末尾ノードの削除remove_last

def remove_last(self) -> None:
    """末尾ノードを削除"""
    self.current = self.head.prev  # 末尾ノードhead.prevを削除
    self.remove_current_node()

remove_lastメソッドではリストの末尾ノードを削除します。

着目ポインタcurrentを末尾ノードhead.prevにしています。

この状態で削除処理をremove_current_nodeメソッドが行います。

全ノードの削除clear

def clear(self) -> None:
    """全ノードを削除"""
    while not self.is_empty():     # リストが空になるまで
        self.remove_first()        # 先頭ノードを削除
    self.no = 0

clearメソッドではリストの全ノードを削除します。

リストが空になるまでremove_firstメソッドで先頭ノードを削除します。

最後にリストのノード数を0にします。

削除が終わると着目ポインタcurrentはダミーノードheadを参照します。

循環・重連結リストのプログラムは以下の通りです。

循環・重連結リストのプログラム

# 循環・重連結リスト

from __future__ import annotations
from typing import Any, Type

class Node:
    """循環・重連結リスト用ノードクラス"""

    def __init__(self, data: Any = None, prev: Node = None,
                 next: Node = None) -> None:
        """初期化"""
        self.data = data          # データ
        self.prev = prev or self  # 先行ポインタ
        self.next = next or self  # 後続ポインタ

class CircularDoublyLinkedList:
    """循環・重連結リストクラス"""

    def __init__(self) -> None:
        """初期化"""
        self.head = self.current = Node()   # ダミーノードを作成
        self.no = 0

    def __len__(self) -> int:
        """リスト上のノード数を返却"""
        return self.no

    def is_empty(self) -> bool:
        """リストは空か"""
        return self.head.next is self.head

    def search(self, data: Any) -> Any:
        """dataと等価なノードを探索"""
        cnt = 0
        ptr = self.head.next        # 現在走査中のノード(先頭ノード)
        while ptr is not self.head:
            if data == ptr.data:
                self.current = ptr
                return cnt          # 探索成功
            cnt += 1
            ptr = ptr.next          # 後続ノードに着目
        return -1                   # 探索失敗

    def print_current_node(self) -> None:
        """着目ノードを表示"""
        if self.is_empty():
            print('着目ノードがありません。')
        else:
            print(self.current.data)

    def print(self) -> None:
        """全ノードを表示"""
        ptr = self.head.next        # ダミーノードの後続ノード(実質的先頭ノード)
        while ptr is not self.head:
            print(ptr.data)
            ptr = ptr.next

    def print_reverse(self) -> None:
        """全ノードを逆順に表示"""
        ptr = self.head.prev        # ダミーノードの先行ノード(末尾ノード)
        while ptr is not self.head:
            print(ptr.data)
            ptr = ptr.prev

    def next(self) -> bool:
        """着目ノードを一つ後方に進める"""
        if self.is_empty() or self.current.next is self.head:
            return False    # 進めることができなかった
        self.current = self.current.next
        return True

    def prev(self) -> bool:
        """着目ノードを一つ前方に進める"""
        if self.is_empty() or self.current.prev is self.head:
            return False    # 進めることができなかった
        self.current = self.current.prev
        return True

    def add(self, data: Any) -> None:
        """着目ノードの直後にノードを挿入"""
        node = Node(data, self.current, self.current.next)
        self.current.next.prev = node
        self.current.next = node
        self.current = node
        self.no += 1

    def add_first(self, data: Any) -> None:
        """先頭にノードを挿入"""
        self.current = self.head       # ダミーノードheadの直後に挿入
        self.add(data)

    def add_last(self, data: Any) -> None:
        """末尾にノードを挿入"""
        self.current = self.head.prev  # 末尾ノードhead.prevの直後に挿入
        self.add(data)

    def remove_current_node(self) -> None:
        """着目ノードを削除"""
        if not self.is_empty():
            self.current.prev.next = self.current.next
            self.current.next.prev = self.current.prev
            self.current = self.current.prev
            self.no -= 1
            if self.current is self.head:
                self.current = self.head.next

    def remove(self, p: Node) -> None:
        """ノードpを削除"""
        ptr = self.head.next

        while ptr is not self.head:
            if ptr is p:         # pを見つけた
                self.current = p
                self.remove_current_node()
                break
            ptr = ptr.next

    def remove_first(self) -> None:
        """先頭ノードを削除"""
        self.current = self.head.next  # 先頭ノードhead.nextを削除
        self.remove_current_node()

    def remove_last(self) -> None:
        """末尾ノードを削除"""
        self.current = self.head.prev  # 末尾ノードhead.prevを削除
        self.remove_current_node()

    def clear(self) -> None:
        """全ノードを削除"""
        while not self.is_empty():     # リストが空になるまで
            self.remove_first()        # 先頭ノードを削除
        self.no = 0

このプログラムは「circular_doubly_linked_list.py」という名前で保存してください。

循環・重連結リストを利用するプログラム

コード例

# 循環・重連結リストクラスCircularDoublyLinkedListの利用例

from enum import Enum
from circular_doubly_linked_list import CircularDoublyLinkedList

Menu = Enum('Menu', ['先頭に挿入', '末尾に挿入', '着目の直後に挿入',
                     '先頭を削除', '末尾を削除', '着目を表示',
                     '着目を進める', '着目を戻す', '着目を削除',
                     '全削除', '探索', '全ノードを表示',
                     '全ノードを逆順に表示', '終了'])

def select_Menu() -> Menu:
    """メニュー選択"""
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep=' ', end='')
        n = int(input(' : '))
        if 1 <= n <= len(Menu):
            return Menu(n)

lst = CircularDoublyLinkedList()             # 循環・重連結リストを作成

while True:
    menu = select_Menu()                     # メニュー選択

    if menu == Menu.先頭に挿入:              # 先頭に挿入
        lst.add_first(int(input('値 : ')))

    elif menu == Menu.末尾に挿入:            # 末尾に挿入
        lst.add_last(int(input('値 : ')))

    elif menu == Menu.着目の直後に挿入:      # 着目の直後に挿入
        lst.add(int(input('値 : ')))

    elif menu == Menu.先頭を削除:            # 先頭を削除
        lst.remove_first()

    elif menu == Menu.末尾を削除:            # 末尾を削除
        lst.remove_last()

    elif menu == Menu.着目を表示:            # 着目を表示
        lst.print_current_node()

    elif menu == Menu.着目を進める:          # 着目を進める
        lst.next()

    elif menu == Menu.着目を戻す:            # 着目を戻す
        lst.prev()

    elif menu == Menu.着目を削除:            # 着目を削除
        lst.remove_current_node()

    elif menu == Menu.全削除:                # 全削除
        lst.clear()

    elif menu == Menu.探索:                  # 探索
        pos = lst.search(int(input('値 : ')))
        if pos >= 0:
            print(f'その値のデータは{pos + 1}番目にあります。')
        else:
            print('その値は存在しません。')

    elif menu == Menu.全ノードを表示:        # 全ノードを表示
        lst.print()

    elif menu == Menu.全ノードを逆順に表示:  # 全ノードを逆順に表示
        lst.print_reverse()

    else:                                    # 終了
        break

実行結果

(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 1
値 : 3
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 2
値 : 4
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 1
値 : 2
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 2
値 : 5
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 1
値 : 1
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 12
1
2
3
4
5
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 11
値 : 3
その値のデータは3番目にあります。
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 6
3
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 9
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 6
2
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 8
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 6
1
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 12
1
2
4
5
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 13
5
4
2
1
(1)先頭に挿入 (2)末尾に挿入 (3)着目の直後に挿入 (4)先頭を削除 (5)末尾を削除 (6)着目を表示 (7)着目を進める (8)着目を戻す (9)着目を削除 (10)全削除 (11)探索 (12)全ノードを表示 (13)全ノードを逆順に表示 (14)終了 : 14

このプログラムは「circular_doubly_linked_list_test.py」という名前で「circular_doubly_linked_list.py」と同じフォルダに保存してください。

アルゴリズム

Posted by ほりえりお