本記事は、ソフトバンクパブリッシングから発行されている「」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、連結リストをリング状に繋ぎ合わせた循環リスト（Circular List）について学んでいきます。
循環リストとは
連結リストでは先頭から次の要素を順番に辿っていき、最終的に要素の最後に辿り着いたときは、その要素が指す次の要素はNULLで終端されています。
循環リスト（Circular List）では、最後の要素が指す次の要素を、リストの先頭にすることで循環させる仕組みをとります。
循環リストの性質
連結リストでは、リストの先頭から辿っていかなければ、リスト全体にはアクセスすることができません。
しかし、循環リストではリストの途中から探索を実行しても、リスト全体にアクセスすることが可能となります。
また、連結リストでは最終的に次の要素がNULLであることがリストの終端を意味していましたが、循環リストでは探索を開始したリストを別の変数に代入して置き、次の要素と比較をすることで、リスト全体を1周したかどうか判断します。
Pythonで循環リストを作ってみる
それでは、Pythonで循環リストを実装してみます。
# circular_list.py
class Cell:
def __init__(self, value):
self.value = value
self.next = None
class CircularList:
def __init__(self):
self.head = None
def insert(self, value):
new = Cell(value)
if not self.head:
self.head = new
new.next = new
return
tmp = self.head
while not tmp.next == self.head:
tmp = tmp.next
tmp.next = new
new.next = self.head
def delete(self, value):
if not self.head:
print("[*] List is empty.")
return
if self.head == self.head.next:
self.head = None
return
if self.head.value == value:
tmp = self.head
self.head = tmp.next
tmp = None
return
front = self.head
rear = front.next
isfound = False
while not rear == self.head:
if rear.value == value:
isfound = True
break
front = rear
rear = rear.next
if isfound:
front.next = rear.next
rear = None
else:
print("[*] Data not found")
def show(self):
tmp = self.head
if tmp:
while tmp:
print(tmp.value)
tmp = tmp.next
if tmp == self.head:
break
else:
print('[*] List is empty.')
l = CircularList()
print('insert 1, 2, 3...')
l.insert(1)
l.insert(2)
l.insert(3)
print('print data')
l.show()
print('delete 2...')
l.delete(2)
print('print data')
l.show()
今回はリストの頭を用いない循環リストで、リストが空の場合はリストの先頭をNoneとしています。
動作確認
それでは上記で作成したスクリプトを実行してみます。
>python circular_list.py insert 1, 2, 3... print data 1 2 3 delete 2... print data 1 3
まず、1、2、3のデータを挿入し、その後データが挿入されているか確認します。
最後に真ん中にあたる2を削除して、きちんとデータの削除及びつなぎ合わせが出来ているか確認をしています。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
