連結リスト
最終更新
連結リストはシーケンスをノードの連鎖として格納し、各ノードは値と次のノードへのポインタを保持します。配列とは異なり、ノードはメモリ上で連続していません。リストをたどるには next ポインタを追っていきます。上の再生を押すと、ノードが先頭と末尾で連結され、連鎖をたどって値が検索され、ポインタを繋ぎ変えてノードが削除される様子を見られます。
先頭への挿入や削除は O(1) です。ヘッドを繋ぎ変えるだけだからです。途中の位置や末尾に到達するのは O(n) です。まずそこまで歩く必要があるからです。このトレードオフ（端は安いがランダムアクセスがない）こそが、連結リストを配列と区別するものです。
計算量
| 操作 | 計算量 | 備考 |
|---|---|---|
| 先頭に挿入 | O(1) | ヘッドを繋ぎ変える |
| 末尾に挿入 | O(n) | まず末尾まで歩く（末尾ポインタがあれば O(1)） |
| 検索 | O(n) | next ポインタを追う |
| 先頭を削除 | O(1) | ヘッドをその先へ繋ぎ変える |
| インデックスによるアクセス | O(n) | ランダムアクセスなし |
連結リスト対配列
| 観点 | 連結リスト | 配列 |
|---|---|---|
| メモリ | 散在するノード + ポインタ | 連続したブロック |
| ランダムアクセス | O(n) | O(1) |
| 先頭への挿入/削除 | O(1) | O(n)（シフト） |
| キャッシュ親和性 | 低い | 高い |
実例
リスト [10, 20] を構築し、5 を先頭に追加してから 20 を削除する場合：
| ステップ | 構造 | 動作 |
|---|---|---|
| 開始 | head -> null | 空のリスト |
| 先頭に 10 を挿入 | head -> 10 -> null | next が旧ヘッド（null）である新ノードへヘッドを繋ぎ変える |
| 末尾に 20 を挿入 | head -> 10 -> 20 -> null | ノード 10 まで歩き、その next を新ノード 20 に設定する |
| 先頭に 5 を挿入 | head -> 5 -> 10 -> 20 -> null | 新ノード 5 が旧ヘッド 10 を指し、ヘッドは今 5 を指す |
| 20 を削除 | head -> 5 -> 10 -> null | 10 まで歩き、その next を 20 から null に設定する。ノード 20 は切り離される |
連結リストを使うべき場面
| 使うべきとき | 避けるべきとき |
|---|---|
| インデックス参照よりも、端（または保持しているノード）での挿入・削除がはるかに多いとき | 位置による高速なランダムアクセス（O(1) インデックス参照）が必要なとき |
| サイズが大きく変動し、リサイズ/コピーのコストを避けたいとき | キャッシュ局所性が性能を左右する密なループを回すとき |
| キュー、スタック、隣接リストを構築しているとき | メモリが逼迫しているとき（各ノードは要素ごとに余分なポインタを消費する） |
| 他所での挿入を生き延びる、ノードへの安定した参照が必要なとき | 主に読み取りでほとんど変更しないとき（配列の方が単純で速い） |
Linked Listのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なLinked Listの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのLinked Listのコード
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)JavaScriptでのLinked Listのコード
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));JavaでのLinked Listのコード
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}C++でのLinked Listのコード
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}CでのLinked Listのコード
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}連結リストのよくある質問
連結リストと配列の違いは何ですか？
配列は要素を1つの連続したブロックに格納するため、
O(1) のランダムアクセスができますが、要素をずらす挿入/削除は O(n) です。連結リストはノードをメモリ上の任意の場所にポインタで繋いで格納するため、既知の位置での挿入/削除は O(1) ですが、連鎖をたどる必要があるためアクセスは O(n) です。いつ連結リストを使うべきですか？
連結リストは、端（またはすでに参照を保持しているノード）での挿入・削除が頻繁で、ランダムアクセスがほとんど不要なとき、たとえばキュー、スタック、隣接リスト、LRUキャッシュで真価を発揮します。高速なインデックスアクセスが必要なら、配列や動的配列の方が通常は優れています。
連結リストの計算量はどれくらいですか？
先頭での挿入や削除は
O(1) です。検索、または末尾ポインタなしで末尾に到達するのは、next ポインタを1つずつたどるため O(n) です。O(1) のランダムアクセスはありません。連結リストへのインデックス参照は O(n) です。単方向連結リストと双方向連結リストの違いは何ですか？
単方向連結リストはノードごとに
next ポインタのみを保持するため、一方向にしかたどれず、ノードの削除には先行ノードへの参照が必要です。双方向連結リストは prev ポインタを追加し、後方へのたどりと保持中ノードの O(1) 削除を可能にしますが、ノードごとに余分なポインタが必要となり、挿入・削除のたびに管理が増えます。先頭への挿入が O(1) なのに、なぜ末尾への挿入は O(n) なのですか？
先頭への挿入は
head ポインタを繋ぎ変えるだけで、これは定数時間の作業です。末尾に到達するには、ヘッドから末尾まで next ポインタをたどる必要があり、これは O(n) です。別途 tail ポインタを保持すれば末尾への挿入も O(1) になるため、実際のリストはしばしば両端を追跡します。連結リストはどこでも O(1) で挿入できますか？
いいえ、それはよくある誤解です。挿入自体が
O(1) なのは、挿入先の直前のノードへのポインタをすでに保持している場合だけです。その位置を値やインデックスで見つけるのは、たどり着くために連鎖を歩く必要があるため、依然として O(n) かかります。関連リソース
その他の可視化
