Singly-Linked List in Rust
本記事は“Open Data Structures” を翻訳した書籍である『みんなのデータ構造』 の第3章を参考にし、Rustで実装したSingly-Linked List(以下、SLListと呼ぶ)について書いてある。
SLListはNodeから構成されており、Nodeはデータと隣のNodeへの参照を持つ。また、SLListはListの先頭への要素の追加、Listの末尾への要素の追加、Listの先頭から要素の取り出しの実行時間がO(1)なるListである。Queue 操作( add(x) 、 remove() )と、 Stack 操作( push(x) 、
pop() )を実装しており、処理の流れは以下のようになる。
[Some(ptr)] -> (1, Some(ptr)) -> (2, None)Stack: push(3)
[Some(ptr)] -> (3, Some(ptr)) -> (1, Some(ptr))-> (2, None)Stack: pop()
[Some(ptr)] -> (1, Some(ptr))-> (2, None)Queue: add(4)
[Some(ptr)] -> (1, Some(ptr)) -> (2, Some(ptr))-> (4, None)Queue: remove()
[Some(ptr)] -> (2, Some(ptr))-> (4, None)
削除(要素の取り出し)はリストの先頭に対する処理のため、pop()とremove()は同様の処理である。
Listの末尾への要素の追加をO(1)で行うために、SLListは末尾のNodeへの参照を保持する必要があり、以下のようなデータ構造にした。
struct SLList<T> {
head: Link<T>,
tail: *mut Node<T>,
}type Link<T> = Option<Box<Node<T>>>;struct Node<T> {
elem: T,
next: Link<T>,
}
Rustで実装する際に、比較的難易度が高いのはListの末尾への要素の追加(add())だと思われる。SLListのtailの型をheadの型と同じOption<Box<Node<T>>>にする場合は、BoxがCopyトレイトを実装していないという問題がある。また、SLListのtailの型をOption<&'a mut Node<T>>にする場合は、ミュータブルな参照を複数の箇所からされる問題がある。これらの理由によりraw pointerを使用している。
Rustで以下のようにSLListの実装した。
raw pointerは作成時は安全であるが、参照外しの際は安全性が保証されないため、add()の中がunsafeなコードになっている。また、*mut Tはnullableであり、std::ptr::null_mut()でnullを表現している。
