本記事は、ソフトバンクパブリッシングから発行されている「」を参考に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を削除して、きちんとデータの連結処理が出来ている確認をしています。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
