【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら

#8-4 循環・重連結リスト
循環・重連結リストというものについてです。
これは、前回とは違って、前に戻ったりする機能がある程度に覚えておきました。
また3章に戻って順番が来たら改めて思い出しながら勉強したいと思います。

list8-5,double_list.py

#循環・重連結リスト

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 DoubleLinkedList:
    """循環・重連結リストクラス"""
    
    def __init__(self) -> None:
        """初期化"""
        self.head = self.current = Node() #ダミーノードを作成
        self.no = 0
        
    def __len__(self) -> int:
        """線形リスト上のノード数を返却する"""
        
    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 __contains__(self, data: Any) -> bool:
        """線形リストにデータは含まれているか"""
        return self.search(data) >= 0
    
    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
        
    
    def __iter__(self) -> DoubleLinkedListIterator:
        """イテレータを返却"""
        return DoubleLinkedListIterator(self.head)
    
    def __reversed__(self) -> DoubleLinkedListReverseIterator:
        """降順イテレータを返却"""
        return DoubleLinkedListReverseIterator(self.head)
    

class DoubleLinkedListIterator:
    """DoubleLinkedListのイテレータ用クラス"""
    
    def __init__(self, head: Node):
        self.head = head
        self.current = head.next
        
    def __iter__(self) -> DoubleLinkedListIterator:
        return self
    
    def __next__(self) -> Any:
        if self.current is self.head:
            raise StopIteration
        else:
            data = self.current.data
            self.current = self.current.next
            return data
        
class DoubleLinkedListReverseIterator:
    """DoubleLinkedListの降順イテレータ用クラス"""
    
    def __init__(self, head: Node):
        self.head = head
        self.current = head.prev
        
    def __iter__(self) -> DoubleLinkedListReverseIterator:
        return self
    
    def __next__(self) -> Any:
        if self.current is self.head:
            raise StopIteration
        else:
            data = self.current.data
            self.current = self.current.prev
            return data

list8-6,double_list_test.py


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

from enum import Enum
from double_list import DoubleLinkedList

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 = DoubleLinkedList()

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.帰属性判定:
        print('その値のデータは含まれま' + ('す。'if int(input('値：'))in lst else 'せん。'))
        
    elif menu == Menu.全ノードを表示: 
        lst.print()
    
    elif menu == Menu.全ノードを逆順に表示: 
        lst.print_reverse()
        
    elif menu == Menu.走査:
        for e in lst:
            print(e)
    elif menu == Menu.逆走査:
        for e in reversed(lst):
            print(e)
    else:
        break

コラム8-3 Pythonの代入について

pythonの場合
self.current.next = self.current.next.prev = node
というようなコードがあった場合
pythonでは正しく動作しません。(CやJavaと比較すると代入順序が逆になるようです)

今回はさらっと流しますが、また改めて学習したいと思います。

以上ですありがとうございました。