📌
Rustで単方向LinkedListを書いてみる
概要
「みんなのデータ構造」という本を読んでいて、Rustの練習に良さそうなので、色々書いてみる。
まずは単方向のLinkedListを書いてみる。
インタフェース
単方向リストのインタフェースは次の通り。
LIFO（Last In First Out）のスタック操作とFIFOのキュー操作を持つ。
pub trait ListInterface<T: std::fmt::Debug> {
fn new() -> Self;
/* スタックの操作 */
fn push(&mut self, element: T);
fn pop(&mut self) -> Option<T>;
/* キューの操作 */
fn add(&mut self, element: T);
fn remove(&mut self) -> Option<T>;
}
データ構造
データの構造は、格納データを持つ Node と Nodeへの参照を持つ List を使う。
#[derive(Debug)]
struct Node<T> {
// 格納するデータ
element: T,
// 次のノードへの参照
next: Option<Arc<Mutex<Node<T>>>>,
}
#[derive(Debug)]
pub struct List<T: std::fmt::Debug> {
// 先頭のノードへの参照
head: Option<Arc<Mutex<Node<T>>>>,
// 最後のノードへの参照
tail: Option<Arc<Mutex<Node<T>>>>,
// Listのサイズ
size: usize,
}
ノードへの参照は、Arcを使う。
Arcは基本的に、参照先の変更を許していないため、参照の書き換えを行うためにMutexでNodeをラップする。
スタック操作
値の追加(push)
// 先頭に値を追加する
pub fn push(&mut self, element: T) {
let new_node = Arc::new(Mutex::new(Node {
element,
// NOTE: takeは、Option型から値を取り出して、なければNoneを返す。
next: self.head.take(),
}));
self.head = Some(Arc::clone(&new_node));
// NOTE: Stackの場合は、最初の値が末尾になるため、sizeが0の場合のみtailを更新する
if self.size == 0 {
self.tail = Some(Arc::clone(&new_node));
}
self.size += 1;
}
rust特有のコードとしては、Option型のtake()とArc::cloneあたり。
Arc::clone(&node) と node.clone() は等価だが Arcの参照クローンを明示するために Arc::cloneを使う。
値の取得(pop)
// 先頭から値を取り出す
pub fn pop(&mut self) -> Option<T> {
if self.size == 0 {
return None;
}
// NOTE: 先に self.tail を None にしておかないと、headから値を取り出せない(Arc::try_unwrap)
if self.size == 1 {
self.tail = None;
}
match self.head.take() {
None => None,
Some(old_head) => {
// NOTE: このcloneは、Option::cloneだが、Optionの中身はArcなので、Arc::cloneと同じ挙動をする
self.head = old_head.lock().unwrap().next.clone();
self.size -= 1;
match Arc::try_unwrap(old_head) {
Ok(node) => Some(node.into_inner().unwrap().element),
Err(_arc) => None,
}
}
}
}
Arc::try_unwrap は、Arc<T> の値を取り出して所有権の移動を行うが、参照カウントが1(最後の参照)でない場合はエラーになってしまう。
そのため、self.size == 1 の場合は、先にtailにNoneを入れ、参照カウントを1にしてから、Arc::try_unwrapで値を取り出している。(self.size == 1のときは、tailとheadに同じ値の参照が入るため）
old_head.lock().unwrap().next.clone() は、headの次の値を取り出して、cloneしている。
nextが指す値は、実際は Option<Arc<Mutex<Node<T>>>> 型だが、Optionにcloneを掛けたときは、Optionの中の値がcloneされるため、Arc<Mutex<Node<T>>> がクローン、つまり、Arc::cloneと同じ挙動になる。
キュー操作
値の追加
// 末尾に値を追加する
pub fn add(&mut self, element: T) {
let new_node = Arc::new(Mutex::new(Node {
element,
next: None,
}));
match self.tail.take() {
// NOTE: tailに値がない = リストの要素が0
None => {
self.head = Some(Arc::clone(&new_node));
self.tail = Some(Arc::clone(&new_node));
}
Some(old_tail) => {
// NOTE: mutexを使わない場合、Arcの値を書き換えることができない
old_tail.lock().unwrap().next = Some(Arc::clone(&new_node));
self.tail = Some(Arc::clone(&new_node));
}
}
self.size += 1;
}
キューは末尾に値を追加するため、tailのnextを追加する要素の参照に更新する必要がある。
Arcの値は、本来書き換え不可だが、Mutexによるlockを行うことで書き換えることができる(old_tail.lock()箇所)
値の取り出し
pub fn remove(&mut self) -> Option<T> {
if self.size == 0 {
return None;
}
if self.size == 1 {
self.tail = None;
}
match self.head.take() {
None => None,
Some(old_head) => {
self.head = old_head.lock().unwrap().next.clone();
self.size -= 1;
match Arc::try_unwrap(old_head) {
Ok(node) => Some(node.into_inner().unwrap().element),
Err(_arc) => None,
}
}
}
}
removeについては、先頭から値を取り出すため、popと同じ挙動になる。
コード全体
コード
use std::sync::{Arc, Mutex};
pub trait ListInterface<T: std::fmt::Debug> {
fn new() -> Self;
/* スタックの操作 */
fn push(&mut self, element: T);
fn pop(&mut self) -> Option<T>;
/* キューの操作 */
fn add(&mut self, element: T);
fn remove(&mut self) -> Option<T>;
}
#[derive(Debug)]
struct Node<T> {
element: T,
next: Option<Arc<Mutex<Node<T>>>>,
}
#[derive(Debug)]
pub struct List<T: std::fmt::Debug> {
head: Option<Arc<Mutex<Node<T>>>>,
tail: Option<Arc<Mutex<Node<T>>>>,
size: usize,
}
impl<T: std::fmt::Debug> Default for List<T> {
fn default() -> Self {
Self {
head: Default::default(),
tail: Default::default(),
size: Default::default(),
}
}
}
impl<T: std::fmt::Debug> List<T> {
pub fn new() -> Self {
Default::default()
}
// 先頭に値を追加する
pub fn push(&mut self, element: T) {
let new_node = Arc::new(Mutex::new(Node {
element,
next: self.head.take(),
}));
self.head = Some(Arc::clone(&new_node));
// NOTE: Stackの場合は、最初の値が末尾になるため、sizeが0の場合のみtailを更新する
if self.size == 0 {
self.tail = Some(Arc::clone(&new_node));
}
self.size += 1;
}
// 先頭から値を取り出す
pub fn pop(&mut self) -> Option<T> {
if self.size == 0 {
return None;
}
// NOTE: 先に self.tail を None にしておかないと、headから値を取り出せない(Arc::try_unwrap)
if self.size == 1 {
self.tail = None;
}
match self.head.take() {
None => None,
Some(old_head) => {
// NOTE: このcloneは、Option::cloneだが、Optionの中身はArcなので、Arc::cloneと同じ挙動をする
self.head = old_head.lock().unwrap().next.clone();
self.size -= 1;
match Arc::try_unwrap(old_head) {
Ok(node) => Some(node.into_inner().unwrap().element),
Err(_arc) => None,
}
}
}
}
// 末尾に値を追加する
pub fn add(&mut self, element: T) {
let new_node = Arc::new(Mutex::new(Node {
element,
next: None,
}));
match self.tail.take() {
// NOTE: tailに値がない = リストの要素が0
None => {
self.head = Some(Arc::clone(&new_node));
self.tail = Some(Arc::clone(&new_node));
}
Some(old_tail) => {
// NOTE: mutexを使わない場合、Arcの値を書き換えることができない
old_tail.lock().unwrap().next = Some(Arc::clone(&new_node));
self.tail = Some(Arc::clone(&new_node));
}
}
self.size += 1;
}
// 先頭から値を取り出す
pub fn remove(&mut self) -> Option<T> {
if self.size == 0 {
return None;
}
if self.size == 1 {
self.tail = None;
}
match self.head.take() {
None => None,
Some(old_head) => {
self.head = old_head.lock().unwrap().next.clone();
self.size -= 1;
match Arc::try_unwrap(old_head) {
Ok(node) => Some(node.into_inner().unwrap().element),
Err(_arc) => None,
}
}
}
}
}
fn main() {
let mut list = List::new();
list.push(1);
list.push(2);
list.pop();
list.pop();
list.add(3);
list.add(4);
list.remove();
list.remove();
println!("{:?}", list);
}
Discussion