比較・疑問解決 · 基礎から応用へ

配列と連結リスト

探索する時間と、場所が分かった後につなぎ替える時間を分け、配列と連結リストの実用上の違いを比較します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 連続した位置とリンクでつながる位置
  2. 添字を読む操作と値を探す操作
  3. 途中の挿入は場所を得るまで含めて数える
  4. 局所性と追加の記憶領域
  5. 参照の安定性と変更の頻度で選ぶ
  6. この記事をロゲイアに質問する理解を確かめる

連続した位置とリンクでつながる位置

固定長要素の配列は、先頭と添字から要素の位置を計算できます。連結リストは、値と次の要素へのリンクを持つノードをたどります。配列の連続性は添字参照や順次走査に役立ち、リストは既知位置の近くでつなぎ替えやすい構造です。ただし、配列へ並ぶものが参照なら、対象オブジェクト本体まで連続するとは限りません。また、単方向か双方向か、末尾参照を持つかによってリストの操作は変わります。二つの名前だけで比較表を作る前に、表現と必要な操作を具体的に決めることが重要です。

操作配列単方向リスト
既知添字の参照通常O(1)最悪O(n)
既知位置での順序保持挿入後続を移す場合O(n)必要な参照があればリンク変更O(1)
未知の値の探索未整列なら最悪O(n)最悪O(n)

添字を読む操作と値を探す操作

添字が分かっている配列の参照は、通常のRAMモデルではO(1)です。単方向リストで添字iの要素を得るには、先頭からリンクをたどるので、最悪O(n)になります。一方、未整列の配列で特定の値を探すなら、配列でも最悪O(n)です。「配列の検索はO(1)」という表現は、既知の添字による参照と、未知の値の探索を混ぜています。例えば100万要素のうち添字500000を読む仕事と、値500000があるか探す仕事は別です。キーで検索したいなら、整列や索引、ハッシュ表など追加の構造も候補になります。

途中の挿入は場所を得るまで含めて数える

配列[10,20,30,40]の20の直後へ25を入れると、順序を保つため30と40を後ろへ移す必要があります。リストで20のノードへの参照が既にあれば、新ノードから30へ、20から新ノードへリンクを直せます。しかし、20を最初から探すならリストの走査費用が加わります。単方向リストの削除でも、対象の直前のノードが必要になる場合があります。位置が既知のリンク変更だけをO(1)とする説明と、探索、確保、解放を含むAPI全体を区別してください。比較する操作の範囲をそろえないと、実際の用途とは違う結論になります。

局所性と追加の記憶領域

配列の順次走査は近いアドレスを使いやすく、キャッシュやプリフェッチに向く場合があります。リストはノードが別々に確保されると、次のアドレスを読み出すまで次へ進めず、リンク分の領域やアロケータの管理費用もかかります。ただし、リストのノードをまとめて確保する方式もあり、配列の要素が大きい場合の移動費用も無視できません。同じO(n)の走査でも、実行時間は表現と配置で異なります。要素数、要素サイズ、確保方法、アクセス順、温まったキャッシュかどうかをそろえて測定すると、何が差を生んだかを説明しやすくなります。

参照の安定性と変更の頻度で選ぶ

動的配列の拡張では保存領域が移り、要素への参照や反復子が無効になる場合があります。リストでも削除したノードへの参照は使えなくなり、並行更新には同期が必要です。どちらも、参照をいつまで保持できるかはライブラリの仕様を確認してください。添字参照と走査が中心なら配列、既知ノードの移動や接続が中心ならリストが候補になりますが、その中間にはdequeや分割された配列などもあります。まず実際の操作列を書き、検索、挿入、削除、走査の割合と寿命管理を整理すると、単独の計算量だけで選ぶ失敗を避けられます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ