Deque as Linked List: Get Values

[patrickbucher]

I'd like to implement a Deque using the interior mutability pattern. For this purpose, I have the following Node and Deque structs:

pub struct Node<T: Clone> {
    value: T,
    next: Option<Rc<RefCell<Node<T>>>>,
    prev: Option<Rc<RefCell<Node<T>>>>,
}

pub struct Deque<T: Clone> {
    head: Option<Rc<RefCell<Node<T>>>>,
    tail: Option<Rc<RefCell<Node<T>>>>,
}

Among others, I'd like to offer a method called get_values that returns a vector of the copied values:

impl<T> Deque<T>
where
    T: Clone,
{
    pub fn get_values(&self) -> Vec<T> {
        let mut values = Vec::new();
        let mut temp = &self.head;
        while let Some(node) = temp {
            values.push(node.borrow().value.clone());
            temp = &node.borrow().next.clone();
        }
        values
    }
}

Unfortunately, the borrowed values doesn't live long enough:

error[E0716]: temporary value dropped while borrowed
  --> src/deque.rs:85:21
   |
83 |         while let Some(node) = temp {
   |                                ---- borrow later used here
84 |             values.push(node.borrow().value.clone());
85 |             temp = &node.borrow().next.clone();
   |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^- temporary value is freed at the end of this statement
   |                     |
   |                     creates a temporary value which is freed while still in use
   |
   = note: consider using a `let` binding to create a longer lived value

So I create a let binding:

 80     pub fn get_values(&self) -> Vec<T> {
 81         let mut values = Vec::new();
 82         let mut temp = &self.head;
 83         while let Some(node) = temp {
 84             values.push(node.borrow().value.clone());
 85             let next = &node.borrow().next.clone();
 86             temp = next;
 87         }
 88         values
 89     }

Which doesn't live long enough:

error[E0716]: temporary value dropped while borrowed
  --> src/deque.rs:85:25
   |
83 |         while let Some(node) = temp {
   |                                ---- borrow later used here
84 |             values.push(node.borrow().value.clone());
85 |             let next = &node.borrow().next.clone();
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^ creates a temporary value which is freed while still in use
86 |             temp = next;
87 |         }
   |         - temporary value is freed at the end of this statement

So let's move the binding further up in the scope:

 80     pub fn get_values(&self) -> Vec<T> {
 81         let mut values = Vec::new();
 82         let mut temp = &self.head;
 83         let mut next;
 84         while let Some(node) = temp {
 85             values.push(node.borrow().value.clone());
 86             next = &node.borrow().next.clone();
 87             temp = next;
 88         }
 89         values
 90     }

Which gives me another error:

error[E0716]: temporary value dropped while borrowed
  --> src/deque.rs:86:21
   |
86 |             next = &node.borrow().next.clone();
   |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^- temporary value is freed at the end of this statement
   |                     |
   |                     creates a temporary value which is freed while still in use
87 |             temp = next;
   |                    ---- borrow later used here
   |
   = note: consider using a `let` binding to create a longer lived value

Here we are again, and I think I tackled the wrong issue.

Any ideas how to prevent this issue?

[jofas]

I'm not sure I understand what you are trying to do with your VecDeque which seems to me to be a deque containing linked lists (?), but this version of Deque::get_values compiles:

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

pub struct Node<T: Clone> {
    value: T,
    next: Option<Rc<RefCell<Node<T>>>>,
    prev: Option<Rc<RefCell<Node<T>>>>,
}

pub struct Deque<T: Clone> {
    head: Option<Rc<RefCell<Node<T>>>>,
    tail: Option<Rc<RefCell<Node<T>>>>,
}

impl<T> Deque<T>
where
    T: Clone,
{
    pub fn get_values(&self) -> Vec<T> {
        let mut values = Vec::new();
        let mut temp = self.head.clone();

        while let Some(node) = temp {
            let node_ref = node.borrow();

            values.push(node_ref.value.clone());
            temp = node_ref.next.clone();
        }

        values
    }
}

Playground.

[patrickbucher]

Thanks; cloning the head did the trick.

The idea is from chapter 14 of A Common-Sense Guide to Data Structures and Algorithms. The examples are in Ruby, but I'd like to implement them in Rust as a transfer exercise.

[jofas]

@patrickbucher

I'd like to implement them in Rust as a transfer exercise.

Nice. Linked lists and trees—which are relatively easy to implement in OOP languages that don't care about aliasing and exclusivity at all—are just a lot harder to implement in Rust, which hopefully isn't too frustrating for you. If you're interested there is the classic Introduction - Learning Rust With Entirely Too Many Linked Lists that contains a deep dive into linked lists in Rust.

[patrickbucher]

The frustration is part of the game; I don't really look forward to all those node-based data structures.

The functional approach (creating new nodes instead of modifying existing ones) is often easier, but not always feasible. (It works well for prepend by just adding a new node in front of it, thereby consuming the current head.)

Thanks for the link; this could be my next project after finishing said book.

PS: And this community is absolutely nice. I always have second thoughts before opening a new thread, but here I'm always getting help and learn something in the process.