Rustにおけるリンクリスト

Rust で連結リストを学ぶのは非常に面倒で、初めてOption<Box<LinkedList>>のような表現を見ると純粋な狂気です。ここでは、私にとって馴染みのないことについて書き留めていますが、それはたくさんあります！

概念#

Rust で定義された連結リストを使用する一つの方法は、Option<Box<LinkedList>>のように、オブジェクトの 1) オプションの存在（cpp のnullptrのような）と 2) 次の要素への固定サイズのポインタを保証するために 2 つのラッパーを使用することです。

以下の概念は、Rust における LinkedList の操作で発生します。一般的に、Linked List の操作を行うためにOption型のas_mut()およびtake()メソッドを使用したいと思うでしょう。

Mermaid Loading...

takeのシグネチャ：

pub fn take(&mut self) -> Option(T)

take()は元のOptionオブジェクトまたはResultをデフォルト値（それぞれNoneまたはErr）で埋めます。これは、可変参照から可変Option()列挙型の所有権を取得するために使用されます。

そのようなOptionに対して可変参照を作成するには、Optionに実装されたas_mut()トレイトを使用して、&mut Option<T>からOption<&mut T>に変換します。シグネチャは以下の通りです：

fn as_mut(&mut self) -> &mut T;

これらの魔法を使って、最終的に cpp でnode1.next = node2; auto tmp = node2.next;のような操作を次のように行うことができます：

// ポインタを別のものに変更する
node2.as_mut()?.next = node1;
// 現在のノードから独立した変数に次を移動する
let node3 = node2.as_mut()?.next.take();
// オブジェクト自体を移動するのは簡単
node1 = node2;
node2 = node2;

なぜ`Box`を使うのか？#

Rust において、Box型はヒープに割り当てられたデータのためのスマートポインタです。Boxがスコープを外れると、そのデストラクタが呼ばれ、ヒープメモリが解放されます。

LinkedListのListNodeにBoxを使用する理由は、Rust の所有権とサイズ要件によるものです。Rust では、すべての変数とデータはコンパイル時に既知のサイズを持たなければなりません。しかし、LinkedListは再帰的なデータ構造であり、ノードが別のノードを含むことができます。Boxなしで定義しようとすると、各ノードが別のノードを含み、それがさらに別のノードを含むため、無限のサイズになります。

Boxを使用することで、ListNodeを親ノードに直接ではなくヒープに保存しています。これにより、親ノードは既知のサイズ（ヒープメモリへのポインタ）を持つBoxのみを保存する必要があります。

以下はListNodeの例です：

pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

この定義では、各ListNodeは次のListNodeを指すBoxを含む可能性のあるOptionを含んでいます。OptionはnextフィールドがNone（次のノードがないかもしれない）であることを示すために使用され、Boxは次のListNodeをヒープに保存するために使用されます。

したがって、Optionだけでは不十分で、サイズ要件の問題を解決しません。ListNodeをヒープに割り当て、nextフィールドの既知のサイズを持つためにBoxが必要です。

では、サイクル連結リストをどう作るのか？#

Boxはスマートポインタ、またはより具体的には cpp のユニークポインタです。これは、Boxで作成された連結リストがサイクルを持たないことが保証されることを意味します。なぜなら、Boxは指しているデータの排他的な所有権を持ち、同じデータへの複数の可変参照を防ぎ、潜在的なデータ競合を回避するからです。

Rust におけるLinkedListでサイクルを作成することは、Rust の所有権モデルとデータ競合を防ぐ方法のために確かに難しいです。しかし、Rust でサイクルやより複雑な構造を作成する方法はありますが、それにはRc（参照カウント）およびRefCell型を使用する必要があります。Rcは同じデータの複数の所有者を許可し、RefCellは内部可変性を許可します。つまり、不可変参照があってもデータを変更できます。

以下はサイクルを作成する例です：

use std::rc::Rc;
use std::cell::RefCell;

struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

fn main() {
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: None }));
    let node2 = Rc::new(RefCell::new(Node { value: 2, next: Some(node1.clone()) }));

    // サイクルを作成
    node1.borrow_mut().next = Some(node2.clone());
}

この例では、node1がnode2を指し、node2が再びnode1を指してサイクルを作成しています。Rc型は両方のノードが互いに所有することを可能にし、RefCell型はnode1が初めは不変であってもnode2を指すように変更することを許可します。

ただし、このようなサイクルはメモリリークを引き起こす可能性があります。この例では、node1とnode2はサイクルのために常に参照カウントがゼロより大きいため、解放されることはありません。Rust のRc型にはサイクルを検出または処理する方法がありません。

したがって、Rust のLinkedListでサイクルを作成することは可能ですが、メモリリークを避けるために非常に注意深く行うべきです。

参考文献#

サイクルのある連結リストの実用的な使用法は？（GPT4 からの回答）#

はい、実世界のアプリケーションにおいて循環またはサイクル連結リストの実用的な使用法はあります。以下はいくつかの例です：

ラウンドロビン・スケジューリング：これは、オペレーティングシステムや時間共有を扱う他のシステムで使用されるスケジューリングアルゴリズムの一種です。タスクのリストは循環連結リストに保持され、スケジューラはタスクを回転させて、それぞれに実行するための小さな時間スライスを与えます。タスクがターンを終えたら、スケジューラは循環リストの次のタスクに移動します。
マルチプレイヤーボードゲーム：多くのマルチプレイヤーゲームでは、ターン制システムを循環連結リストで実装できます。各ノードはプレイヤーを表し、現在のノードはターンを持つプレイヤーを表します。各ターンの後、ゲームは循環リストの次のプレイヤーに進みます。
画像カルーセルまたはスライドショー：ウェブまたはモバイルアプリケーションでは、画像カルーセルやスライドショーが循環連結リストを使用して画像を循環させることがあります。ユーザーが最後の画像に達すると、次の画像は最初の画像になり、シームレスなループを作成します。
CPU キャッシュの組織：コンピュータアーキテクチャでは、一部のキャッシングシステムが循環バッファ（循環連結リストで実装可能）を使用してメモリを管理します。
ナビゲーションシステム：一部のナビゲーションシステムは、オプションやメニューを循環するために循環連結リストを使用します。

これらは実用的な使用法ですが、他のデータ構造（配列や配列リストなど）を使用して同じ目標を達成することができ、時にはより良いパフォーマンス特性を持つことがあることに注意する価値があります。データ構造の選択は、状況の特定の要件に依存します。