DOMツリーの内部表現とノード操作のコスト

DOMは「木」だが、その実装は「連結リスト」

DOM はブラウザが HTML をメモリ上に展開した木構造です。基礎は DOM で扱っていますが、本稿はその一段下――ノードがメモリ上でどう表現され、なぜ特定の操作が重いのか――を内部から解きほぐします。

最初に外せない事実が1つあります。childNodes は配列に見えますが、DOM ツリーは内部的には兄弟どうしをポインタでつないだ連結リストとして保持されています。各ノードは少なくとも次のリンクを持ちます。

parentNode      … 親へのポインタ
firstChild      … 最初の子へのポインタ
lastChild       … 最後の子へのポインタ
previousSibling … 1つ前の兄弟へのポインタ
nextSibling     … 1つ後の兄弟へのポインタ

子の集合は「先頭から nextSibling を辿る」ことで列挙されます。つまり parent.childNodes[k] のような添字アクセスは内部的に先頭から k 個たどる O(n) の走査であり、配列のような O(1) ではありません。ループで childNodes[i] を回すと、各反復で先頭から数え直す実装では全体が O(n^2) に化けることがあります。

ノード・要素・属性・テキストの階層

DOM の型は1本の継承木にまとまっています。すべてのノードは抽象基底 Node を継承し、用途別に枝分かれします。この階層を知っていると、「なぜ textContent はあるのに children がないノードがあるのか」が一目で分かります。

重要なのは属性（Attr）が子ノードではない点です。<div class="x" id="y"> の class や id は childNodes には現れず、element.attributes（live な NamedNodeMap）や getAttribute() 経由でアクセスします。一方テキストは独立した Text ノードとして子に並びます。だから <p>あ<b>い</b>う</p> の p は「Text(あ)・Element(b)・Text(う)」の3つの子を持ちます。

live コレクションと static NodeList

DOM のコレクション取得 API には、**取得後のツリー変更が反映されるもの（live）と、しないもの（static）**の2系統があります。この違いを取り違えると、ループ中の挙動が破綻します。

live コレクションは「結果を配列に固めて返す」のではなく、問い合わせ条件を保持したビューです。アクセスのたびに現在のツリーを評価して結果を作るため、ノードを足せばその場で length が増えます。これが次のような典型バグを生みます。

// 危険：getElementsByTagName は live。append で要素が増えると length も増え続ける
const items = document.getElementsByTagName('div');
for (let i = 0; i < items.length; i++) {
  const clone = items[i].cloneNode(true);
  document.body.appendChild(clone); // items が伸び、ループが止まらない
}

// 安全：querySelectorAll は static。その瞬間の集合で固定される
const snapshot = document.querySelectorAll('div');
for (const el of snapshot) {
  document.body.appendChild(el.cloneNode(true)); // 元の集合だけを処理
}

appendChild と insertBefore のコスト

ノードをツリーへ挿入する操作は、ポインタの付け替えだけでは終わりません。appendChild(node) は内部でおおよそ次を行います。

1. node が既にどこかの子なら、まず元の位置から取り外す（DOM ノードは木の中で同時に2か所に存在できない）。
2. 親の子リストの末尾へ連結し、parentNode などのポインタを張り替える。
3. その部分木をスタイル無効化としてマークし、レイアウトとペイントの再計算候補に載せる。
4. 接続状態が変わるため、関連する MutationObserver の記録や connectedCallback（カスタム要素）の起動対象になる。

ポインタ操作自体は O(1) ですが、3 のスタイル・レイアウト無効化が本当のコストです。可視ツリーへの1回の挿入は、その要素と影響範囲のジオメトリ再計算（リフロー）を招き得ます。どの変更がどれだけ重いかの分類は リフローとリペイントのコスト で詳説しています。

insertBefore(newNode, referenceNode) も計算量は同じ O(1) です。「途中挿入だから配列のように後続をずらす O(n) が要る」と誤解されがちですが、連結リストなので前後2本のポインタを張り替えるだけです。コストの本体は位置ではなく、やはり挿入に伴う無効化のほうにあります。

DocumentFragment が効く理由

DocumentFragment は、親を持たない、画面に出ない軽量な入れ物です（nodeType は 11）。ここに子を組み立てているあいだはメインの文書ツリーに接続されていないため、スタイル無効化もリフローも発生しません。そして fragment を appendChild すると、特別なルールが働きます。

// 良い：1000個を fragment 上で組み立て、可視ツリーへの接続は最後の1回だけ
const frag = document.createDocumentFragment();
for (let i = 0; i < 1000; i++) {
  const li = document.createElement('li');
  li.textContent = '項目 ' + i;
  frag.appendChild(li);      // ここでは文書外。リフローは起きない
}
list.appendChild(frag);      // フラグメントの“中身”だけが移動。接続は1回に集約

ポイントは、appendChild(fragment) がフラグメントそのものではなく、その子全部を移動させ、移動後の fragment は空になる、という仕様です。結果として文書ツリーへの接続イベントは1回にまとまり、スタイル無効化とリフローの起点も1回で済みます。

テキストとノード同一性の落とし穴

ノードは木の中で一意の実体であり、同じノードを2か所に置くことはできません。a.appendChild(node) の時点で node が別の親に属していれば、その親から自動的に外れて移動します。これは「コピーされる」のではなく「引っ越す」挙動で、cloneNode(true) を使わない限り元の場所からは消えます。

テキストの読み書きにも段差があります。textContent は子孫の Text ノードの中身を連結して返し、書き込むと子をすべて1つの Text に置き換えます（パースしない・安全）。innerText は CSS のレンダリング結果に依存し、非表示要素を除外したうえ読み取りでレイアウトを誘発し得ます。innerHTML は HTML として解釈するため、信頼できない文字列を入れると XSS になります。

まとめ