data-structures - ノードベースのデータ構造の不変性

Question

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

Answer 1

不変リストは基本的に通常の連結リストと同じように表されますが、通常リストを変更するすべての操作は代わりに新しいリストを返します。この新しいリストは必ずしも以前のリスト全体のコピーを含む必要はありませんが、その要素を再利用できます。

次の操作を次の方法で実装することをお勧めします。

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