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

背景

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

双方向リストとは

前回の単方向リストを理解できれば、双方向リストは簡単です。名前の通り、前後のノードへの参照を持ちます。単方向リストは次のノードの参照だけでした。

双方向リストイメージ

後ろのノードも簡単に走査できるのがメリットです。ただし挿入や削除時に後ろのノードへの参照を設定するのを忘れないように気をつけてください。

実装

class Node:
    """
    双方向リンクリストのノード
    """
    def __init__(self, data):
        self.data = data
        self.prev = None # 前のノードの参照
        self.next = None

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

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

計算量