Rust で Linked List を実装する(1. 単方向連結リスト編)

はじめに

Rust を勉強したいので Linked List を実装します。
元ネタは Introduction - Learning Rust With Entirely Too Many Linked Lists
リンク先では スタック \rightarrow 永続スタック \rightarrow 双方向 Linked List \rightarrow ... といった順で解説が書かれていて、読み物としても面白いので目を通すことをおすすめします。

とりあえず(単方向)Linked List を実装したので備忘録的に記事を書きます。
まだ上記リンクの3章までしか実装していないので、Linked List とは言っても機能的にはスタック(C++ の std::stack)と呼んだ方が適切かもしれません。

ソースコードsingle linked list · GitHub に置いてあります
Rust 何も分かってないので間違えていたらコメント欄かどこかで教えてください。

環境

  • OS: Windows 10 Home + WSL
  • rustc: ver. 1.44.0
  • エディタ: VSCode + Rust(extension)

Linked List

こんな感じのデータ構造。

f:id:zaki_joho:20200616235214p:plain
単方向リスト

できる操作は

  • 先頭への要素の挿入
  • 先頭要素へのアクセス
  • 先頭要素の削除
  • 素数の取得

で、いずれも O(1) です。
今回はこれらの操作に加え、先頭からシーケンシャルアクセスが可能なイテレータを実装します。

実装

構造体

まずは Linked List を表す構造体を実装します。

struct Node<T> {
    elem: T,
    next: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct List<T> {
    head: Link<T>,
    size: u32,
}

各ノードは値と次のノードへのリンクを保持します。

Option<Box<Node<T>>>

の形でリンクを表すことで、次のノードが存在しないことを None で表現することができます。
リスト自体には先頭要素へのリンクのみを保持します。

操作

リストが定義できたので各操作を実装していきます。

impl<T> List<T> {
    fn new() -> Self {
        List {
            head: None,
            size: 0,
        }
    }

    fn push(&mut self, elem: T) {
        self.size += 1;
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    fn pop(&mut self) -> Option<T> {
        match self.head.take() {
            None => None,
            Some(node) => {
                self.size -= 1;
                self.head = node.next;
                Some(node.elem)
            }
        }
    }

    fn top(&self) -> Option<&T> {
        match &self.head {
            None => None,
            Some(node) => Some(&node.elem),
        }
    }

    fn top_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| &mut node.elem)
    }

    fn is_empty(&self) -> bool {
        match &self.head {
            None => true,
            Some(_) => false,
        }
    }

    fn len(&self) -> u32 {
        self.size
    }

    fn clear(&mut self) {
        self.size = 0;
        self.head = None;
    }
}

take(), as_mut() がやばいですね、コンパイラに怒られまくった。
ここまでの実装でスタックとしては利用できるはずですが、先頭以外の要素も見たいのでシーケンシャルアクセスのできるイテレータを実装していきます。

イテレータ

ここで出てくる関数名とかは std::collections::LinkedList - Rust に従っているはずです、多分。
まずはイテレータを表す構造体を宣言しましょう。

struct IntoIter<T>(List<T>);

struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

<'a> とかが出てきましたね。ライフタイムは完全に理解していないので言及しません、コンパイラが全てを教えてくれます。
リストからイテレータを取得する関数を実装します。

impl<T> List<T> {
    fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter {
            next: self.head.as_ref().map(|node| &**node),
        }
    }

    fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
        IterMut {
            next: self.head.as_mut().map(|node| &mut **node),
        }
    }
}

(&mut **node) がやばいですね、解説は最初に挙げた元ネタに書かれているので気になる人はそちらを読んでください。
さて、ここで Iterator trait を見てみましょう。

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

要素の型を表す Item と次の要素を指すイテレータを得る関数 next() が必要なようです、これも実装していきましょう。

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

完成!

感想

ライフタイム全然分からない。コンパイラに言われるとおりに直したら動いたのでヨシ。
as_mut() と as_ref() が良く分かっていない気がするのでちゃんとドキュメント読みたいね。
やる気と時間があれば続きを書く予定です。

ところでこんな記事を書いている場合ではない。論文を、書こうね!