【出典】「新・明解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と比較すると代入順序が逆になるようです)
今回はさらっと流しますが、また改めて学習したいと思います。
以上ですありがとうございました。