LoginSignup
5
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@syuuu

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

Last updated at Posted at 2022-01-03

概要

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

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

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() を使うブロックをうまく分けるのがポイント
5
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?