連結リスト
番兵ノードを使えば、全てのノードに次のノードや前のノードが存在することを保証でき、特定のリスト操作を単純化できる。しかし、(特に小さなリストを多数使用する場合)余分な領域を必要とするという欠点があり、他のリスト操作は逆に複雑化する。余分な領域を消費するのを防ぐため、番兵ノードはリストの先頭あるいは最後尾のノードへの参照として再利用されることがある。
線形リストには、片方向リストと双方向リストがあり、どちらも任意の位置でデータの追加・削除が"O(1)"時間でできるのが特長である。しかし、ソートされた配列や木構造と違い、データの検索はO(n)時間かかってしまうという欠点がある(ソートされていない配列は線形リストと同じ"O(n)"の検索時間である)。
片方向リスト(singly-linked list)は、最も単純な連結リストであり、ノード毎に1つのリンクを持つ。このリンクはリスト上の次のノードを指し、リストの最後尾ならNull値を格納するか、空のリストを指す。
ここでのノードのデータ構造には2つのフィールドがある。また、List の "firstNode" というフィールドがリストの先頭ノード(空のリストの場合は "null")を指すとする。
片方向リストを辿るのは単純で、先頭ノードから各ノードの "next" リンクを最後まで辿っていく。
次のコードは片方向リスト上のあるノードの次に新たにノードを挿入する。あるノードの前にノードを挿入することはできない。その場合は挿入位置の前のノードを見つける必要がある。
リストの先頭にノードを追加する場合、別の関数が必要である。この場合、firstNode を更新しなければならない。
同様に、指定されたノードの次のノードを削除する関数と、リストの先頭のノードを削除する関数を示す。特定のノードを探して削除する場合、その前のノードを覚えておく必要がある。
removeBeginning() は、削除するノードが最後のノードだった場合、"list.
双方向リスト(doubly-linked list)は、より洗練された連結リスト。各ノードには2つのリンクがあり、1つが次のノード(前方リンク)、もう1つが後ろのノード(後方リンク)を指す。リストの先頭のノードには後ろのノードがないので、後方リンクにはヌル値を格納するか、空のリストを指す。リストの最後尾のノードには次のノードがないので、前方リンクにはヌル値を格納するか、空のリストを指す。
低レベルの言語の中には、XOR連結リストを使って双方向リストの2つのリンクを1つのワードで表せるようにしたものもあるが、この技法は一般には使われない。
スタックとキューは連結リストを使って実装されることが多く、単にリストで許されている操作を制限するだけでよい。
スキップリストは、ポインタが階層化された連結リストであり、多数のノードを高速に飛ばして検索可能である。
二分木は、データ部も同じような連結リストへのリンクになっている連結リストと見なすこともできる。各ノードは2つのノードへのリンクになっており、それぞれが部分木の頂点を指している。
unrolled linked list は、各ノードに配列が置かれている形式の連結リストである。主に参照の局所性を高め、性能を向上させる目的で使われる。
ハッシュテーブルは、ハッシュ値が衝突しているデータを保持する際に連結リストの構造を使うことがある。