[解決済み] ダブルリンクとは何ですか？

質問

の文章を読んでいました。 ここで とある一文で混乱しました。

このため、ダブルリンクや破壊的な更新などを気にしなければならない他の言語のリストよりも、基礎となるルーチンがはるかに高速になります。

ダブルリンクについてググってみたが、適切な定義が見つからなかった。著者が言う「ダブルリンク」とはどういう意味なのでしょうか？

どのように解決するのですか？

回答する前に、いくつかの定義と概念を理解する必要があります。

参照した文脈では 記事 は、リストの2つの概念である。

1. MLなどの関数型言語で使われるImmutableなリスト．
2. C, C++, Javaなどの命令型言語で使用されるリンクリスト(ミュータブルリスト)。

また、リストの作成方法、破棄方法、使用方法も異なります。

それぞれのリストを構築する必要がありますが、イミュータブルリストはリストの先頭にのみ新しい項目を追加して構築します。一方、リンクリストはリストのどこにでも項目を追加して構築できますが、通常、新しい項目はリンクリストの末尾に追加されます。

一方、リンクリストは前方にも後方にも移動でき、移動中に方向を変えることもできます。

リンクリストはデストラクタで破壊しなければならないが、イミュータブルリストはソースコード中のステートメントで破壊されず、ガベージコレクションで自動的に破壊される。

さらに、不変リストはすべて同じ型であるのに対し、リンクリストはさまざまな型のアイテムを保持することができます。

イミュータブルリストの制限により、任意の項目に対する操作は O (1). 例えば、リストに項目を追加する場合、常に先頭に追加されるため、O(1)となります。また、リスト内のある項目を使用する場合は、その項目が現在のリストの先頭であるため、O(1)となる。これを実現する方法は、関数型言語の中でリストが使われるとき、リストの先頭の項目が使われ、リストの末尾が新しい先頭になるように渡されることである。 1,2,3 というリストの先頭を使用します。 1 を渡すと、リスト 2,3 ここで 2 が新しい頭です。コンセプトとしては2つの異なるリストですが、これがどのように実装されるかの詳細は別の問題です。

作者が言う「"double-links"」とはどういう意味ですか？

ダブルリンクとは、以下のことを指します。 二重リンクリスト これは、リスト内の項目が前後の項目へのポインタを持つように構成できる言語でのリストです。

コメントでOPも聞いています。

シングルリンクのどこがシングルリンクより速いのか？ ダブルリンク

先の項で述べたように、リストに対するすべての演算がO(1)であることです。