ノードベースのデータ構造の不確かさ

Question

たとえば、次のような不変のバージョンを提供したい場合、一般的なアプローチはありますか？リンクされたノードのシーケンスとして実装されたLinkidList？私はArrayListの場合、基本的な配列をコピーすることを理解していますが、この場合、これは私にはわかりません...

Answer 1

不変リストは基本的にすべての操作通常はリストを変更して新しいリストを返します。この新しいリストには、必ずしも前のリスト全体のコピーを入れる必要はありませんが、その要素を再利用することができます。

Iは、次の方法で以下の操作を実施するお勧め：前部の要素をポップ

• ：単に次のノードへのポインタを返します。複雑さ：O（1）。
• 要素を前面に押す：古いリストの最初のノードを指す新しいノードを作成して返します。 O（1）。
• リストaをリストbに連結する。b：リスト全体をコピーし、最後のノードのポインタをリストbの先頭を指すようにする。これは、変更可能リストの同じ操作よりも高速です。 O（長さ（a））。
• 位置xに挿入する：すべてをxまでコピーし、新しい要素を含むノードをコピーの後ろに追加し、そのノードが位置x + 1の古いリストを指すようにします。
• 位置xでの要素の削除：実質的に挿入と同じです。 O（x）である。
• ソート：単純なクイックまたはマージソートを使用できます。変更可能なリストよりもはるかに速くも遅くもありません。唯一の違いは、ソートすることはできませんが、ソートする必要があることです。 O（n * log n）である。