Rustで単方向リストを実装する(Box版)

概要

腕試しに単方向リストを実装してみた。次の記事のBox版になります。作ってみてなんですが、Box版はないかな…と思います。

Rc<RefCell>版と unsafe版の記事はこちら。

• Rustで単方向リストを実装する(Rc<RefCell>版)
• Rustで単方向リストを実装する(unsafe版)

環境

• rustc 1.57.0 (Rust 2021)
• WSL1 (Ubuntu 18.04 LTS)

問題設定

• 単方向リスト

  • tail(末尾へのポインタ)をメンバーに持たない次のような構造体
  • push_back() ... 末尾に値を追加
    tailを含まないことで内部でリストをたどる処理が必要(実力を試される)
  • pop_back() ... 末尾から値を取り出す
  • pop_front() ... 先頭から値を取り出す
  • iter() ... イテレータ

• テスト

  • ソースの Example に記載の通り

pub struct ListNode<T> {
    value: T,
    next: Option<Box<ListNode<T>>>,
}

# [derive(Default)]
pub struct SinglyLinkedList<T> {
    head: Option<Box<ListNode<T>>>,
}

pub struct SinglyLinkedListIterator<'a, T:'a> {
    next: Option<&'a ListNode<T>>
}

impl<T> ListNode<T> {
    pub fn new(v: T) -> ListNode<T> {
        ListNode { value: v, next: None }
    }
}

impl<T> SinglyLinkedList<T> {
    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_using_box::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// ```
    pub fn push_back(&mut self, v: T) {}

    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_using_box::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.pop_back(), Some(2));
    /// assert_eq!(list.pop_back(), Some(1));
    /// assert_eq!(list.pop_back(), None);
    /// ```
    pub fn pop_back(&mut self) -> Option<T> { None }

    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_using_box::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.pop_front(), Some(1));
    /// assert_eq!(list.pop_front(), Some(2));
    /// assert_eq!(list.pop_front(), None);
    /// ```
    pub fn pop_front(&mut self) -> Option<T> { None }

   pub fn iter(&self) -> SinglyLinkedListIterator<'_,T> {}
}

実装例

Cargo.toml

[package]
name = "singly-linked-list-using-box"
version = "0.1.0"
edition = "2021"

[dependencies]

main.rs

use singly_linked_list_using_box::SinglyLinkedList;

fn main() {
    let mut list: SinglyLinkedList<u8> = Default::default();
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    println!("{}", list);

    assert_eq!(list.pop_front(), Some(1));
    assert_eq!(list.pop_front(), Some(2));
    assert_eq!(list.pop_front(), Some(3));
    assert_eq!(list.pop_front(), None);
    println!("{}", list);

    list.push_back(1);
    list.push_back(2);
    assert_eq!(list.pop_back(), Some(2));
    assert_eq!(list.pop_back(), Some(1));
    assert_eq!(list.pop_back(), None);

    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&1));
    assert_eq!(iter.next(), Some(&2));
    assert_eq!(iter.next(), Some(&3));
    assert_eq!(iter.next(), None);
}

lib.rs

• push_back() ... Rc版のように素直に実装できます
• pop_back() ... 一つ前のポインターを mut で記憶する必要があり、末尾の要素以外も replace で解体するのは苦肉の策という感じです
• pop_front() ... 先頭だけ扱えばよいので、ごく自然な実装
• iter() ... Clippyで &Box<T> でなく、 &T を使えと言われたのでそうしてます
  as_deref() に相当する部分は、事例だと self.head.map(|node| &**node) みたいな感じで Box外ししているものがありますが、Clippy 的に古い書き方みたいですね
• 最後のコメントアウトしているテストは Rc版では動作するのですが、Box版ではコンパイルエラーとなります
  イテレータ操作と pop_front() が同時にできて嬉しいことはないけれども、Box版の限界を感じさせるテストケースです

use std::fmt;

# [derive(Debug)]
struct ListNode<T> {
    value: T,
    next: Option<Box<ListNode<T>>>,
}

# [derive(Default, Debug)]
pub struct SinglyLinkedList<T> {
    head: Option<Box<ListNode<T>>>,
}

pub struct SinglyLinkedListIterator<'a, T:'a> {
    next: Option<&'a ListNode<T>>
}

impl<T: fmt::Debug> ListNode<T> {
    fn new(v: T) -> ListNode<T> {
        ListNode { value: v, next: None }
    }
}

impl<T: fmt::Debug> SinglyLinkedList<T> {
    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_using_box::v2::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// ```
    pub fn push_back(&mut self, v: T) {
        let mut cur_ref = match &mut self.head {
            Some(head_ref) => head_ref,
            None => {
                let node_new = ListNode::new(v);
                self.head = Some(Box::new(node_new));
                return;
            }
        };

        while let Some(ref mut next) = cur_ref.next {
            cur_ref = next;
        }

        cur_ref.next = Some(Box::new(ListNode::new(v)))
    }

    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_using_box::v2::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.pop_back(), Some(2));
    /// assert_eq!(list.pop_back(), Some(1));
    /// assert_eq!(list.pop_back(), None);
    /// ```
    pub fn pop_back(&mut self) -> Option<T> {
        use std::mem::replace;
        let cur = replace(&mut self.head, None);
        cur.as_ref()?;

        let mut cur = cur.unwrap(); // safe because of the check above
        if cur.next.is_none() {
            return Some(cur.value);
        }

        let mut prev_next = &mut self.head;
        while cur.next.is_some() {
            // Take ownership of the next element
            let n_next = replace(&mut cur.next, None).unwrap();

            // Update the previous element's "next" field
            *prev_next = Some(cur);

            // Progress to the next element
            cur = n_next;

            // Progress our pointer to the previous element's "next" field
            prev_next = &mut prev_next.as_mut().unwrap().next;
        }

        Some(cur.value)
    }

    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_using_box::v2::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.pop_front(), Some(1));
    /// assert_eq!(list.pop_front(), Some(2));
    /// assert_eq!(list.pop_front(), None);
    /// ```
    pub fn pop_front(&mut self) -> Option<T> {
        use std::mem::replace;
        let cur = replace(&mut self.head, None);
        cur.as_ref()?;

        let cur = cur.unwrap();
        self.head = cur.next;
        Some(cur.value)
    }

    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_using_box::v2::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// let mut iter = list.iter();
    /// assert_eq!(iter.next(), Some(&1));
    /// assert_eq!(iter.next(), Some(&2));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn iter(&self) -> SinglyLinkedListIterator<'_,T> {
        return SinglyLinkedListIterator {
            next: self.head.as_deref()
        }
    }
}

impl<T: fmt::Debug> fmt::Display for ListNode<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self.next {
            Some(ref next) => {
                write!(f, "ListNode({:?}), {}", self.value, next)
            },
            None => write!(f, "ListNode({:?})", self.value)
        }
    }
}

impl<T: fmt::Debug> fmt::Display for SinglyLinkedList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self.head {
            Some(ref head) => write!(f, "SinglyLinkedList[{}]", head),
            None => write!(f, "SinglyLinkedList[]")
        }
    }
}

impl<'a, T: fmt::Debug> Iterator for SinglyLinkedListIterator<'a,T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_deref();
            &node.value
        })
    }
}

# [cfg(test)]
mod tests {
    use super::SinglyLinkedList;

    #[test]
    fn test_pop_front() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        assert_eq!(list.pop_front(), None);

        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), Some(2));
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), None);

        list.push_back(1);
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);

    }

    #[test]
    fn test_pop_back() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        assert_eq!(list.pop_back(), None);

        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);

        list.push_back(1);
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);
    }

    #[test]
    fn test_iter() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        let mut iter = list.iter();
        assert_eq!(iter.next(), None);

        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    #[ignore]
    fn test_iter_and_pop_front() {
        // let mut list: SinglyLinkedList<u8> = Default::default();
        // list.push_back(1);
        // list.push_back(2);
        // list.push_back(3);

        // let mut iter = list.iter();             // NG: immutable borrow occurs here
        // assert_eq!(list.pop_front(), Some(1));  // NG: mutable borrow occurs here
        // assert_eq!(iter.next(), None);          // NG: immutable borrow later used here
    }
}

おまけ

std::mem::replace の理解を深めるために作成したコードです。

ノード追加の小さな実装(3,2,1と逆順に追加)

3 を追加し、それを2にぶら下げて、さらにそれを1にぶら下げる…というやり方。

# [derive(Debug, PartialEq)]
pub struct ListNode<T> {
    pub value: T,
    pub next: Option<Box<ListNode<T>>>,
}

impl<T> ListNode<T> {
    pub fn new(v: T) -> ListNode<T> {
        ListNode { value: v, next: None }
    }
}

impl<T: std::fmt::Debug> std::fmt::Display for ListNode<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self.next {
            Some(ref next) => {
                write!(f, "ListNode({:?}, _), {}", self.value, next)
            },
            None => write!(f, "ListNode({:?}, None)", self.value)
        }
    }
}

fn main() {
    // use std::mem::replace;
    let mut some_boxed_node_1 = Some(Box::new(ListNode::new(1)));
    let mut some_boxed_node_2 = Some(Box::new(ListNode::new(2)));
    let mut some_boxed_node_3 = Some(Box::new(ListNode::new(3)));

    let mut cur: Box<ListNode<_>>;
    let mut next_node: Box<ListNode<_>>;
    let mut prev_next: &mut Option<Box<ListNode<_>>>;

    // cur = replace(&mut some_boxed_node_3, None).unwrap();
    cur = some_boxed_node_3.take().unwrap();
    assert_eq!(some_boxed_node_3, None);
    next_node = cur;

    // cur = replace(&mut some_boxed_node_2, None).unwrap();
    cur = some_boxed_node_2.take().unwrap();
    assert_eq!(some_boxed_node_2, None);
    prev_next = &mut cur.next;
    *prev_next = Some(next_node);
    next_node = cur;

    // cur = replace(&mut some_boxed_node_1, None).unwrap();
    cur = some_boxed_node_1.take().unwrap();
    assert_eq!(some_boxed_node_1, None);
    prev_next = &mut cur.next;
    *prev_next = Some(next_node);

    println!("{}", cur);
}

ノード追加の小さな実装(1,2,3と順に追加)

ノードをたどるにあたって、head を壊して next ポインターを取得する必要があります。
処理の終わりに head にぶら下げなおしています。

use std::mem::replace;

# [derive(PartialEq)]
pub struct ListNode<T> {
    pub value: T,
    pub next: Option<Box<ListNode<T>>>,
}

impl<T> ListNode<T> {
    pub fn new(v: T) -> ListNode<T> {
        ListNode { value: v, next: None }
    }
}

impl<T: std::fmt::Debug> std::fmt::Debug for ListNode<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self.next {
            Some(ref next) => {
                write!(f, "ListNode({:?}, _), {:?}", self.value, next)
            },
            None => write!(f, "ListNode({:?}, None)", self.value)
        }
    }
}

fn main() {
    let mut head: Option<Box<ListNode<u8>>> = None;

    // push_back(1)
    let some_boxed_node_1 = Some(Box::new(ListNode::new(2)));
    if head.is_none() {
        head = some_boxed_node_1;
        println!("1: {:?}", head);
    }

    // push_back(2)
    let some_boxed_node_2 = Some(Box::new(ListNode::new(2)));
    if head.is_some() {
        // let mut node1_cur = replace(&mut head, None).unwrap();
        let mut node1_cur = head.take().unwrap();
        if node1_cur.next.is_none() {
            let node1_cur_next = &mut node1_cur.next;
            *node1_cur_next = some_boxed_node_2;
        }
        head = Some(node1_cur);
        println!("2: {:?}", head);
    }

    // push_back(3)
    let some_boxed_node_3 = Some(Box::new(ListNode::new(3)));
    if head.is_some() {
        // let mut node1_cur = replace(&mut head, None).unwrap();
        let mut node1_cur = head.take().unwrap();
        if node1_cur.next.is_some() {
            let mut node2_cur = replace(&mut node1_cur.next, None).unwrap();
            if node2_cur.next.is_none() {
                let node2_cur_next = &mut node2_cur.next;
                *node2_cur_next = some_boxed_node_3;        
            }
            let node1_cur_next = &mut node1_cur.next;
            *node1_cur_next = Some(node2_cur);
        }
        head = Some(node1_cur);
        println!("3: {:?}", head);
    }
}

まとめ

実装してみたものの pop_back() の replace のあたりの実装が気持ち悪いです。 pop_back() あたりは、一つ前のノードの next ポインタを書き換える都合上、複数の変数からの参照先を記憶しておく必要があります。

Rc<RefCell> 版では強参照、弱参照を使い分けることで実装するのですが、Box版は unwrap()がオブジェクトを消費する動作も絡んで所有権を一時的に得るためのreplaceで回避しています。(他の言語と比べて可読性が良い訳でもなく、論理的な納得性もないのでBox版はないわーと感じます。)

参考

• What would be a better way to implement .pop() in my single linked list in Rust? - Stack Overflow
  pop_back() はここのコードを大いに参考にしています
• Singly-Linked List in Rust - Stack Overflow
  気持ち悪いですが再帰で実装する方法もあるんですね
• Singly Linked List in Rust - gists · GitHub
  イテレータ周りは大いに参考にしています。このmapを使った実装は読みにくいですね。理解できてきましたが、Rustを使うデメリットが強くでている部分かと思います。参照外しの中の人など知りたくなかった。