概要

腕試しに単方向リストを実装してみた。結果的に Rc, RefCell の知識があやふやだと正解にたどり着けない。

知識があやふやな人は、次の記事も参照してください。

スライスの実装を通してRustのRc, RefCellの理解度が分かるコード例 (Go, Julia との比較)

Box版/unsafe版の記事はこちら

環境

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

問題設定

単方向リスト ... tail(末尾へのポインタ)をメンバーに持たない次のような構造体
tailを含まないことで、内部でリストをたどる点で理解度が試される。

pub struct ListNode<T: Debug> {
    value: T,
    next: Option<Rc<RefCell<ListNode<T>>>>,
}

pub struct SinglyLinkedList<T: Debug> {
    head: Option<Rc<RefCell<ListNode<T>>>>,
}

push_back()のみ実装 (後ろに要素を追加する)

impl<T: Debug> SinglyLinkedList<T> {
    pub fn push_back(&mut self, v: T) {
        //...
    }
}

pop_back()は今回は実装(紹介)しない (興味がある人は試してみてください)
以下のメソッドで Copyトレイト(<T: Copy>)を要求しないこと。まずは <T: Debug + Clone> でやるほうが難易度は低い。
```
impl<T: Debug> SinglyLinkedList<T> {
   pub fn pop_back(&mut self) -> Option<T> {
       //...
   }
}
```

テスト

次の結果で 1, 2, 3 がリストに追加されること。

use list::SinglyLinkedList;

fn main() {
    let mut list = SinglyLinkedList::new();
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    println!("{}", list);
}

実装例

試行錯誤の段階も面白いのですが、実装例を示します。

Cargo.toml

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

[lib]
name = "list"  
path = "src/lib.rs"

[dependencies]

src/main.rs

use list::SinglyLinkedList;

fn main() {
    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!(list.pop_back(), Some(2));
    assert_eq!(iter.next(), None);
    assert_eq!(list.iter().collect::<Vec<_>>(), vec![1]);

    list.push_back(2);
    list.push_back(3);
    println!("{}", list);
    assert_eq!(list.iter().collect::<Vec<_>>(), vec![1, 2, 3]);
    for v in list.iter() {
        println!("{:?}", v);
    }
    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);
    list.push_back(2);
    assert_eq!(list.pop_front(), Some(1));
    assert_eq!(list.iter().collect::<Vec<_>>(), vec![2]);
}

src/lib.rs

全般
- 所有権が移動(Move)されては困るので Rc::clone() で所有権を複製します
- borrow / borrow_mut を同じスコープで使わないようにします
pop_back()/pop_front()
- 要素を取り出すときに、borrow()だと一時的にしか有効でないから、clone()するなり、セルを解体してvalueだけ所有権を渡してやる必要があります
- この例では try_unwrap を使っており、try_unwrap は strong な参照が1つの場合に限りにセルを消費し中身を取り出すことができます

例1) cloneで値を取り出す場合

let result: T;
result = Rc::clone(&cur).borrow().value.clone();
if let Some(prev) = some_prev {
    prev.borrow_mut().next = None;
} else {
    self.head = None;
}
Some(result)

例2) try_unwrapでセルを解体して値を渡す場合

last が ListNode でその一部の value のみ所有権を渡している。しかし、部分的に所有権を渡すとListNodeの自作Dropトレイトが実装できなくなる。

        if let Some(prev) = some_prev {
            prev.borrow_mut().next = None;
        } else {
            self.head = None;
        }

        let last: ListNode<T> = Rc::try_unwrap(cur).ok().unwrap().into_inner();
        Some(last.value)

use std::default::Default;
use std::fmt;
use std::rc::Rc;
use std::rc::Weak;
use std::cell::RefCell;


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

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

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.borrow())
            },
            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.borrow())
            }
            None => write!(f, "SinglyLinkedList[]")
        }
    }
}

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

pub struct SinglyLinkedListIterator<T> {
    cur: Option<Weak<RefCell<ListNode<T>>>>
}

impl<T> SinglyLinkedList<T> {
    /// # Examples
    ///
    /// ```
    /// use list::v6::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 node_new = ListNode::new(v);
        let mut cur: Rc<RefCell<ListNode<T>>>;
        if let Some(ref head) = self.head {
            cur = Rc::clone(head);
        } else {
            self.head = Some(Rc::new(RefCell::new(node_new)));
            return;
        };

        while let Some(ref next) = Rc::clone(&cur).borrow().next {
            cur = Rc::clone(next);
        }

        cur.borrow_mut().next = Some(
            Rc::new(RefCell::new(node_new))
        );
    }

    /// # Examples
    ///
    /// ```
    /// use list::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> {
        let mut some_prev: Option<Rc<RefCell<ListNode<T>>>> = None;
        let mut cur: Rc<RefCell<ListNode<T>>>;
        if let Some(ref head) = self.head {
            cur = Rc::clone(head);
        } else {
            // You can't pop the head of the list.
            return None;
        };

        while let Some(ref next) = Rc::clone(&cur).borrow().next {
            some_prev = Some(Rc::clone(&cur));
            cur = Rc::clone(next);
        }

        if let Some(prev) = some_prev {
            prev.borrow_mut().next = None;
        } else {
            self.head = None;
        }

        let last: ListNode<T> = Rc::try_unwrap(cur).ok().unwrap().into_inner();
        Some(last.value)
    }

    /// # Examples
    ///
    /// ```
    /// use list::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> {
        let head = match self.head {
            Some(ref head) => Rc::clone(head),
            None => return None,
        };
        assert_eq!(Rc::strong_count(&head), 2);
        self.head = None;
        assert_eq!(Rc::strong_count(&head), 1);
        let node: ListNode<T> = Rc::try_unwrap(head).ok().unwrap().into_inner();
        self.head = node.next;
        Some(node.value)
    }

    /// # Examples
    ///
    /// ```
    /// use list::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> {
        if let Some(ref head) = self.head {
            SinglyLinkedListIterator {
                cur: Some(Rc::downgrade(&Rc::clone(head)))
            }    
        } else {
            SinglyLinkedListIterator { cur: None }
        }
    }
}

impl<T:Clone> Iterator for SinglyLinkedListIterator<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        let cur_weak = match self.cur {
            Some(ref cur_weak) => cur_weak,
            None => return None,
        };

        let cur_strong = match cur_weak.upgrade() {
            Some(cur_strong) => cur_strong,
            None => return None,
        };

        let cur_val = cur_strong.borrow().value.clone();
        if let Some(ref next) = cur_strong.borrow().next {
            self.cur = Some(Rc::downgrade(next))
        } else {
            self.cur = None;
        }
        Some(cur_val)
    }
}

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

    #[test]
    fn test_push_pop_1() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        list.push_back(1);
        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_push_pop_2() {
        let mut list: SinglyLinkedList<&str> = Default::default();
        list.push_back("hello");
        list.push_back("world");
        assert_eq!(list.pop_back(), Some("world"));
        assert_eq!(list.pop_back(), Some("hello"));
        assert_eq!(list.pop_back(), None);
        list.push_back("hello");
        list.push_back("world");
        assert_eq!(list.pop_back(), Some("world"));
        assert_eq!(list.pop_back(), Some("hello"));
        assert_eq!(list.pop_back(), None);
    }

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

        list.push_back(1);
        assert_eq!(list.pop_front(), Some(1));
        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_front_2() {
        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);
    }

    #[test]
    fn test_iter_unwrap_failed() {
        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!(list.pop_back(), Some(2));
        assert_eq!(iter.next(), None);

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

    #[test]
    fn test_iter_last_add() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        list.push_back(1);
        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(1));
        list.push_back(2);
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_and_pop_front_1() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        list.push_back(1);
        list.push_back(2);
        let mut iter = list.iter();             // The next pointer points to 1.
        assert_eq!(list.pop_front(), Some(1));  // node 1 is dropped.
        assert_eq!(iter.next(), None);          // The next pointer is None.
    }

    #[test]
    fn test_iter_and_pop_front1() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        list.push_back(1);
        list.push_back(2);
        let mut iter = list.iter();            // The next pointer points to 1.
        assert_eq!(iter.next(), Some(1));      // The next pointer points to 2.
        assert_eq!(list.pop_front(), Some(1)); // node 1 is dropped.
        assert_eq!(iter.next(), Some(2));      // The next pointer points to None.
        assert_eq!(iter.next(), None);
    }
}

参考: 試行錯誤

0. match句で実行時エラー

use std::fmt;
use std::fmt::Debug;
use std::rc::Rc;
use std::cell::RefCell;

pub struct ListNode<T: Debug> {
    value: T,
    next: Option<Rc<RefCell<ListNode<T>>>>,
}

pub struct SinglyLinkedList<T: Debug> {
    head: Option<Rc<RefCell<ListNode<T>>>>,
}

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

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

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

impl<T: Debug> SinglyLinkedList<T> {
    pub fn new() -> SinglyLinkedList<T> {
        SinglyLinkedList {
            head: None,
        }
    }

    pub fn push_back(&mut self, v: T) {
        let node_new = ListNode::new(v);

        let mut cur: Option<Rc<RefCell<ListNode<T>>>>;
        if let Some(ref head) = self.head {
            cur = Some(Rc::clone(head));
        } else {
            self.head = Some(Rc::new(RefCell::new(node_new)));
            return;
        };

        loop {
            let cur_cloned = match cur {
                None => break,
                Some(ref n) => Rc::clone(n)
            };
            cur = match cur_cloned.borrow().next {
                Some(ref next) => Some(Rc::clone(next)),
                None => {
                    cur_cloned.borrow_mut().next = Some(Rc::new(RefCell::new(node_new)));  // ここでエラー
                    return;
                }
            };
        }
    }
}

$ cargo run
   Compiling singly-linked-list v0.1.0 (.../singly-linked-list)
    Finished dev [unoptimized + debuginfo] target(s) in 2.23s
     Running `/home/guest/tmp_rust/rust-examples/projects/collections/target/debug/singly-linked-list`
thread 'main' panicked at 'already borrowed: BorrowMutError', .../singly-linked-list/src/lib.rs:68:32
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

1. unsafe で無理やり

match で新しい要素を追加できず、unsafe を使って実装。

use std::fmt;
use std::fmt::Debug;
use std::rc::Rc;
use std::cell::RefCell;

pub struct ListNode<T: Debug> {
    value: T,
    next: Option<Rc<RefCell<ListNode<T>>>>,
}

pub struct SinglyLinkedList<T: Debug> {
    head: Option<Rc<RefCell<ListNode<T>>>>,
}

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

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

impl<T: Debug> SinglyLinkedList<T> {
    pub fn new() -> SinglyLinkedList<T> {
        SinglyLinkedList {
            head: None,
        }
    }

    pub fn push_back(&mut self, v: T) {
        let node_new = ListNode::new(v);

        let mut cur: Option<Rc<RefCell<ListNode<T>>>>;
        if let Some(ref head) = self.head {
            cur = Some(Rc::clone(head));
        } else {
            self.head = Some(Rc::new(RefCell::new(node_new)));
            return;
        };

        loop {
            let cur_cloned = match cur {
                None => break,
                Some(ref n) => Rc::clone(n)
            };
            cur = match cur_cloned.borrow().next {
                Some(ref next) => Some(Rc::clone(next)),
                None => {
                    unsafe {
                        (*cur_cloned.as_ptr()).next = Some(
                            Rc::new(
                                RefCell::new(node_new)
                            )
                        );
                    }
                    return;
                }
            };
        }
    }
}

2. unsafe を使わない方法に置き換え

match を使わない方法に変えた
- match と if let において借用をしていると else 含めてブロック中で Mutable な参照を行えない

use std::fmt;
use std::fmt::Debug;
use std::rc::Rc;
use std::cell::RefCell;

pub struct ListNode<T: Debug> {
    value: T,
    next: Option<Rc<RefCell<ListNode<T>>>>,
}

pub struct SinglyLinkedList<T: Debug> {
    head: Option<Rc<RefCell<ListNode<T>>>>,
}

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

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

impl<T: Debug> SinglyLinkedList<T> {
    pub fn new() -> SinglyLinkedList<T> {
        SinglyLinkedList {
            head: None,
        }
    }

    pub fn push_back(&mut self, v: T) {
        let node_new = ListNode::new(v);
        let mut cur: Rc<RefCell<ListNode<T>>>;
        if let Some(ref head) = self.head {
            cur = Rc::clone(head);  //<1>
        } else {
            self.head = Some(Rc::new(RefCell::new(node_new)));
            return;
        };

        loop {
            if let Some(ref next) = Rc::clone(&cur).borrow().next {  //<1>
                cur = Rc::clone(next);  //<1>
                continue;
            } // <2>

            cur.borrow_mut().next = Some(
                Rc::new(RefCell::new(node_new))
            );
            return;
        }
    }
}

<1> Moveされるのは本意ではないので Rc::clone() する
<2> else に処理を書きたいところだが、 borrow_mut と競合しないように if let句は continue で終わらせた

3. loop を while let に置き換え

今回紹介した例そのもの。

考え方としては、リストの末尾に進める処理は借用 borrow でループする
移動し終えたら borrow_mut で更新をする

use std::fmt;
use std::rc::Rc;
use std::cell::RefCell;

pub struct SinglyLinkedList<T> {
    value: T,
    next: Option<Rc<RefCell<SinglyLinkedList<T>>>>,
}

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

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

    pub fn push_back(&mut self, v: T) {
        let node_new = SinglyLinkedList::new(v);
        let mut cur: Rc<RefCell<SinglyLinkedList<T>>>;
        if let Some(ref next) = self.next {
            cur = Rc::clone(next);
        } else {
            self.next = Some(Rc::new(RefCell::new(node_new)));
            return;
        };

        while let Some(ref next) = Rc::clone(&cur).borrow().next {
            cur = Rc::clone(next);
        }

        cur.borrow_mut().next = Some(
            Rc::new(RefCell::new(node_new))
        );
    }
}

まとめ

単方向リストはイテレータ(主にImutable)と追加(Mutable)の組み合わせで書き方によってコンパイルエラーになる
borrow() / borrow_mut() を使うブロックをうまく分けるのがポイント