Engineering Note

プログラミングなどの技術的なメモ

連結リスト (Pythonによるアルゴリズムとデータ構造)

linked list

本記事は、ソフトバンクパブリッシングから発行されている「定本 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を削除して、きちんとデータの連結処理が出来ている確認をしています。

 

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)