連結リスト
連結リストは配列と比較したとき、いくつかの利点を持つ。リストでは要素の挿入は無制限に可能であるが、配列はサイズが決まっているために限界があり、配列を大きくしようとしても、メモリのフラグメンテーションによって不可能なこともある。同様に、配列から要素の多くを削除すると領域の無駄となったり、サイズを小さくする必要が生じる。
複数のリストが尾部を共有することで、さらにメモリを節約できる場合もある。つまり、先頭が複数あって、末尾が1つになっている構造が可能である。これを使って、何らかのデータの古いバージョンと新しいバージョンを同時に保持することが可能であり、簡単な永続データ構造の例となっている。
一方、配列はランダムアクセス性に優れており、連結リストがシーケンシャルアクセスを得意とするのと対照的である。片方向リストは一方向にしか辿れない。従って、ヒープソートのようにインデックスによって高速に要素を参照する必要がある場合、連結リストは不向きである。シーケンシャルアクセスも多くのマシン上では、連結リストよりも配列の方が高速である。これは、キャッシュメモリの効果と参照の局所性によるものである。連結リストはキャッシュメモリからはほとんど何も恩恵を受けない。
連結リストの別の欠点は、参照のための余分な領域を必要とする点である。このため、キャラクタやブーリアン型のような小さなデータ要素を連結リストで操作するのは(1文字ごとにノードを割り当てて文字列操作を実現するなど)、速度の面でもメモリ消費の面でも無駄が多く、現実的でない。
循環リストには、片方向のものと双方向のものがある。循環リストでは環状にノードが連結されているので、"null" は使わない。キューのような前後関係のあるリストでは、リストの最後尾ノードへの参照を保持する必要がある。循環リストでは最後尾ノードの次のノードは先頭ノードである。要素の最後尾への追加や先頭からの削除は定数時間で可能である。
循環リストの利点は、任意のノードから開始してリスト全体をたどることができる点である。このため、"firstNode" や "lastNode" も保持する必要がないことが多いが、空のリストを表すには何らかの特別な表現が必要である。ここでは "lastNode" に "null" を格納することで空のリストを表す。これにより空でないリストでの追加・削除は大幅に単純化されるが、空のリストを特殊ケースとして扱う必要がある。
双方向リストでは更新すべきポインタが増えるが、逆方向のポインタでリスト上の前の要素を参照できるため、操作に必要な情報は少なくて済む。これにより、新たな操作が可能となり、特殊ケースの関数が不要になる。ノードには前の要素を指す "prev" フィールドが追加される。また リスト構造の "lastNode" が最後尾のノードを指す。空のリストの場合、"list.firstNode" も "list.lastNode" も "null" である。
双方向リストでは双方向に繰り返しが可能である。方向は必要に応じて何度でも変えられる。
順方向
逆方向
指定したノードの次に新たなノードを挿入する関数と、前に挿入する関数を示す。
空のリストを含むリストの先頭に新たなノードを挿入する関数が必要となる。
同様に、最後尾にノードを挿入する関数を示す。
ノードの削除は簡単で、firstNode と lastNode にだけ注意すればよい。
この手続きで、リストから1つだけ残っているノードを削除する場合、"firstNode" と "lastNode" が "null" に設定され、正しく処理が行われる。また、"removeBefore" や "removeAfter" といった手続きは不要であり、単に "remove(node.prev)" や "remove(node.next)" を呼び出せばよい。
双方向リストはノード毎に要するメモリ量が多くなるし、基本的な操作にかかる手間が多くなる。しかし、どちらの方向にもシーケンシャルアクセス可能であるため、扱いやすくなることが多い。特に、あるノードの削除をする場合、そのノードのアドレスさえ分かっていれば、定数時間でそれが可能である。挿入の場合も、挿入する位置(そのノードの前に新たなノードを挿入する)が判っていれば、双方向リストでは定数時間で挿入が可能である。片方向リストでは、挿入・削除の際に1つ前のノードのアドレスも知る必要がある。アルゴリズムによっては双方向のアクセスが必須な場合もある。一方、双方向リストでは尾部の共有はできないので、永続データ構造としては使えない。