連結リストとは？仕組み・コード・計算量をわかりやすく解説

連結リストが解決する問題

配列（Pythonのlist）は要素を連続したメモリ領域に置きます。a[i]の読み取りは一瞬ですが、先頭への挿入では他のすべての要素を1つ右にずらす必要があり、O(n)かかります。連結リストではこのずらしが不要です。各要素が独立したノードに入っていて、ノード同士は参照でつながっているため、挿入時に書き換えるのは数個の参照だけです。

連結リストは、スタック、キュー、ハッシュテーブルのバケット（チェイン法）、LRUキャッシュ、グラフの隣接リストなど、多くのデータ構造の土台になっています。

イメージで理解する

宝探しゲームを思い浮かべてください。各ヒントは次のヒントの場所を教えてくれます。7番目のヒントに直接ジャンプすることはできず、1番から6番まで順にたどる必要があります。リスト自身が覚えているのは最初のノード（先頭、head）だけで、最後のノードは何も指しません（None）。

具体例：挿入と削除

3 -> 7 -> 9というリストから始めます。3の後ろに5を挿入し、その後7を削除します。

1. 値5を持つ新しいノードを作ります。
2. new.nextを、3の次にあるノード（7のノード）に設定します。
3. node3.nextを新しいノードに設定します。これでリストは3 -> 5 -> 7 -> 9になります。
4. 7を削除するには、先頭からたどって、その前のノード（5）を見つけます。
5. node5.next = node5.next.nextと設定すると、7が飛ばされます。リストは3 -> 5 -> 9になります。到達できなくなったノードは、Pythonのガベージコレクタが解放します。

単方向連結リストのPython実装

このクラスは、先頭への参照とサイズのカウンタを持ちます。先頭・末尾への追加、最初に一致した値の削除、イテレーションに対応しています。

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1
    def push_back(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
        self.size += 1
    def remove(self, value):
        prev, cur = None, self.head
        while cur and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False          # not found
        if prev is None:
            self.head = cur.next  # removing the head
        else:
            prev.next = cur.next
        self.size -= 1
        return True
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next

items = LinkedList()
for x in [3, 7, 9]:
    items.push_back(x)
items.push_front(1)
items.remove(7)
print(list(items), items.size)  # [1, 3, 9] 3

push_backはここではリスト全体をたどるため、O(n)です。追加のtail参照を持てばO(1)になり、実際のキュー実装ではそのようにしています。

代表的な操作：反転と循環検出

リストをその場で反転する問題は、連結リストの面接で最もよく出る問題です。リストを1回たどり、各nextポインタの向きを逆にします。

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next     # remember the rest
        cur.next = prev    # turn the pointer around
        prev, cur = cur, nxt
    return prev            # new head
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
head = Node(1, Node(2, Node(3)))
head = reverse(head)
print(head.value, head.next.value, head.next.next.value)  # 3 2 1
print(has_cycle(head))  # False

has_cycleはフロイドの「亀と兎」アルゴリズムです。遅いポインタは1ステップ、速いポインタは2ステップずつ進みます。ループがあれば、速いポインタはいずれ遅いポインタに追いつき、なければNoneに到達します。追加のメモリはO(1)で済みます。

時間計算量と空間計算量

実際には、連結リストのほうがオーダー（ビッグO）で有利な操作でも、配列のほうが速いことがよくあります。配列の要素はメモリ上で隣り合っていてCPUキャッシュを効率よく使えるのに対し、連結リストのノードは散らばっているためです。

種類と、よくある間違い

• 空のリストを忘れる：head.nextを読む前に、必ずhead is Noneを確認します。
• nextを保存する前に上書きして、リストの残りを失う（reverseのnxtを参照）。
• 最初のノードを削除したときにheadを、最後のノードを削除したときにtailを更新し忘れる。
• 非常に長いリストで再帰を使う：Pythonのデフォルトの再帰上限は約1000フレームなので、反復で書くほうが安全です。
• ダミー（番兵）の先頭ノードを置くと、特殊ケースの大半がなくなります。実データのノードがすべて前のノードを持つようになるためです。
• 双方向連結リストでは、挿入・削除のたびに4つの参照を更新する必要があります。1つでも漏れると、気づかないうちにリストが壊れます。

連結リストを使う場面と、Pythonでの選択肢

連結リストが向いているのは、すでに参照を持っている位置で、端や途中への挿入・削除を行い、ランダムアクセスをほとんど必要としない場合です。例として、LRUキャッシュ（双方向連結リストとハッシュマップ）、メモリアロケータのフリーリスト、元に戻す（undo）履歴、ハッシュテーブルのバケットがあります。

普段のPythonコードで自作することはまずありません。キューやデックには、両端でO(1)の追加・取り出しができるcollections.dequeを使います。一般的なシーケンスにはlistを使います。自作の連結リストが役に立つのは、学習や面接、そしてLRUキャッシュのようにノードをO(1)で付け替えたい場合です。

from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)
q.append(4)
print(q.popleft(), q.pop(), list(q))  # 0 4 [1, 2, 3]