本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、データ構造としてリストを繋ぎ合わせた連結リスト(Linked List)について学んでいきます。
連結リストとは
連結リスト(Linked List)とは、リストに含まれる各要素を繋ぎ合わせたデータ構造を言います。
自分の次(もしくは前)のリスト情報を保持することによって、データの探索、挿入および削除の一連の処理が可能になります。
通常のリスト(配列)では、インデックス(添え字)を指定することで、対象のデータにアクセスすることができ、その計算量はO(1)になります。
なお、リストのようなデータ構造ではランダムアクセスが可能となります。
一方連結リストでは、先頭のリストから順番に辿っていくため、その計算量はO(n)となり、シーケンシャルアクセスしかできません。
しかし連結リストを使うことで、データの挿入や削除がとても簡単に実行することが出来ます。
またC言語では、データ挿入が必要な場合はmalloc()で動的にメモリを確保し、データ削除の場合はfree()でそのメモリ領域を解放できるため、効率的にメモリを管理することが出来ます。
Pythonで連結リストを作ってみる
それでは、Pythonで連結リストを実装してみます。
# linked_list.py class Cell: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = Cell(None) def insert(self, value): front = self.head rear = front.next while rear and value > rear.value: front = rear rear = rear.next cell = Cell(value) cell.next = rear front.next = cell def delete(self, value): front = self.head rear = front.next while rear: if rear.value == value: break front = rear rear = rear.next if not rear: print("[*] Data not found") return front.next = rear.next rear = None def show(self): tmp = self.head.next while tmp: print(tmp.value) tmp = tmp.next l = LinkedList() print('insert 3, 5, 1...') l.insert(3) l.insert(5) l.insert(1) print('print data') l.show() print('delete 3...') l.delete(3) print('print data') l.show()
LinkedListクラスでは、初期化でNoneデータの入ったCellクラスオブジェクトを作成します。
このようにリストの先頭に空のダミーを置くことで、後の挿入や削除の操作が若干楽になります。
また今回は、無雑作にデータを連結していくのではなく、数値を昇順で挿入するようにしました。
動作確認
それでは上記で作成したスクリプトを実行してみます。
>python linked_list.py insert 3, 5, 1... print data 1 3 5 delete 3... print data 1 5
まず、3、5、1の順番でデータを挿入し、その後データが昇順で挿入されている確認します。
最後に真ん中にあたる3を削除して、きちんとデータの連結処理が出来ている確認をしています。