配列は先頭への追加が数百倍遅くなります。連結リストと並べて実測し、入れ物の選び方を決めます。
これは【深掘り】の記事です。本線の順路ではありません。 上から順に読み進めている方は、ここを飛ばして次の本線記事へ進んで構いません。 本線でデータ構造を最初に触るのは 配列は先頭への挿入が遅い — データ構造を自作する です。この深掘りは、その回で「遅い」と書いただけで終わらせた部分を、実測の数字まで降りて確かめ直す回です。
この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows本体の PowerShell では打ちません。VMへの入り方は VMを29台溜めた話 — Ubuntu Serverの立て方 と nanoで書き続けるのは無理 — VS CodeからVMを直接編集する にあります。 使うのは Node.js だけです。ネットワークにも他のサーバーにも触りません。
自分がやらかした話から始めます。
ログを溜めて、新しいものを上に表示したかったので、こう書きました。
logs.unshift(newLog); // 先頭に入れる
これで新着が常に logs[0] に来ます。動きました。テストも通りました。
そのあと、過去ログ1万件をまとめて読み込む処理を足しました。同じ関数を1万回呼んだだけです。
固まりました。
正確には固まっていません。終わるまで数秒かかっていたのですが、その間ブラウザは何も返さないので、体感は「固まった」でした。おかしいのは、同じ1万件を push で入れていたときは一瞬で終わっていたことです。
logs.push(newLog); // 末尾に入れる → 一瞬
logs.unshift(newLog); // 先頭に入れる → 数秒
やっていることは「配列に1件足す」で同じに見えます。書き方も1単語しか違いません。それで数千倍違う理由は、JavaScript の書き方の問題ではなく、配列というものがメモリにどう置かれているかの問題でした。
そして、そこを調べていて逆向きにも驚きました。「じゃあ先頭への追加が速い連結リストにすればいい」と思って書き換えたら、別のところが遅くなったのです。教科書には「全走査はどちらも O(n)」と書いてあるのに、実測すると配列のほうが数倍速い。
この記事は、その両方を自分の手で測ります。
対象レベル: 中級〜上級 / 区分: 発展
この記事でわかること
- データ構造とは「データの置き方」の決定であり、置き方を決めた瞬間に「どの操作が速いか」も決まってしまう。あとから速くする余地はほとんど残らない
- 配列の
arr[500000]が一瞬なのは検索しているからではなく、「先頭アドレス + 添字 × 1要素の大きさ」という足し算1回でその場所に行けるから - JavaScript の配列が自動で伸びるのは魔法ではなく、裏で「いっぱいになったら2倍の場所を取り直して全部コピー」している。だから
pushは「たまにすごく重い」 - 1回あたりは重いのに、平均すると O(1) になるという考え方(償却計算量)が、コピー回数を数えると数字で見える
- 連結リストは先頭への追加が O(1) だが、「n番目を取る」は O(n)。配列とちょうど得意・苦手が裏返っている
- 計算量の表だけを見て選ぶと外す。同じ O(n) でも、メモリ上に連続して並んでいる配列のほうが CPU キャッシュに乗るので実測は数倍速い
- 結論として、迷ったら配列でよい。連結リストを選ぶ理由はかなり限定される
この記事でやること
- VMの中に
~/cslab/listを作り、Node.js のバージョンを確かめる pushとunshiftを10万回ずつ回して、先頭への追加が何倍遅いかを実測する- 動的配列(自動で伸びる配列)を自分で実装し、「2倍に取り直して全部コピー」が何回起きたかを数える
- 単方向・双方向の連結リストを自分で書く(
push/unshift/insertAfter/remove/get) - 同じ O(n) の全走査を配列と連結リストで比べ、教科書どおりにならないことを実測する
- 操作ごとの判断表を、計算量と実測の両方を入れて1枚に落とす
- 実務で連結リストが顔を出す場所を確認し、
~/cslab/listを消す
先に知る言葉
基本的な言葉は用語集にもまとめてあります。
| 言葉 | この記事での意味 |
|---|---|
| データ構造 | データをメモリのどこにどう置くかの決め方。置き方が決まると、できる操作の速さも決まる |
| 配列(array) | 同じ大きさの箱がメモリ上に連続して並んでいるもの。添字で一発で場所が出る |
| 連結リスト(linked list) | 値と「次はここ」という矢印を1組にしたもの(ノード)を、鎖のように繋いだもの。メモリ上では散らばっていてよい |
| ノード | 連結リストの1個分。「値」と「次への矢印」の組 |
| 参照(reference) | 「そのノードそのもの」を指す変数。添字(何番目か)とは別物 |
| 計算量 / O記法 | データが n 件のとき、手数が n にどう比例して増えるかの表し方。O(1) は件数に関係なく一定、O(n) は件数に比例 |
| 償却計算量 | ならした計算量。1回だけ重い処理があっても、回数で割ると軽いときに使う |
| 動的配列 | 満杯になると自動で大きく取り直す配列。JavaScript の Array はこれ |
| CPUキャッシュ | CPU の中にある小さくて速いメモリ。近くのデータをまとめて持ってくるので、連続して並んでいるデータに強い |
| キャッシュミス | 欲しいデータがキャッシュに無く、遅いメインメモリまで取りに行くこと |
O記法そのものが初めてなら、先に 1万件で100倍になる — 計算量とO記法を測る を読んでからのほうが早いです。この記事は「O記法は読める」前提で、その表が現実と合わない場面を扱います。
① 準備 — 作業場所を作り、Node.js を確かめる
VMにログインした状態で始めます。
/home/<ユーザー名>/cslab/list と出れば、いる場所は合っています。
Node.js が入っているか確かめます。
v20.x.x のようにバージョンが出れば大丈夫です。command not found と出たら入っていないので、入れます。
apt はUbuntuのパッケージ管理コマンドで、sudo は「管理者の権限で1回だけ実行する」という意味です。
apt から入る Node.js は、Ubuntu のバージョンによっては古いことがあります。 この記事で使うのは performance.now() と class だけなので、v16 以上なら問題ありません。バージョンが v14 未満だった場合だけ、新しいものを入れ直してください。
この記事の測定は、動く Node.js が1つあれば足ります。 ライブラリは1つも入れません。npm install はしません。
📷 スクリーンショット①:
node --versionの出力とpwdの出力が一緒に写っている画面。あとで「どの環境で測った数字か」を自分で確認できるようにするためです。測定の記事は、環境が書いていないと数字が意味を持ちません。
計測に使う関数を先に1つだけ用意します。エディタで bench.mjs を作り、次の内容を入れます。
// bench.mjs
// 引数の関数を1回実行して、かかったミリ秒を返すだけの道具
export function measure(label, fn) {
const start = performance.now();
const result = fn();
const ms = performance.now() - start;
console.log(`${label.padEnd(34)} ${ms.toFixed(2)} ms`);
return { ms, result };
}
performance.now() は、ミリ秒より細かい時刻を返します。Date.now() はミリ秒単位で、しかもシステムの時計変更に影響されるので、処理時間の計測には向きません。
.mjs という拡張子にしているのは、import / export をそのまま使うためです。 .js にすると Node.js は CommonJS として読もうとして Cannot use import statement outside a module で落ちます。
ファイルを作るのは nano でも VS Code でも構いません。この記事はファイルを9個作るので、まとめて編集できるエディタのほうが圧倒的に楽です。
② 配列 — 添字アクセスが速い理由は「足し算1回」
まず、なぜ arr[500000] が一瞬なのかをはっきりさせます。
配列は、同じ大きさの箱がメモリ上に隙間なく連続して並んでいるものです。ここが全部の出発点です。
メモリのアドレス: 1000 1008 1016 1024 1032 1040
配列の中身: [ 10 ][ 20 ][ 30 ][ 40 ][ 50 ][ 60 ]
添字: 0 1 2 3 4 5
1要素が8バイトだとすると、添字 3 の要素があるアドレスは、こう出ます。
1000 + 3 × 8 = 1024
先頭アドレス + 添字 × 1要素の大きさ。掛け算1回と足し算1回です。 探していません。前から数えてもいません。だから 添字が 0 でも 500000 でも、かかる時間は同じです。これが O(1) の意味です。
そして、ここから苦手なほうも自動的に決まります。
先頭に1個入れたいとします。添字 0 に新しい値を置きたい。しかし添字 0 の箱にはもう 10 が入っていて、その隣も詰まっています。空けるには、後ろの全員を1つずつ後ろにずらすしかありません。
入れる前: [ 10 ][ 20 ][ 30 ][ 40 ][ 50 ]
ずらす: [ ][ 10 ][ 20 ][ 30 ][ 40 ][ 50 ]
入れる: [ 5 ][ 10 ][ 20 ][ 30 ][ 40 ][ 50 ]
n 件入っていたら n 件動かします。これが O(n) です。 そして1万回それをやると、動かす回数の合計は 1 + 2 + 3 + … + 10000 で、約5000万回になります。自分が「固まった」と思ったのは、これでした。
実測する
数字にします。01-push-unshift.mjs を作ります。
// 01-push-unshift.mjs
import { measure } from './bench.mjs';
const N = 100_000;
measure(`push を ${N} 回`, () => {
const arr = [];
for (let i = 0; i < N; i++) arr.push(i);
return arr.length;
});
measure(`unshift を ${N} 回`, () => {
const arr = [];
for (let i = 0; i < N; i++) arr.unshift(i);
return arr.length;
});
走らせます。
自分の環境(VMware 上の Ubuntu Server、2 vCPU)ではこうなりました。
push を 100000 回 3.41 ms
unshift を 100000 回 1842.67 ms
約540倍です。 同じ「1件足す」で、片方は3ミリ秒、片方は1.8秒。
数字はそのまま真似しないでください。 マシン、Node.js のバージョン、そのときの CPU の空き具合で変わります。大事なのは「540倍」という比率と、次に確かめる「件数を増やしたときの伸び方」です。
件数を変えて、伸び方を見る
O(n) と O(1) の違いは、件数を2倍にしたとき何倍になるかを見ればはっきりします。02-scaling.mjs を作ります。
// 02-scaling.mjs
import { measure } from './bench.mjs';
for (const N of [10_000, 20_000, 40_000, 80_000]) {
measure(`push N=${N}`, () => {
const arr = [];
for (let i = 0; i < N; i++) arr.push(i);
});
}
console.log('');
for (const N of [10_000, 20_000, 40_000, 80_000]) {
measure(`unshift N=${N}`, () => {
const arr = [];
for (let i = 0; i < N; i++) arr.unshift(i);
});
}
出た数字です。
push N=10000 0.52 ms
push N=20000 0.94 ms
push N=40000 1.71 ms
push N=80000 2.88 ms
unshift N=10000 19.84 ms
unshift N=20000 76.12 ms
unshift N=40000 301.55 ms
unshift N=80000 1203.90 ms
読み方はここです。
pushは件数が2倍になると時間も約2倍。1回あたりは一定なので、n 回やれば n 倍 → 1回は O(1)unshiftは件数が2倍になると時間が約4倍。1回が O(n) のものを n 回やっているので、合計は O(n²)
「4倍になる」を目で見たら、それはもう O(n²) です。 表を暗記する必要はなく、件数を倍にして測れば自分で判定できます。
📷 スクリーンショット②: この
02-scaling.mjsの出力全体。unshiftの列が 19 → 76 → 301 → 1203 と4倍ずつ伸びているのが1画面に入っている状態にしてください。この4倍が、この記事でいちばん覚える価値のある数字です。
③ 動的配列の裏側 — 「2倍に取り直して全部コピー」を自分で書く
ここで疑問が出ます。
配列がメモリに連続して並んでいるなら、あとから増やせないはずです。 隣のアドレスは他のデータが使っているかもしれません。それなのに JavaScript の配列は push でいくらでも伸びます。どうなっているのか。
答えは、伸びていません。取り直しています。
満杯になったら、もっと大きい場所を新しく確保して、中身を全部コピーして、古いほうを捨てているのです。よく使われる作戦が「2倍にする」です。
これを自分で実装すると、何が起きているか手に取るように分かります。JavaScript には固定長の配列がないので、new Array(n) で作った配列を「これは固定長だと思って使う」ことにします。03-dynamic-array.mjs を作ります。
// 03-dynamic-array.mjs
class MyDynamicArray {
constructor() {
this.capacity = 1; // いま確保している箱の数
this.length = 0; // 実際に入っている数
this.store = new Array(1); // 固定長の入れ物だと思って使う
this.copyCount = 0; // 取り直しが起きた回数
this.copiedElements = 0; // コピーした要素の総数
}
push(value) {
if (this.length === this.capacity) {
this._grow();
}
this.store[this.length] = value;
this.length++;
}
_grow() {
const newCapacity = this.capacity * 2;
const bigger = new Array(newCapacity);
for (let i = 0; i < this.length; i++) { // ← ここが O(n)
bigger[i] = this.store[i];
this.copiedElements++;
}
this.store = bigger;
this.capacity = newCapacity;
this.copyCount++;
}
get(i) {
if (i < 0 || i >= this.length) return undefined;
return this.store[i]; // 添字1回 → O(1)
}
}
const N = 100_000;
const a = new MyDynamicArray();
for (let i = 0; i < N; i++) a.push(i);
console.log(`要素数 : ${a.length}`);
console.log(`確保している箱数 : ${a.capacity}`);
console.log(`取り直した回数 : ${a.copyCount}`);
console.log(`コピーした要素総数: ${a.copiedElements}`);
console.log(`1回のpushあたり : ${(a.copiedElements / N).toFixed(3)} 要素のコピー`);
出力です。
要素数 : 100000
確保している箱数 : 131072
取り直した回数 : 17
コピーした要素総数: 131071
1回のpushあたり : 1.311 要素のコピー
この数字が償却計算量の中身です。
10万回 push して、取り直しは 17回だけ。10万回のうち 99983 回は「箱に置くだけ」で終わっています。
そして最後の1行がいちばん大事です。コピーした要素の総数が 13万 で、push の回数が 10万。割ると 1.3。つまり 1回の push の平均コストは「1.3要素分のコピー」で、件数がいくら増えても変わりません。
- 最悪の1回は O(n)(10万件入っているときの取り直しは10万回コピー)
- でも平均すると O(1)(何回やっても1.3のまま)
これが償却計算量 O(1) です。「たまにすごく重いが、回数で割ると軽い」。
2倍でなければどうなるか
「2倍」が効いていることも確かめられます。_grow を「毎回1個だけ増やす」に変えた版を 04-grow-by-one.mjs として作ります。
// 04-grow-by-one.mjs
class GrowByOne {
constructor() {
this.capacity = 1;
this.length = 0;
this.store = new Array(1);
this.copyCount = 0;
this.copiedElements = 0;
}
push(value) {
if (this.length === this.capacity) {
const bigger = new Array(this.capacity + 1); // ← 1個だけ増やす
for (let i = 0; i < this.length; i++) {
bigger[i] = this.store[i];
this.copiedElements++;
}
this.store = bigger;
this.capacity = this.capacity + 1;
this.copyCount++;
}
this.store[this.length] = value;
this.length++;
}
}
const N = 20_000; // 10万にすると相当待たされるので減らしてある
const start = performance.now();
const a = new GrowByOne();
for (let i = 0; i < N; i++) a.push(i);
const ms = performance.now() - start;
console.log(`N=${N}`);
console.log(`取り直した回数 : ${a.copyCount}`);
console.log(`コピーした要素総数: ${a.copiedElements}`);
console.log(`1回のpushあたり : ${(a.copiedElements / N).toFixed(1)} 要素のコピー`);
console.log(`かかった時間 : ${ms.toFixed(2)} ms`);
N=20000
取り直した回数 : 19999
コピーした要素総数: 199990000
1回のpushあたり : 9999.5 要素のコピー
かかった時間 : 213.44 ms
1回あたり1万要素のコピーです。 2倍作戦のときは1.3でした。件数を増やすとこの「1回あたり」もどんどん増えるので、償却しても O(1) にならず、全体は O(n²) になります。
「2倍にする」は思いつきではなく、これを O(1) にするための選択です。 取り直しの回数が log₂(n) 回に抑えられ、コピーの総数が n の定数倍で止まるからです。実際の V8 は倍率がぴったり2ではありませんが、「一定の倍率をかけて増やす」という性質は同じです。
そして、ここで unshift の遅さの正体がもう1つ見えます。 unshift は取り直しが起きなくても毎回必ず全要素をずらします。ずらす作業には償却の逃げ道がありません。だから push は速く、unshift は遅いのです。
④ 連結リストを自分で書く
配列の弱点は「先頭・途中への出し入れで全員がずれる」ことでした。ずれる原因は「連続して並んでいること」です。
では、連続を捨てたらどうなるか。 それが連結リストです。
値のとなりに「次はここ」という矢印を持たせて、鎖のように繋ぎます。
head → [10|→] → [20|→] → [30|→] → null
メモリ上でどこにあってもかまいません。矢印が繋がっていればリストです。だから、間に1個入れるのは「矢印を2本つなぎ替えるだけ」で済みます。
入れる前: [10|→] → [30|→]
入れた後: [10|→] → [20|→] → [30|→]
前後の要素以外は1個も動きません。
単方向連結リスト
05-singly.mjs を作ります。
// 05-singly.mjs
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null; // 先頭
this.tail = null; // 末尾(持っておくと push が O(1) になる)
this.length = 0;
}
// 先頭に足す → 矢印1本 → O(1)
unshift(value) {
const node = new Node(value);
node.next = this.head;
this.head = node;
if (this.tail === null) this.tail = node;
this.length++;
return node;
}
// 末尾に足す → tail を持っているので O(1)
push(value) {
const node = new Node(value);
if (this.tail === null) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.length++;
return node;
}
// node の直後に入れる → 矢印2本 → O(1)(node を既に持っている前提)
insertAfter(node, value) {
const fresh = new Node(value);
fresh.next = node.next;
node.next = fresh;
if (this.tail === node) this.tail = fresh;
this.length++;
return fresh;
}
// n番目を取る → 先頭から数える → O(n)
get(index) {
if (index < 0 || index >= this.length) return undefined;
let cur = this.head;
for (let i = 0; i < index; i++) cur = cur.next;
return cur.value;
}
// 値で消す → 探すのに O(n)、繋ぎ替えは O(1)
remove(value) {
let prev = null;
let cur = this.head;
while (cur !== null) {
if (cur.value === value) {
if (prev === null) this.head = cur.next;
else prev.next = cur.next;
if (this.tail === cur) this.tail = prev;
this.length--;
return true;
}
prev = cur;
cur = cur.next;
}
return false;
}
toArray() {
const out = [];
let cur = this.head;
while (cur !== null) { out.push(cur.value); cur = cur.next; }
return out;
}
}
// 動くことを確かめる
const list = new SinglyLinkedList();
list.push('b');
list.push('c');
list.unshift('a');
console.log('push/unshift 後 :', list.toArray().join(' → '));
const nodeA = list.head;
list.insertAfter(nodeA, 'a2');
console.log('a の直後に a2 :', list.toArray().join(' → '));
console.log('get(2) :', list.get(2));
list.remove('b');
console.log('b を消した後 :', list.toArray().join(' → '));
console.log('length :', list.length);
push/unshift 後 : a → b → c
a の直後に a2 : a → a2 → b → c
get(2) : b
b を消した後 : a → a2 → c
length : 3
remove で prev を持ち回っているところに注目してください。 単方向リストは前に戻れないので、消すには「1つ前のノード」が必要です。だから「消したいノードそのもの」を持っていても、単方向リストでは O(1) で消せません。
これを解決するのが双方向リストです。
双方向連結リスト
06-doubly.mjs を作ります。
// 06-doubly.mjs
class DNode {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
unshift(value) {
const node = new DNode(value);
if (this.head === null) { this.head = node; this.tail = node; }
else { node.next = this.head; this.head.prev = node; this.head = node; }
this.length++;
return node;
}
push(value) {
const node = new DNode(value);
if (this.tail === null) { this.head = node; this.tail = node; }
else { node.prev = this.tail; this.tail.next = node; this.tail = node; }
this.length++;
return node;
}
insertAfter(node, value) {
const fresh = new DNode(value);
fresh.prev = node;
fresh.next = node.next;
if (node.next !== null) node.next.prev = fresh;
else this.tail = fresh;
node.next = fresh;
this.length++;
return fresh;
}
// ノードそのものを渡せば O(1) で消せる ← 双方向の価値はここ
removeNode(node) {
if (node.prev !== null) node.prev.next = node.next;
else this.head = node.next;
if (node.next !== null) node.next.prev = node.prev;
else this.tail = node.prev;
node.prev = null;
node.next = null;
this.length--;
}
get(index) {
if (index < 0 || index >= this.length) return undefined;
let cur = this.head;
for (let i = 0; i < index; i++) cur = cur.next;
return cur.value;
}
toArray() {
const out = [];
let cur = this.head;
while (cur !== null) { out.push(cur.value); cur = cur.next; }
return out;
}
toArrayBackward() {
const out = [];
let cur = this.tail;
while (cur !== null) { out.push(cur.value); cur = cur.prev; }
return out;
}
}
const d = new DoublyLinkedList();
const n1 = d.push('one');
const n2 = d.push('two');
const n3 = d.push('three');
console.log('前から :', d.toArray().join(' → '));
console.log('後ろから:', d.toArrayBackward().join(' → '));
d.removeNode(n2); // n2 を持っているので探さない
console.log('two を消した:', d.toArray().join(' → '));
console.log('length :', d.length);
console.log('前後の整合 : head =', d.head.value, '/ tail =', d.tail.value);
前から : one → two → three
後ろから: three → two → one
two を消した: one → three
length : 2
前後の整合 : head = one / tail = three
removeNode(n2) は、リストの中を1歩も歩いていません。 矢印を4本つなぎ替えただけです。10万件入っていても、100万件入っていても同じ手数。これが真の O(1) の削除です。
ただし条件が付きます。「消したいノードそのものを既に持っている」ときだけです。 「値が two のものを消して」と言われたら探すので O(n) に戻ります。この条件を落として「連結リストは削除が速い」と覚えると、必ず外します。
先頭への追加を、配列と比べる
いよいよ、①で困った操作を比べます。07-unshift-compare.mjs を作ります。
// 07-unshift-compare.mjs
import { measure } from './bench.mjs';
class Node { constructor(v) { this.value = v; this.next = null; } }
const N = 100_000;
measure(`配列 unshift ${N} 回`, () => {
const arr = [];
for (let i = 0; i < N; i++) arr.unshift(i);
return arr.length;
});
measure(`リスト unshift ${N} 回`, () => {
let head = null;
let count = 0;
for (let i = 0; i < N; i++) {
const node = new Node(i);
node.next = head;
head = node;
count++;
}
return count;
});
配列 unshift 100000 回 1836.09 ms
リスト unshift 100000 回 6.94 ms
約265倍です。 連結リストの圧勝で、これは教科書どおりです。O(n²) と O(n) の差がそのまま出ています。
ここまでなら話は簡単です。「先頭に入れるなら連結リスト」。
ところが、ここから教科書どおりにいかなくなります。
⑤ 同じ O(n) なのに、配列のほうが数倍速い
「先頭への追加が265倍速いなら、ログは連結リストで持とう」と考えました。
そして書き換えたら、一覧を表示する処理が遅くなりました。
一覧表示は「全件を順に見る」だけです。計算量の表にはこう書いてあります。
| 操作 | 配列 | 連結リスト |
|---|---|---|
| 全走査 | O(n) | O(n) |
同じです。 同じなら同じ速さのはずです。測ります。08-traverse.mjs を作ります。
// 08-traverse.mjs
import { measure } from './bench.mjs';
class Node { constructor(v) { this.value = v; this.next = null; } }
const N = 5_000_000;
// 同じ中身を、配列とリストの両方で作る
const arr = new Array(N);
for (let i = 0; i < N; i++) arr[i] = i;
let head = null;
let tail = null;
for (let i = 0; i < N; i++) {
const node = new Node(i);
if (tail === null) { head = node; tail = node; }
else { tail.next = node; tail = node; }
}
// 同じことをする:全部足す
for (let round = 1; round <= 3; round++) {
console.log(`--- ${round} 回目 ---`);
measure('配列を全部足す', () => {
let sum = 0;
for (let i = 0; i < arr.length; i++) sum += arr[i];
return sum;
});
measure('リストを全部足す', () => {
let sum = 0;
let cur = head;
while (cur !== null) { sum += cur.value; cur = cur.next; }
return sum;
});
}
出た数字です。
--- 1 回目 ---
配列を全部足す 6.12 ms
リストを全部足す 58.91 ms
--- 2 回目 ---
配列を全部足す 4.88 ms
リストを全部足す 54.33 ms
--- 3 回目 ---
配列を全部足す 4.91 ms
リストを全部足す 53.70 ms
約11倍、配列のほうが速いです。 計算量は同じ O(n) なのに。
3回繰り返しているのは、1回目だけ遅い「暖まっていない状態」を切り離すためです。2回目以降が安定しているので、この差は誤差ではありません。
理由 — CPUキャッシュ
O記法が数えているのは「手数」です。1手のコストが同じだ、という前提で数えています。 その前提が崩れています。
CPU はメインメモリからデータを取るとき、1個ずつ取ってきません。 「キャッシュライン」という単位(多くの CPU で64バイト)でまとめて持ってきます。
配列の場合。arr[0] を読むと、隣の arr[1] から arr[7] くらいまでがついでにキャッシュに入ります。次の7回はメインメモリに行きません。8回に1回だけ取りに行けば済みます。
配列: [0][1][2][3][4][5][6][7] ← まとめて1回で来る
連結リストの場合。ノードはメモリ上のどこにあるか分かりません。node1 を読んだとき、そのついでに来た64バイトの中に node2 があるとは限りません。1個進むたびにメインメモリまで取りに行く可能性があります。
リスト: [node1] ...... [node7] .. [node3] ........ [node2]
ばらばらの場所 → 毎回取りに行く
これがキャッシュミスです。メインメモリはキャッシュより桁で遅いので、手数は同じでも1手の値段が違うのです。
さらに連結リストには不利が2つ重なります。
- 「次のアドレスを読んでから、次に進む」という順番が固定される。 先読みができません。配列は「次は連続した場所」と分かっているので、CPU が勝手に先に持ってきてくれます
- 矢印そのものにメモリを食う。 値1個につき
nextが付くので、同じ件数でも配列より広い範囲に散ります。触るメモリが増えれば、キャッシュに乗る割合はさらに下がります
ここが結論です
計算量の表は「どちらが速いか」を教えてくれません。「件数が増えたときの伸び方」だけを教えてくれます。
- 伸び方が違うとき(O(n) と O(n²) など)は、表が正しい。 件数が増えれば必ず逆転する
- 伸び方が同じとき(どちらも O(n))は、表は何も言っていない。 決めるのは実測
そして、伸び方が同じで実測が違う場面では、たいてい連続して並んでいるほう(配列)が勝ちます。 現代の CPU がそういう作りになっているからです。
「速くする前に必ず測る」は 速くする前に必ず測る — パフォーマンス改善とEXPLAIN でも書きましたが、計算量の表を根拠に測らずに置き換えるのは、勘で直すのと同じでした。自分がやったのはそれです。
📷 スクリーンショット③:
08-traverse.mjsの出力3回分。「同じ O(n) で11倍違う」が1枚に写っている状態にしてください。この記事を読み返すとき、いちばん効くのはこの画面です。
⑥ 判断表 — 操作で決める
ここまでを1枚にします。計算量と実測の両方を並べます。
N=100000、Ubuntu Server(2 vCPU)、Node.js v20 での測定値です。「操作1回」ではなく「その操作を N 回まわしたときの合計」で書いています。
| 操作 | 配列(計算量) | 配列(実測) | 連結リスト(計算量) | 連結リスト(実測) | 勝ち |
|---|---|---|---|---|---|
| 末尾に追加 | 償却 O(1) | 3.4 ms | O(1)(tail を持つ場合) | 8.1 ms | 配列 |
| 先頭に追加 | O(n) | 1836 ms | O(1) | 6.9 ms | リスト(265倍) |
| n番目にアクセス | O(1) | ほぼ0 ms | O(n) | 測定不能なほど遅い | 配列(桁違い) |
| 途中の削除(参照あり) | O(n) | 遅い | O(1)(双方向) | 速い | リスト |
| 途中の削除(値で探す) | O(n) | 遅い | O(n) | さらに遅い(キャッシュミス) | 配列 |
| 全走査 | O(n) | 4.9 ms | O(n) | 53.7 ms | 配列(11倍・表では同じ) |
| 末尾から削除 | O(1) | 速い | O(1) 双方向 / O(n) 単方向 | 条件次第 | 配列 |
| メモリ使用量 | 値のみ | 少ない | 値+矢印1〜2本 | 多い | 配列 |
「n番目にアクセス」の行を補足します。list.get(50000) は5万回歩きます。これを10万回やると50億回の移動になるので、測ろうとしても現実的な時間で終わりません。だから数字を入れていません。「遅い」ではなく「やってはいけない」の領域です。
結論
迷ったら配列です。 これは手抜きではなく、上の表を読んだ結果です。
- 8行のうち6行で配列が勝っている
- 配列が負ける行(先頭追加・参照ありの途中削除)は、条件が付いている
- しかも「全走査」の行が示すように、表で引き分けの操作でも実測では配列が勝つ
連結リストを選ぶのは、次の2つが同時に成り立つときだけです。
- 途中の挿入・削除が処理の主役である(おまけではなく、そこが回数の大半)
- その位置のノードへの参照を、探さずに既に持っている
2番が抜けているケースがほとんどです。 「削除が O(1)」は「探さなくていい」が前提で、探すなら O(n) で、しかもキャッシュミスの分だけ配列に負けます。
そしてもう1つ。JavaScript では、その2条件が揃っても連結リストが最善とは限りません。
「先頭への追加が主役」なら、多くの場合はそもそも先頭に入れる必要がありません。09-push-then-reverse.mjs で確かめます。
// 09-push-then-reverse.mjs
import { measure } from './bench.mjs';
const N = 100_000;
measure('unshift で新着順に並べる', () => {
const arr = [];
for (let i = 0; i < N; i++) arr.unshift(i);
return arr[0];
});
measure('push してから最後に reverse', () => {
const arr = [];
for (let i = 0; i < N; i++) arr.push(i);
arr.reverse();
return arr[0];
});
measure('push だけして、読むときに後ろから', () => {
const arr = [];
for (let i = 0; i < N; i++) arr.push(i);
let last;
for (let i = arr.length - 1; i >= 0; i--) last = arr[i];
return last;
});
unshift で新着順に並べる 1841.22 ms
push してから最後に reverse 4.98 ms
push だけして、読むときに後ろから 5.61 ms
370倍速くなりました。データ構造を変えずに、順番を作るタイミングを変えただけです。
自分の「固まった」問題の実際の直しかたは、これでした。連結リストは書かなくて済みました。データ構造を変える前に、「その操作を本当にその順番でやる必要があるか」を疑うほうが、たいてい効きます。
- 挿入のたびに順番を作っていた → 読むときに1回だけ作る
- 先頭が欲しかった → 末尾を先頭として読む
「キーで引きたい」なら、そもそも配列でも連結リストでもなく Map や Set です。そこは別の話になるので、この記事では扱いません。
⑦ 実務で連結リストが出てくる場所
「自分で書くことは滅多にない」と書きましたが、読む機会はあります。 実際に中で使われているものを3つ挙げます。どれも「⑥の2条件が本当に揃っている」例です。
LRUキャッシュの中身
LRU は「いちばん長く使われていないものから捨てる」キャッシュです。必要な操作はこうなります。
- キーで値を引く → 速くしたい
- 使われたものを「最近使った」側に移す → 速くしたい
- 満杯なら「最も古い」ものを捨てる → 速くしたい
これを、ハッシュマップ(Map)+双方向連結リストの組み合わせで作ります。
Mapが「キー → そのノードへの参照」を持つ → 引くのが O(1)- 双方向リストが「使った順」を持つ → 末尾が最も古い
Mapからノードそのものが出てくるので、removeNodeが O(1) で撃てる
⑥の条件2「参照を既に持っている」を、Map が満たしているのがポイントです。 連結リストが単体で使われているのではなく、参照を配る相棒と組んで初めて成立しています。
Redis の maxmemory-policy に allkeys-lru のような設定があるのは、この種の仕組みが中にあるからです。実際に触ったのは キャッシュは消すのが一番難しい — Redisの導入 でした。
エディタの undo 履歴
Ctrl+Z と Ctrl+Y は、履歴の上を前後に1歩ずつ動きます。
- 「n番目の履歴を出せ」とは言われない →
get(n)が O(n) でも困らない - 常に「いま」の前後に動く → 双方向リストの
prev/nextそのまま - 途中で新しい操作をすると、そこから先の履歴を捨てる → 矢印1本を
nullにするだけ
配列で作れないわけではありませんが、「途中から先を捨てる」が矢印1本になるのは素直です。
Git のコミット
コミットには「親コミット」への参照が入っています。git log が歴史を辿れるのは、コミットが親を指す鎖になっているからです。矢印が過去に向いた連結リストです(マージがあるので、正確には分岐する構造です)。
だから git log は速いのに、「1000個前のコミット」を出すには1000個辿るという性質になります。⑥の表の「n番目アクセスは O(n)」がそのまま出ています。
これは自分で作って確かめました。gitは差分を保存していない — コミットを自作する です。あのとき「親を指すだけで歴史になる」と書いた部分が、この記事の連結リストと同じものでした。
だから、書けなくてもいい
3つとも「読めば分かる」で足ります。自分でゼロから書く場面はほとんど来ません。
意味があるのは、この記事で1回自分の手で書いたことです。書いたので、
- Redis の LRU の説明を読んで「あの
Map+双方向リストか」と分かる - コミット履歴の後ろのほうを取り出す操作が遅い理由を推測できる
- 「配列の代わりに連結リストにしたら速くなるのでは」という思いつきを、自分で棄却できる
面接対策のために覚える話ではありません。 覚えても⑤の11倍は説明できません。測ったから説明できます。
roadmap.sh のコンピュータ科学のロードマップにもデータ構造の項目は入っていますが、そこに並んでいる名前を暗記して埋めていく作業には価値がありませんでした。 この1本で確かめたのは名前ではなく、「置き方を決めると速さが決まる」という1つのことです。
つまずいたところ
1. .js で書いたら Cannot use import statement outside a module で落ちた
bench.mjs を bench.js にして import したときです。Node.js は .js を CommonJS として読むので、import が構文エラーになります。拡張子を .mjs にするだけで直ります。 package.json に "type": "module" と書く方法もありますが、この記事は npm init もしないので拡張子で解決しました。
2. unshift の計測が終わらなくて Ctrl+C した
最初 N = 1_000_000 で unshift を測ろうとしました。動かす回数の合計は約5000億回になるので、待っても終わりません。O(n²) のものを測るときは、n を小さくしてから件数を倍にしていくのが正しい進め方でした。①の「固まった」の再現でもあります。止まったと思ったら Ctrl+C で戻れます。 VMは壊れません。
3. 1回目の測定だけ極端に遅くて、結論を間違えた
最初は1回しか測っておらず、配列の全走査が 40 ms 出ていました。「思ったほど差がない」と書きかけたところで、3回繰り返してみたら2回目以降は 5 ms でした。1回目は実行時の最適化が効く前で、キャッシュにも何も乗っていません。 測定は必ず複数回まわして、2回目以降を見ます。 1回目の数字で判断すると、逆の結論が出ます。
4. new Array(1) を「長さ1の固定配列」だと思って書いたら、勝手に伸びていた
③の MyDynamicArray で満杯チェックの位置を間違え、チェックが効いていないのに動いていました。JavaScript の配列は範囲外に代入しても伸びるので、バグに気づけません。copyCount が 0 のままだったので発覚しました。「動いた」ではなく「回数が想定と合っている」で確認する必要があります。 固定長のふりをさせるときは、自分でチェックを入れないと誰も止めてくれません。
5. 単方向リストの remove で tail を直し忘れて、あとから push した要素が消えた
末尾のノードを消したときに this.tail を更新していませんでした。toArray() では正しく見えるのに、次に push すると消したはずのノードの後ろに繋がって、リストから見えなくなるという症状でした。連結リストのバグは「壊れた瞬間」ではなく「次の操作」で出ます。 消したあとに必ず push して toArray() を見る、というのを手順に入れました。
6. 双方向リストの removeNode で prev / next を null にしなかった
繋ぎ替えだけして、消したノードの prev / next はそのままにしていました。表示上は正しく動きます。ただ消したノードがリストの中身を掴んだままになるので、参照が生き残っている間はメモリが解放されません。消したノードは、自分の矢印も切る。 表示では絶対に気づけない種類の問題でした。
7. 「配列より連結リストのほうが挿入が速い」を無条件に信じていた
⑤を測るまで、「挿入は連結リスト」と丸暗記していました。実際は「その位置のノードを既に持っているとき」だけです。「10000番目に入れて」なら、連結リストは1万回歩いたうえに毎回キャッシュミスするので、配列の splice に負けます。計算量の話には、ほぼ必ず「前提」が隠れています。 前提を落とした暗記は、間違いより危ないです。
8. 数字を1回測って記事にしようとした
⑤の11倍は、最初 3 倍でした。ノードの作り方を変えたら(オブジェクトリテラルから class に)数字が動いたのです。測り方で数字が動くのを見て、「比率と伸び方だけを主張して、絶対値は主張しない」という書き方に変えました。実測を載せるなら、環境と回数を必ず一緒に書きます。 数字だけ書くと、読んだ人が自分の環境で再現できません。
後片づけ
作ったのは ~/cslab/list の中のファイルだけです。書き換えた設定はありません。
中身を確認します。
.mjs が10個ほどと、数十KB のはずです。確認してから消します。
cslab の下が空なら、それも消して構いません。
rm -rf は確認なしで消えます。 打つ前に pwd で場所を確かめ、~/cslab/list と完全に一致していることを見てください。ホームディレクトリで対象を間違えると戻せません。消したファイルはごみ箱に入らず、そのまま無くなります。
Node.js を apt で入れた人は、残しておいて構いません。この先の記事でも使います。 消したいなら次で消せます。
まとめ — 理解できたこと
- データ構造は「データの置き方」の決定であり、置き方を決めた瞬間に「どの操作が速いか」も全部決まる。 あとから工夫して速くする余地はほとんど残らない
- 配列の添字アクセスが O(1) なのは検索しているからではなく、「先頭アドレス + 添字 × 1要素の大きさ」という足し算1回でその場所に行けるから。添字 0 でも50万でも同じ時間
- 同じ性質(連続して並んでいる)が、先頭への追加を O(n) にしている。 空けるには後ろの全員をずらすしかない。得意と苦手は同じ理由から出る
pushとunshiftを10万回ずつ回すと 約540倍の差。同じ「1件足す」に見えて中身が違う- 件数を2倍にして「約2倍」なら O(1) の積み上げ、「約4倍」なら O(n²)。 表を暗記しなくても、倍にして測れば自分で判定できる
- JavaScript の配列が自動で伸びるのは、満杯になったら2倍の場所を取り直して全部コピーしているから。10万回の
pushで取り直しは 17回だけ - 1回の最悪は O(n)、平均すると O(1)。 これが償却計算量。コピー総数13万 ÷ push 10万 = 1.3 という数字がその中身
- 「1個ずつ増やす」に変えると1回あたり 1万要素のコピーになり、償却しても O(1) にならない。「2倍」は O(1) を成立させるための選択だった
- 連結リストは連続を捨てたので、先頭への追加が矢印1本で終わる O(1)。実測でも配列の 265倍速い
- ただし「n番目を取る」が O(n)。配列とちょうど得意・苦手が裏返っている。10万件の途中を取る操作は、やってはいけない領域
- 双方向リストの
removeNodeは本当に O(1) だが、「消したいノードそのものを既に持っている」ときだけ。値で探すなら O(n) に戻る - 同じ O(n) の全走査で、配列が約11倍速い。 理由は CPU キャッシュ。連結リストはメモリ上に散らばっているので1個進むたびに取りに行く
- 計算量の表が教えてくれるのは「伸び方」だけで、「どちらが速いか」ではない。 伸び方が同じなら、決めるのは実測。表だけ見て置き換えるのは勘で直すのと同じ
- 迷ったら配列。 連結リストを選ぶのは「途中の挿入削除が主役」かつ「参照を既に持っている」の両方が揃うときだけ
- そして揃っていても、先に「その順番でやる必要があるか」を疑うほうが効く。
unshift10万回をpush+reverseに変えただけで370倍速くなった
参考リンク
- roadmap.sh — Computer Science — この記事が扱っている範囲の位置
- MDN — Array — JavaScript の配列の仕様
- MDN — Array.prototype.push — 末尾への追加
- MDN — Array.prototype.unshift — 先頭への追加
- MDN — Array.prototype.splice — 途中の挿入と削除
- MDN — Map — 「キーで引く」ときの選択肢
- MDN — Performance.now — ミリ秒より細かい時刻の取り方
- Node.js ドキュメント — Performance measurement APIs — Node.js 側の計測 API
- V8 ブログ — Elements kinds in V8 — JavaScript の配列が内部でどう持たれているか
次に読む
この記事は 【深掘り】コンピュータ科学 の 5 / 25 本目です。
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- 動的配列の裏側と償却計算量
- 計算量が同じでも配列のほうが速い
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント