要素索引と連結リストで局所linkを更新する

概要

索引付き連結リスト

要素IDから前後linkへ直接到達し、挿入・削除で影響する局所的なlinkだけを更新する。

考え方

各要素の前後の要素を索引として持ち、挿入・削除の際に隣接linkだけをつなぎ直す。値の並びを毎回移動せず、要素IDと掲載順を分ける。

番兵head,tailを使い、空列ではnext[head]=tail,prev[tail]=headとする。uの直後へ新ID xを入れるならv=next[u]を保存し、next[u]=x,prev[x]=u,next[x]=v,prev[v]=xとする。xを消すならu=prev[x],v=next[x]としてnext[u]=v,prev[v]=uへ変更する。最後はnext[head]からtailまで辿って元の列順を出力する。IDからnodeを探す辞書の費用はlink更新のO(1)と別に数える。

成立条件と計算量

位置の要素IDが既知なら挿入・削除O(1)。k番目の要素の検索は単純なlinkだけではO(N)。head・tail、唯一の要素、削除済みID、重複値を扱い、値から一意のIDを推定しない。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 茶色(400–799)。配列や辞書で要素を索引化し、挿入・削除で変わる前後関係だけを更新する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-linked-list-index

習得する技能

  • 要素IDから前後linkを引き、挿入・削除で変わる局所linkだけを更新して列順を復元できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

配列やmapの索引を使い、順序全体を走査せず前後linkだけを更新して列を保つ。

このUnitでは扱わないもの

  • 全候補の大小順や区間集約を保つ平衡木・heap。

根拠