リンクドリスト （データ構造）

序文

リンクドリストに関する些細なことを書き留める. 誰でも知っていると言われそうだが, 社内教育用のノートにするつもり.
以下は主にゲーム開発における見解である, と予防線を張っておく.
バスやキャッシュ機構を含むメインメモリアクセス速度とCPU速度の差が大きい2017年では,
メモリアドレスをベースとしたポインタでは出番の少ない構造.

リンクドリスト

概要

ポインタによって繋がれたデータ構造のこと.
前又は, 後だけを指すポインタを持つものは単方向リスト, 前後を指すポインタを持つものは双方向リストと区別したりする.
頻繁に要素の追加・削除, 移動があり, 尚且つ要素の構築・破壊, コピーのコストが高い場合に有効なデータ構造.

Boostのintrusiveに見られるように, ポインタを要素に埋め込み, メモリ確保オーバーヘッドを削減する方法がある.
ポインタを配列のインデックスで表現し, ポインタを要素に埋め込むと効率がよい.
フレームワークを使用していて, どうしても要素のメモリ確保が必要な場合活用できる場合がある.
スタックを別のデータ構造を利用して実現するなら動的配列で十分である.
キューなら配列を使ったリングバッファの方がよい.