DListとは

DListは、各ノードに前後両方にポインタを持つ双方向連結リスト(Doubly Linked List)です。そのため、O(1)の複雑度でノードの挿入、削除、参照操作を実現できます。

単方向リストに比べて、双方向リストは、特定のノードが与えられたときの直前のノードへの直接アクセスなど、いくつかの操作でより便利です。ただし、直前のノードのアドレスを格納するための追加のポインタが必要となるため、双方向リストのメモリ消費は比較的多くなります。

逐次挿入および削除が行われ、任意の場面でのアクセスが必要な場面、例えばLRUキャッシュなどに適しています。