2026-10-31
list_drop.rs
struct Node {
value: i32,
next: Option<Box<Node>>,
}
struct List {
head: Option<Box<Node>>,
}
impl Drop for List {
fn drop(&mut self) {
}
}
単方向連結リスト List の drop を書いてください。List を捨てたときに、ノードがいくつあってもスタックの深さが一定のまま、すべてのノードを解放します。リストは空のこともあります。例の make(n) は、値が 0 から n - 1 までの n 個のノードを順につないだ List を返す関数とします。
入力例 1
drop(make(3)); println!("done");
出力例 1
done
入力例 2
drop(make(1_000_000)); println!("done");
出力例 2
done
入力例 3
drop(make(0)); println!("done");
出力例 3
done
Reference
impl Drop for List {
fn drop(&mut self) {
let mut cur = self.head.take();
while let Some(mut node) = cur {
cur = node.next.take();
}
}
}
Drop を実装しなくても、List を捨てればノードはすべて解放されます。ただし、コンパイラが用意する drop は、head の Box<Node> を drop する中で Node の next を drop し、その中でさらに次の next を drop します。ノード1つにつき呼び出しが1段深くなるので、入力例2の100万個ではスタックを使い切り、プログラムは異常終了します。
参考実装では、まず self.head.take() で先頭のノードを取り出し、head を None にします。ループの中では node.next.take() で次のノードを cur に移してから、node はその回の終わりで捨てられます。捨てる時点の node の next は None なので、その drop は次のノードまで進まず、ノード1つ分で終わります。ノードを1つずつ同じループの中で解放するので、スタックの深さはノードの数によりません。
take を使うのは、drop が受け取るのが &mut self で、そこからフィールドの値を持ち出せないからです。take は中身を取り出して、代わりに None を置きます。
掲載したのは参考実装で、唯一の正解ではありません。Box からはフィールドを持ち出せるので、while let Some(node) = cur { cur = node.next; } と書いても同じように動きます。