Rust で連結リストを反転してみる

linked-list-reverse.rs

/*
参考:
  3.2.3 テストケース: 連結リスト
  http://rust-lang-ja.org/rust-by-example/custom_types/enum/testcase_linked_list.html
*/

use List::*;

enum List {
    // Cons: これは、要素をラップし、次の要素へのポインタを保持するタプル
    Cons(u32, Box<List>),
    // Nil: 連結リストの終端であることを示すノード
    Nil,
}

// 列挙型にはメソッドを付与することができる。
impl List {
    // 空リストの作成
    fn new() -> List {
        // `Nil` は `List` 型を持つ。
        Nil
    }

    // リストを受け取り、その始端に新しい要素を付加したものを返す関数
    fn prepend(self, elem: u32) -> List {
        // この`Cons`自体も、その第２要素もどちらもList型である
        Cons(elem, Box::new(self))
    }

    // List の長さを返すメソッド
    fn len(&self) -> u32 {
        // このメソッドは、`self`の状態によって振る舞いが
        // 変化するため、match をする必要がある
        // `self` の型は `&List` であるので、`*self` は `List` になる。マッチングは
        // リファレンス (`&T`) ではなく実体 (`T`) に対して行うのが好ましい。
        match *self {
            // `self` をすでに借用しているので、tail の所有権を取ることができない。
            // 代わりに参照を使用する。
            Cons(_, ref tail) => 1 + tail.len(),
            // 空リストならば長さは0
            Nil => 0
        }
    }

    // List を heap 上の文字列として表したものを返すメソッド
    fn stringify(&self) -> String {
        match *self {
            Cons(head, ref tail) => {
                // `format!` は `print!` に似ているが、コンソール上に出力
                // する代わりに、heap上の文字列を返す。
                format!("{}, {}", head, tail.stringify())
            },
            Nil => {
                format!("Nil")
            },
        }
    }

    // [追加] リストを反転して連結しなおす
    fn reverse(&self, prev: Option<List>) -> List {
        match *self {
            // 要素
            Cons(head, ref tail) => {
                match prev {
                    // 再帰呼び出しされた時: 渡されたリストへ連結し再帰呼出し
                    Some(p) => tail.reverse(Some(Cons(head, Box::new(p)))),
                    // 初回呼び出し時: 終端要素として生成して再帰呼び出し
                    None => tail.reverse(Some(Cons(head, Box::new(Nil)))),
                }
            },
            // 終端
            Nil => {
                match prev {
                    // 完成したリストを返す(最後まで再帰したらリストが完成している)
                    Some(p) => p,
                    // Nil を返す(空リスト)
                    None => Nil,
                }
            },
        }
    }
}

fn main() {
    // 空の連結リストを作成
    let mut list = List::new();

    // 要素を追加
    list = list.prepend(1);
    list = list.prepend(2);
    list = list.prepend(3);

    // 追加後の状態を表示
    println!("linked list has length: {}", list.len());
    println!("{}", list.stringify());
    // [追加]反転した結果を表示
    let reversed_list = list.reverse(None);
    println!("reversed linked list has length: {}", reversed_list.len());
    println!("{}", reversed_list.stringify());
}

出力結果:

linked list has length: 3
3, 2, 1, Nil
reversed linked list has length: 3
1, 2, 3, Nil