エンジニア実践的基礎: 単方向リスト

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

単方向リストとは

単方向リストのイメージは電車です。電車は複数台の車両が連結されています。

車両イメージには3台の車両が連結されています。この電車は特殊な電車で、左から右にしか移動できません。つまり、1 → 2 → 3 の順に移動できます。この移動制限が「単方向」つまり一方方向にしかデータを参照できないことを示します。

正確には車両を「ノード」と呼びます。ノードは「値」と「次のノードの参照」を持ちます。参照は連結部分のことです。末尾ノードは次のノードが無いので参照を持ちません。

ノードの追加

ノードの追加は単純です。新しいノードを作成して末尾のノードの参照に設定するだけです。

興味深いのはリストの途中にもノードを簡単に追加できることです。イメージではノード1とノード2の間にノード1.5 を追加しています。もちろん、追加箇所の一つ前のノードの場所を事前に知っている必要があります。この場合、ノード1 の場所がわかっている必要があります。

配列の場合、途中にデータを追加すると以降のノードをすべて右にシフトする必要があります。最悪のケースで n - 1 回の右シフトするので計算量は O(n) です。一方で単方向リストは右シフトが不要で、参照ノードを変更するだけなので、O(1) の計算量でノードを追加できます。

ノードの削除

ノードの削除は削除対象のノードを連結から外すだけです。削除ノードの前のノードが、削除ノードの次のノードを参照します。言葉では伝わりにくいですが、画像を見れば理解できるはずです。

ノードの参照

ここまで単方向リストのメリットが目立ちましたが、当然デメリットもあります。単方向リストの仕様上、最大で次のノードまでしか参照できません。そのため、２つ隣のノードを参照するには２回のノードを走査する必要があります。電車の例えでは、1 → 2 → 3 と車両1から車両3へ2回車両を渡る必要があります。そのため n 個の非常に長い単方向リストの先頭から末尾まで移動するのに最悪で n - 1 回の走査になり、計算量は O(n) になります。

配列の場合、現在のインデックスから相対的なインデックスを計算できるので、目的のデータを O(1) で参照できます。例えば、インデックス3の2つ隣のデータはインデックス5です。

実装例

class Node:
    """
    単方向リンクリストのノード
    """
    def __init__(self, data):
        self.data = data
        self.next = None

# ノードの作成
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

# ノードの追加
node1.next = node2
node2.next = node3

計算量

まとめ

単方向リストはこのように追加や削除を柔軟にシンプルにできるデータ構造です。現段階では便利さがわかりにくいと思いますが、今後いろいろな応用例を学べば有用性に気づくはずです。単方向リストを忘れたら「一方方向にしか車内を移動できない電車」を思い出してください。