連結リスト
連結リストは他のデータ構造の構成要素として使われる。例えば、スタック、キューなどである。
ノードのデータ部が別の連結リスト(へのポインタ)という構成も可能である。これを応用すると様々なデータ構造をリストで構成できる。これはLISPを起源とする方法であり、LISP では連結リストは主要なデータ構造とされ、今では関数型言語で一般に使われている。
連結リストを使って連想配列を実装することもあり、これを連想リスト(association list)と呼ぶ。このような連結リストの応用にはあまり利点がない。平衡2分探索木などのデータ構造の方が、ごく小さいデータ量であっても性能的に優れている。しかし、木構造のサブセットという範囲を超えて連結リストを動的に生成することもあり、より効率的にそのような構成のデータを扱うのに使われる。
これらの問題の一部を改善する連結リストの派生データ構造がいくつか存在する。Unrolled linked list は各ノードに複数の要素を格納するもので、キャッシュ性能を向上させ、参照時のメモリのオーバヘッドを低減させる。CDRコーディングも参照を参照すべき実データと置換することで同様の効果が得られる。
配列との比較で利点と欠点を明確にする好例として、ジョセファスの問題を解くプログラムの実装がある。ジョセファスの問題とは、人間が輪になって並んでいる状況で、そこから1人を選ぶというものである。ある人を開始点として、特定の方向に n 人を数えていく。n 番目の人に到達したら、その人を輪から外して、残りの人間で一回り小さい輪を作る。そして再び n 番目まで数えていく。これを1人だけが残るまで繰り返し、最後に残った人が選ばれた人ということになる。これを循環リストを使って表すのは直接的で分かり易いし、ノードの削除も簡単である。しかし、循環リストでは、現在のノードから n 番目のノードを見つけるには、リストを順に辿っていくしかない。配列であればインデックスの計算で即座に見つけられる。一方、配列では要素(ノード)の削除は容易ではなく、n 番目のノードを即座に見つけるという利点を生かすには、ノードを削除したときに残った要素を詰めてやる必要がある。
一般に、データ構造を複数の連結リストに属させる必要がある場合、外部収納が最善の手法である。データ構造が1つの連結リストにしか属さない場合、内部収納の方が若干良いが、外部収納の汎用リスト操作パッケージが利用可能なら、それを利用するほうがよい場合もある。
いくつかの言語で採用されている別の手法として、いくつかの種類のデータ構造があって、それらの先頭部分の同じ位置にリストのための "next" および "prev" のフィールドが存在する場合がある。この場合、リスト操作は汎用的なルーチンを使い、個々のノード内のデータは個別のルーチンで処理する。様々な種類のメッセージを受信する際の構文解析などでよく使われる。メッセージのキューへの追加と削除は汎用的なルーチンで行われる。メッセージの種類がメッセージの先頭にあり、それを見て適切なメッセージ処理ルーチンを呼び出す。