索引付き連結リスト
要素IDから前後linkへ直接到達し、挿入・削除で影響する局所的なlinkだけを更新する。
この典型を扱う単元: 要素索引と連結リストで局所linkを更新する
検索別名: doubly linked list、linked list、連結リスト
未知問からこの典型を見つける手掛かり
- 扱う対象
- link
- node
- 列
- 前
- 後
- 要素
- 使う手掛かり
- 削除
- 前後をつなぐ
- 局所更新
- 直後に挿入
- 保つ不変量
- head
- next
- prev
- tail
- 隣接関係
- 求めるもの
- 列を復元
- 挿入削除
- 順序を出力
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
学習成果と学習単位
要素IDから前後linkを引き、挿入・削除で変わる局所linkだけを更新して列順を復元できる。
要素索引と連結リストで局所linkを更新するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC218 H「Red and Blue Lamps」 公式問題主題: path matchingのheap縮約greedy / 補助タグ
技能・出典
主題: path matchingのheap縮約greedy
主タグ: path matchingのheap縮約greedy / 補助タグ: 索引付き連結リスト、priority queue・best-first列挙、状態・配置の正規化
- ABC344 E「Insert or Erase」 公式問題主題: 要素索引と連結リストで局所linkを更新する / 主タグ
- ABC421 F「Erase between X and Y」 公式問題主題: 要素索引と連結リストで局所linkを更新する / 主タグ