~ LeetCode 2. Add Two Numbers から学ぶ、メモリとリアルタイムシステムの深淵 ~
はじめに
「Googleを目指すエンジニア」として、LeetCodeのMedium問題に挑戦しています。 今回は LeetCode 2. Add Two Numbers。
一見ただの「連結リスト（Linked List）の足し算」ですが、深く掘り下げると 「償却計算量」 や 「CPUキャッシュ」 、さらには 「NASAや自動車業界のメモリ管理」 にまで話が及ぶ、非常に奥深い問題でした✨
この記事では、問題を解くだけでなく、Googleの面接官と対等に渡り合うための「エンジニアリングの勘所」 を余すところなく共有します。
前提知識
この記事では前提知識でBigO(計算量)が出てくるので、こちらもお読みください💚
1. 問題の概要：Add Two Numbers
逆順に数字が格納された2つの連結リストを足し合わせ、結果を連結リストで返す問題です。
- Input:
l1 = [2,4,3],l2 = [5,6,4](342 + 465) - Output:
[7,0,8](807)
🎀💚解き方💚🎀
逆順になっているため、先頭（1の位）から順に足していけば、小学校の筆算と同じロジックで解けます。2.最強の定石「ダミーヘッド」(Dummy Head)
Linked Listの問題を解く際、初心者が必ずぶつかる壁があります。 「最初のノード（head）をどうやって作るか問題」 です。
dummyheadがなければ、ループの中で最初のダミーヘッドを作るかの if 判定をしなければいけません。
ループ内の処理を初期化に置き換えることをエッジケースを一般化する といいます。
ダミーヘッドなしの苦しいコード
// 悪い例：条件分岐が複雑になる
if (head === null) {
head = newNode; // 1回目だけの特別処理
current = head;
} else {
current.next = newNode; // 2回目以降の処理
current = current.next;
}
ループの中で毎回 if (head === null) を判定するのは非効率ですし、コードが汚くなります。
ダミーヘッドありのスマートなコード
「値が0の捨て駒ノード（ダミー）」を最初に作っておけば、すべてのノードを「前のノードの次につなぐ」という処理で統一できます。
計算量 $O(max(M,N))$
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
// 1. ダミーヘッド作成（ここが起点）
let dummyHead = new ListNode(0);
let current = dummyHead;
let carry = 0;
// l1, l2, carry のいずれかが残っている限りループ
while (l1 !== null || l2 !== null || carry > 0) {
const val1 = (l1 !== null) ? l1.val : 0;
const val2 = (l2 !== null) ? l2.val : 0;
const sum = val1 + val2 + carry;
carry = Math.floor(sum / 10);
const digit = sum % 10;
// ★常に「次」につなぐだけでOK
current.next = new ListNode(digit);
current = current.next;
if (l1 !== null) l1 = l1.next;
if (l2 !== null) l2 = l2.next;
}
// ダミーの次（本当の先頭）を返す
return dummyHead.next;
};
疑問：「current動かしたらdummyHeadも動いちゃわない？」
ここで多くの人が混乱しますが、動きません。
- dummyHead は「杭（工事の起点）」として動きません。
- current は「作業員」として、next をつないでは自分自身（変数の中身）を更新して進んでいきます。 だから最後に dummyHead.next を返せば、正しくリスト全体を取得できます。
3.面接官からの追撃：「もしリストが正順だったら？」
「完璧だね。じゃあ入力が [3, 4, 2] ($3 \to 4 \to 2$) のように正順だったらどうする？」
Linked Listは後ろに戻れません。この場合、データ構造の知識が問われます。
答えは...💚
答えは「スタック (Stack)」です。「入れて、逆順に出す（LIFO）」特性を使えば、リストを走査してスタックに積み、取り出すときに「1の位」から計算できます。
4.データ構造の深淵: Array vs Linked List
ここで重要な議論が発生します。 「スタックを実装するなら、Array（動的配列）と Linked List どっちがいい？」
Array Stack (JavaScriptの [] や Pythonの list)
- メリット：平均して高速。メモリが連続しているため、CPUキャッシュ（空間的局所性）が効く。
- デメリット：リサイズ（拡張） が発生する。容量がいっぱいになると、倍の領域を確保してコピーするため、一時的に $O(N)$ かかる。
- 計算量: 償却計算量 (Amortized) $O(1)$。
Amortizedとは...?💚
Array.push Array.pop って $O(1)$なの？
と考えたあなた....
鋭い！そこを疑えるのは、アルゴリズムのセンスがある証拠です。
結論から言うと、「基本的には $O(1)$ だが、厳密には『償却（Amortized）$O(1)$』」 というのが、Googleの面接で期待される100点満点の回答です。
1. なぜ基本的には O(1)なのか？
配列（Array）の末尾にデータを追加したり、末尾から削除したりするだけなら、メモリの特定の場所に書き込むだけなので一瞬で終わります。
-
arr[last] = value（これだけ！）
2.なぜ「たまにO(N)になるのか」（ここが重要）
JavaScript/TypeScriptの Array や Pythonの list は、「動的配列 (Dynamic Array)」 と呼ばれます。
最初は「10個分」などのメモリを確保していますが、データがいっぱいになった瞬間に裏側で大工事が起きます。
- 新しいメモリ領域（例えば倍の20個分）を確保する。
- 古いデータを全部そこへコピーする（引越し）。
- 古い領域を捨てる。
この「コピー（引越し）」の瞬間だけは、データの個数分だけ時間がかかるので $O(N)$ になります。
3.それでもなぜ「$O(1)$」と言い切っていいのか？
この「引越し（リサイズ）」は頻繁には起きないからです。通常、配列がいっぱいになるとサイズを「2倍」にします。
- 10個埋まる → 引越し ($O(10)$)
- 20個埋まる → 引越し ($O(20)$)
- 40個埋まる → 引越し ($O(40)$)
- ...
- 100万個埋まる → 引越し ($O(10^6)$)
引越しのコストを、それまでに行われた大量の「$O(1)$ の操作」で割り勘すると、「平均すればほぼ $O(1)$ だよね」 と見なせます。
これを専門用語で 「償却計算量 (Amortized Time Complexity)」 と言います。
「リサイズが起こる回数」は $O(\log N)$ ですが、「1回あたりの平均コスト（償却）」は $O(1)$ になります。
Google面接でのキラーフレーズ
もし面接で「Stackの push は $O(1)$ ですか？」と聞かれたら、こう答えると評価が爆上がりします。
「 動的配列（Dynamic Array） で実装する場合は、リサイズが発生する最悪ケースでは $O(N)$ ですが、償却計算量（Amortized Complexity） としては $O(1)$ です。
もし厳密に常に $O(1)$ を保証したいなら、Linked Listを使ってStackを実装します（先頭への追加・削除は常に $O(1)$ なので）。」
ここまで言えれば、データ構造の基礎は完璧だと判断されます！
Linked List Stack
-
メリット：常に一定 。リサイズがないため、いつ
pushしても厳密に $O(1)$。 -
デメリット: 平均して遅い メモリがバラバラに配置されるためキャッシュミスが起きやすく、
newのオーバーヘッドもある。
// Linked List Stackの例
class LinkedListStack {
private head: ListNode | null = null; // スタックの頂上
// Push: 先頭に新しいノードを挿入 O(1)
push(val: number): void {
const newNode = new ListNode(val);
newNode.next = this.head; // 今の先頭を、新しいやつの次にする
this.head = newNode; // 先頭を新しいやつに更新
}
// Pop: 先頭のノードを取り除いて値を返す O(1)
pop(): number | null {
if (this.head === null) return null; // 空ならnull
const popVal = this.head.val;
this.head = this.head.next; // 先頭を次の人に譲る
return popVal;
}
// おまけ: 中身を見るだけ O(1)
peek(): number | null {
return this.head ? this.head.val : null;
}
}
5.ガチ勢の視点：「リアルタイムシステム」の真実
「Arrayの方が速いなら、全部Arrayで良くない？」そう思ったあなたに、Googleの面接官や組み込みエンジニアはこう返します。
「速さ（Speed）と、予測可能性（Predictability）は違う」
リアルタイム性とは「締め切りを守ること」
車のエアバッグや医療機器のようなハードリアルタイムシステムでは、平均速度よりも「最悪のケース」を重視します。 Arrayのリサイズで発生する「たまに遅くなるスパイク」は、命に関わるため許容されません。 そのため、遅くても常に一定時間で動く Linked List が選ばれるケースがあります。
さらに奥へ：Object Pool と 静的割り当て
しかし、Linked Listの new （動的メモリ確保）もシステム的にはコストが高い処理です。 そこで、NASAや自動車業界（MISRA C）では、さらに厳しい運用をします。
- Static Allocation (静的割り当て): 起動時に必要なメモリ（ノード1000個分など）を全て確保してしまう。
- Object Pool: 実行中は new を禁止し、確保済みのプールから使い回す。
- 枯渇したら？: 「足りないから増やす（リサイズ）」は禁止。設計ミスとしてエラーにするか、安全に停止させる。
「メモリは無限にあると思うな、勝手に増やせると思うな」 この感覚こそが、大規模システムやミッションクリティカルなシステムを設計するエンジニアに必要な視点です。
まとめ
たかが LeetCode の1問ですが、掘り下げるとここまで世界が広がります。
- アルゴリズム: ダミーヘッドでコードを簡略化する。
- データ構造：スタックの内部実装（償却 $O(1)$ vs 完全 $O(1)$）を理解する。
- システム設計: キャッシュ効率（Array有利）とリアルタイム性（Linked List有利）のトレードオフを知る。
Googleを目指す旅は、単にコードを書くことではなく、こうした「コンピュータの気持ち」を理解する旅なのかもしれません。