アルゴリズム・データ構造図鑑 · 入門

連結リスト:挿入が速くても探索は速くならない

リンクのつなぎ替えと、目的の位置までたどる処理を分けて評価する。

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

更新日

この記事の目次
  1. 要素の場所をリンクでつなぐ
  2. 挿入で変更する二本のリンク
  3. 削除と境界条件
  4. 配列と比べるときの視点
  5. この記事をロゲイアに質問する理解を確かめる

要素の場所をリンクでつなぐ

単方向連結リストでは、各ノードが値と次のノードへのリンクを持ちます。先頭ノードへの参照から、リンクを順にたどって列を読みます。配列のように要素が連続している必要はありません。その代わり、添字iのノードを取り出すには先頭からi回ほど進むため、ランダムアクセスは通常O(n)です。連結リストを使うときは、双方向か単方向か、末尾参照を保持するかまで確認する必要があります。

挿入で変更する二本のリンク

A→B→Cという列で、Bの直後にXを挿入します。Bへの参照が既にあれば、まずX.nextをCへ向け、次にB.nextをXへ向ければA→B→X→Cになります。既存ノードを後方へ移す必要はありません。しかし「値がBであるノードを探して挿入する」操作では、Bを見つける走査が別に必要です。位置が既知の場合のO(1)を、位置探索を含む操作全体へ広げてはいけません。

削除と境界条件

単方向リストでXを外すには、その直前のノードからXの次へリンクをつなぎます。このため、削除対象への参照だけでは直前のノードが分からない場合があります。先頭を削除する場合は先頭参照の更新が必要です。双方向リストは前後のリンクを持つため既知ノードの削除を行いやすくなりますが、追加のリンク領域と整合性の維持が必要です。解放済みノードを参照し続ける不具合にも注意します。

配列と比べるときの視点

連結リストは、既知位置の周辺で列を頻繁につなぎ替える用途や、キューなどの構成に使えます。一方で、ノードごとの割り当て、リンク分のメモリ、キャッシュミスが負担になります。連続走査中心の処理では、要素の移動が不要という利点だけで配列より速いとは判断できません。末尾への追加をO(1)にしたいなら、末尾参照を保持して更新するなど、表現に必要な条件も説明します。

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

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

CS基礎を固める · STEP 9

学習コースから次を選ぶ