連結リスト
データ構造の一つ。
各要素にデータと次のリストを指し示すためのポインタが格納されており、ポインタの情報を元にデータの関連が表現されるもの。
目的のデータを探す時には基本的には線型探索しか使えず、データがソートされていたとしても常に$ O(n)の時間を要するという欠点があるが、データの削除、追加はポインタの変更だけで済むため手間がかからず高速である。
連結リストを使って実装されることが多く、単にリストで許されている操作を制限するだけでよい。 ポインタが階層化された連結リストであり、多数のノードを高速に飛ばして検索可能である。
データ部も同じような連結リストへのリンクになっている連結リストと見なすこともできる。
各ノードは2つのノードへのリンクになっており、それぞれが部分木の頂点を指している。
各ノードに配列が置かれている形式の連結リストである。主に参照の局所性を高め、性能を向上させる目的で使われる。
ハッシュ値が衝突しているデータを保持する際に連結リストの構造を使うことがある。