循環リスト （Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考に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)