連結リスト
someNode は空でないリストにある何らかのノードであるとする。ここでは任意の "someNode" から繰り返しを開始するものとしている。
順方向
逆方向
ループの最後で終了条件のチェックをしている点に注意されたい。これは、リストに "someNode" という1つのノードしかない場合に重要である。
次の関数は双方向循環リスト上のノードの次に新たなノードを追加する。
"insertBefore" を実現したければ、単に "insertAfter(node.prev, newNode)" を行えばよい。空のリストへのノードの追加は次の特殊関数が必要となる。
先頭に挿入したければ、"insertAfter(list.lastNode, node)" を実行すればよい。ノードの削除では空のリストにうまく対処する必要がある。
双方向リストと同様、"removeAfter" と "removeBefore" は "remove(list, node.prev)" と "remove(list, node.next)" で実現可能である。
連結リストを操作する場合、無効化され使われなくなった値の扱いに注意する必要がある。そのため、連結リストでの挿入・削除のアルゴリズムはある意味で巧妙である。ここでは、片方向リスト、双方向リスト、循環リストでのノードの追加と削除に関する擬似コードを示す。リストの終端を表すマーカー(あるいは番兵)としては "null" を使うが、その実装は様々なものが考えられる。
双方向循環リスト(doubly-circularly-linked list)では、各ノードは線形の双方向リストと同じように2つのリンクを持つが、先頭ノードの後方リンクは最後尾ノードを指し、最後尾ノードの前方リンクは先頭ノードを指す。双方向リストと同様、挿入も削除もその位置に隣接するノードへの参照が1つあれば、高速に行える。構造的には双方向循環リストには先頭も最後尾もないが、一般に外部のアクセスポインタを用意して、先頭または最後尾のノードを指しておくことが多い。そして、双方向リストでの番兵ノードのように順序を把握するのに使われる。
リンクとしてアドレスを使っていないので、リロケータブル(メモリ上でコピー可能)である。また、直接シリアライズしてディスクやネットワークに転送可能である。
小さいリストの場合、配列インデックスの方がポインタよりも小さくて済むことが多い。
ノードがメモリ上に連続して存在するため、参照の局所性が向上する可能性がある。
素朴な動的メモリ確保でノード用にメモリを割り当てると無駄が生じる可能性があるが、この方式ではノード毎のオーバーヘッドはほとんどない。
事前に配列として確保されている範囲では、動的メモリ確保よりもノードの生成が高速化される。
ただし、この方式にはノード群のためのメモリ領域管理を独自に行わなければならないという欠点がある。このため、次のような問題が生じる。
実装が複雑になる。
全ノードを使い切ったとき、配列の拡張が困難か不可能な場合がある。汎用のメモリプールからノード用にメモリを確保するほうが容易である。
動的配列に要素を追加しようとすると、予期しないタイミングで定数時間ではなく線形時間(O(n))がかかってしまう(平均すれば定数時間と言える)。
予想したよりもノード数の使用量が少ないと、メモリを無駄に確保することになる。
以上のような理由から、この手法は動的メモリ確保をサポートしていない言語で主に利用される。問題の多くは、配列生成時にリストの最大サイズが分かっている場合には問題ではなくなる。
同様の論文は1964年4月、Communications of the ACM に Bobrow と Raphael の "A Comparison of list-processing computer languages" が掲載されている。
Technical Systems Consultants (TSC) 社は、片方向リストをファイル構造に利用したオペレーティングシステム FLEXを開発した。ディレクトリがファイルの第一セクターを指し、その後のファイルの中身も線形リストのポインタを辿ることで得られるようになっていた。FLEX から派生したオペレーティングシステムとして Smoke Signal Broadcasting社が開発したものがあるが、こちらは双方向リストを同じ用途に使っていた。
IBM社が System/360やSystem/370向けに開発したTSSでも、ファイルシステムに双方向リストを使っていた。そのディレクトリ構造は UNIX のものと似ており、ディレクトリはファイルや他のディレクトリを格納でき、任意の深さまで階層構造を作ることができた。システムがクラッシュしたとき、このファイルシステム構造の一部がディスクに書き戻されていない場合があり、これを修復するためのユーティリティ "flea" が開発された。これは双方リストの前方リンクと後方リンクの一貫性をチェックすることで問題を検出する。
連結リストで特定の要素を探す場合、たとえそれがソート済みであっても一般に O(n) の時間を要する(線型探索)。これは連結リストの重大な欠点である。これを改善するいくつかの方法が存在する。
ソートされていないリストでは、平均検索時間を短縮する単純なヒューリスティックとして "Move To Front" と呼ばれる手法がある。これは、1度検索して見つかったノードをリストの先頭に移動させるという方式である。これは一種の簡単なキャッシュ構成法であり、最も後に検索したノードを再度検索する場合に高速化される。
もう1つの一般的な手法は、より効率的な外部のデータ構造を使ってノードにインデックスを付けるというものである。例えば、赤黒木やハッシュテーブルを構築し、その要素が連結リストの各ノードへの参照を持つようにする。1つのリストに対して、そのようなインデックスを複数構築できる。この手法の欠点は、ノードの追加や削除の度にインデックス側の更新が必要となる点である。少なくともインデックスを再利用する前に更新が必要である。
LISPやScheme、Prologといったプログラミング言語は、片方向リストを組み込みで装備している。多くの関数型言語では、リストを構成するノードを「consセル」と呼ぶ。consセルには "car" 部分と "cdr" 部分があり、"car" 部はそのノードのデータへの参照、"cdr" 部は次のノードへの参照を格納している。consセルは他のデータ構造にも使われるが、主な用途はリストを構成することである。
抽象データ型やテンプレートをサポートする言語では、連結リストの抽象データ型やテンプレートを使って、連結リストを構築できる。
オブジェクト指向プログラミング言語では、次のようなクラスが連結リスト用に用意されている。
C++(STL) - std::list<T>クラス(<list>)
Java - java.util.LinkedListクラス
.NET - System.Collections.Generic.LinkedList<T>クラス
以下に、C言語での片方向リストの例を示す。