双方向連結リスト

Q: 単方向連結リストと双方向連結リストの違いは何ですか?

単方向連結リストはノードごとにポインタが1つ(`next`)なので、前方にしか進めません。双方向連結リストは `prev` ポインタを追加し、後方へのたどりや、参照を持つノードの `O(1)` での削除を可能にします。その代償として、ノードごとに余分なポインタが1つ増え、変更のたびに2つのリンクを更新する必要があります。

Q: 双方向連結リストが余分なメモリに見合うのはいつですか?

後方へのたどりや、すでに参照している任意のノードの `O(1)` 削除が必要なときです。典型例はデック(両端キュー)と LRU キャッシュで、エントリが両端で頻繁に移動・追い出しされます。

Q: 双方向連結リストと配列、どちらを使うべきですか?

インデックスによる `O(1)` アクセスやキャッシュに優しい反復が必要で、挿入が主に末尾で行われる場合は配列を使います。ノード参照がある状態で中間や両端に頻繁に挿入・削除する場合は双方向連結リストを使います。これは配列の `O(n)` のシフトに対して `O(1)` だからです。配列はメモリと局所性で勝り、リストは構造的な編集で勝ります。

Q: 双方向連結リストにおける番兵(sentinel)ノードとは何ですか?

番兵(またはダミー)ノードは、リストが本当に空になることがないように、先頭の前や末尾の後に置くプレースホルダです。`head`、`tail`、境界での挿入/削除に関する `null` チェックを取り除き、すべての操作を同じつなぎ直しのコード経路に従わせます。多くの実運用の LRU キャッシュ実装では、両端を特別扱いしないために2つの番兵を使います。

Q: 双方向連結リストからの削除で最もよくあるバグは何ですか?

先頭または末尾のノードを削除するときに `head` や `tail` の更新を忘れることで、解放されたノードへのダングリングポインタが残ります。隣接ノードをつなぎ直す前に、`node.prev` が `null` か(`head` を更新)、`node.next` が `null` か(`tail` を更新)を必ず確認してください。

最終更新 2026年7月1日

双方向連結リストは、各ノードが2つのポインタを持つ連結リストです: next(次のノードへ)と prev(前のノードへ)。この余分な後方リンクにより、両方向へたどることができ、すでに参照を持っているノードを O(1) で削除できます。先頭からたどらずに、直接その前のノードへ到達できるからです。上の再生ボタンを押すと、ノードが両方向へつながり、つなぎ直される様子を確認できます。

その代償は、ノードごとに1つ余分なポインタと、より多くの管理です。挿入と削除のたびに、隣接ノードの next と prev の両方を更新しなければなりません。これは、両端からの高速な削除が重要となる多くのデック(deque)や LRU キャッシュの背後にある構造です。

時間計算量

操作	計算量	備考
先頭/末尾への挿入	O(1)	先頭と末尾のポインタがある場合
既知のノードの削除	O(1)	prev に直接到達、走査なし
探索	O(n)	依然として線形走査
インデックスによるアクセス	O(n)	ランダムアクセス不可

単方向連結リストと双方向連結リストの比較

観点	単方向	双方向
ノードあたりのポインタ	1 (next)	2 (next + prev)
後方へのたどり	不可	可
既知のノードの削除	O(n) (prev を探す)	O(1)
メモリのオーバーヘッド	低い	高い

具体例で追う

末尾に追加して [10, 20, 30] を作り、その後ノード 20 を削除する:

ステップ	構造	動作
開始	`null`	空のリスト: `head` と `tail` はどちらも `null`
10 を追加	`10`	最初のノード。`head` と `tail` がこれを指し、`prev` = `next` = `null`
20 を追加	`10 <-> 20`	`10.next = 20` と `20.prev = 10` を設定。`tail` = `20`
30 を追加	`10 <-> 20 <-> 30`	`20.next = 30` と `30.prev = 20` を設定。`tail` = `30`
20 を削除	`10 <-> 30`	`20.prev` と `20.next` を使い、`10.next = 30` と `30.prev = 10` を `O(1)` で設定

双方向連結リストを使うべき場面

使うべき場面	避けるべき場面
両方向にたどる、または継ぎ足す必要がある	前方にしか進まない: 単方向リストの方が軽量
すでに参照を持つ任意のノードを削除する (`O(1)`)	主に位置でインデックスする: `O(1)` アクセスには配列を使う
デック、LRU キャッシュ、取り消し履歴を実装する	メモリが逼迫している: 余分な `prev` ポインタがリンクのオーバーヘッドを倍増させる
挿入と削除が両端で頻繁に発生する	データが小さくめったに変わらない: 配列のコピーの方が安い

Doubly Linked Listのコード

Python, JavaScript, Java, C++, Cによるクリーンで実行可能なDoubly Linked Listの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。

PythonでのDoubly Linked ListのコードPython
1class Node:2    def __init__(self, value):3        self.value = value4        self.prev = None5        self.next = None6
7
8class DoublyLinkedList:9    def __init__(self):10        self.head = None11        self.tail = None12
13    def append(self, value):14        node = Node(value)15        if self.tail is None:16            self.head = self.tail = node17            return18        # Wire both directions: old tail <-> new node19        node.prev = self.tail20        self.tail.next = node21        self.tail = node22
23    def prepend(self, value):24        node = Node(value)25        if self.head is None:26            self.head = self.tail = node27            return28        node.next = self.head29        self.head.prev = node30        self.head = node31
32    def forward(self):33        values, current = [], self.head34        while current:35            values.append(current.value)36            current = current.next37        return values38
39    def backward(self):40        values, current = [], self.tail41        while current:42            values.append(current.value)43            current = current.prev44        return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49    lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())
このコードをPythonプレイグラウンドで実行

JavaScriptでのDoubly Linked ListのコードJavaScript
1class Node {2    constructor(value) {3        this.value = value;4        this.prev = null;5        this.next = null;6    }7}8
9class DoublyLinkedList {10    constructor() {11        this.head = null;12        this.tail = null;13    }14
15    // Tail pointer makes append O(1)16    append(value) {17        const node = new Node(value);18        if (!this.tail) {19            this.head = node;20            this.tail = node;21            return;22        }23        node.prev = this.tail;24        this.tail.next = node;25        this.tail = node;26    }27
28    forward() {29        const out = [];30        for (let n = this.head; n; n = n.next) out.push(n.value);31        return out;32    }33
34    backward() {35        const out = [];36        for (let n = this.tail; n; n = n.prev) out.push(n.value);37        return out;38    }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));
このコードをJavaScriptプレイグラウンドで実行

JavaでのDoubly Linked ListのコードJava
1public class Main {2    static class Node {3        int value;4        Node prev, next;5        Node(int value) { this.value = value; }6    }7
  static Node head, tail;9
  static void append(int value) {11        Node node = new Node(value);12        if (head == null) { head = tail = node; return; }13        node.prev = tail;14        tail.next = node;15        tail = node;16    }17
  // Unlink in O(1) once found: fix both neighbor pointers19    static void delete(int value) {20        for (Node cur = head; cur != null; cur = cur.next) {21            if (cur.value != value) continue;22            if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23            if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24            return;25        }26    }27
  public static void main(String[] args) {29        append(1);30        append(2);31        append(3);32        append(4);33
      StringBuilder forward = new StringBuilder("Forward:");35        for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36        System.out.println(forward);37
      StringBuilder backward = new StringBuilder("Backward:");39        for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40        System.out.println(backward);41
      delete(3);43        StringBuilder after = new StringBuilder("After delete 3:");44        for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45        System.out.println(after);46    }47}
このコードをJavaプレイグラウンドで実行

C++でのDoubly Linked ListのコードC++
1#include <iostream>2
3struct Node {4    int value;5    Node* prev = nullptr;6    Node* next = nullptr;7    explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11    Node* head = nullptr;12    Node* tail = nullptr;13
14    void append(int value) {15        Node* node = new Node(value);16        if (tail == nullptr) {17            head = tail = node;18            return;19        }20        node->prev = tail;  // link both directions21        tail->next = node;22        tail = node;23    }24
25    void prepend(int value) {26        Node* node = new Node(value);27        if (head == nullptr) {28            head = tail = node;29            return;30        }31        node->next = head;32        head->prev = node;33        head = node;34    }35
36    void printForward() const {37        for (Node* cur = head; cur != nullptr; cur = cur->next) {38            std::cout << cur->value << " <-> ";39        }40        std::cout << "null\n";41    }42
43    void printBackward() const {44        for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45            std::cout << cur->value << " <-> ";46        }47        std::cout << "null\n";48    }49};50
51int main() {52    DoublyLinkedList list;53    for (int value : {10, 20, 30}) list.append(value);54    list.prepend(5);55    std::cout << "Forward:  ";56    list.printForward();57    std::cout << "Backward: ";58    list.printBackward();59    return 0;60}
このコードをC++プレイグラウンドで実行

CでのDoubly Linked ListのコードC
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5    int value;6    struct Node* prev;7    struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14    Node* n = calloc(1, sizeof(Node));15    n->value = value;16    return n;17}18
19void append(int value) {20    Node* node = newNode(value);21    if (tail == NULL) {22        head = tail = node;23        return;24    }25    node->prev = tail;  // link both directions26    tail->next = node;27    tail = node;28}29
30void prepend(int value) {31    Node* node = newNode(value);32    if (head == NULL) {33        head = tail = node;34        return;35    }36    node->next = head;37    head->prev = node;38    head = node;39}40
41void printForward(void) {42    for (Node* cur = head; cur != NULL; cur = cur->next) {43        printf("%d <-> ", cur->value);44    }45    printf("NULL\n");46}47
48void printBackward(void) {49    for (Node* cur = tail; cur != NULL; cur = cur->prev) {50        printf("%d <-> ", cur->value);51    }52    printf("NULL\n");53}54
55int main(void) {56    int values[] = {10, 20, 30};57    for (int i = 0; i < 3; i++) append(values[i]);58    prepend(5);59    printf("Forward:  ");60    printForward();61    printf("Backward: ");62    printBackward();63    return 0;64}
このコードをCプレイグラウンドで実行

双方向連結リストのよくある質問

単方向連結リストと双方向連結リストの違いは何ですか?

単方向連結リストはノードごとにポインタが1つ(next)なので、前方にしか進めません。双方向連結リストは prev ポインタを追加し、後方へのたどりや、参照を持つノードの O(1) での削除を可能にします。その代償として、ノードごとに余分なポインタが1つ増え、変更のたびに2つのリンクを更新する必要があります。

双方向連結リストが余分なメモリに見合うのはいつですか?

後方へのたどりや、すでに参照している任意のノードの O(1) 削除が必要なときです。典型例はデック(両端キュー)と LRU キャッシュで、エントリが両端で頻繁に移動・追い出しされます。

なぜ双方向連結リストはノードを O(1) で削除できるのですか?

ノードを取り除くには、その前のノードと次のノードをつなぐ必要があります。単方向連結リストでは前のノードを見つけるために先頭からたどる必要があります(O(n))が、双方向連結リストではノードの prev ポインタが前のノードを直接与えるため、つなぎ直しは O(1) です。

双方向連結リストと配列、どちらを使うべきですか?

インデックスによる O(1) アクセスやキャッシュに優しい反復が必要で、挿入が主に末尾で行われる場合は配列を使います。ノード参照がある状態で中間や両端に頻繁に挿入・削除する場合は双方向連結リストを使います。これは配列の O(n) のシフトに対して O(1) だからです。配列はメモリと局所性で勝り、リストは構造的な編集で勝ります。

双方向連結リストにおける番兵(sentinel)ノードとは何ですか?

番兵(またはダミー)ノードは、リストが本当に空になることがないように、先頭の前や末尾の後に置くプレースホルダです。head、tail、境界での挿入/削除に関する null チェックを取り除き、すべての操作を同じつなぎ直しのコード経路に従わせます。多くの実運用の LRU キャッシュ実装では、両端を特別扱いしないために2つの番兵を使います。

双方向連結リストからの削除で最もよくあるバグは何ですか?

先頭または末尾のノードを削除するときに head や tail の更新を忘れることで、解放されたノードへのダングリングポインタが残ります。隣接ノードをつなぎ直す前に、node.prev が null か(head を更新)、node.next が null か(tail を更新)を必ず確認してください。