Reversing a Doubly Linked List in Rust

Question

I have the following implementation for a Doubly Linked List ->


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

impl<T> Node<T> {
    fn new(value: T) -> Self {
        Node {
            value,
            next: None,
            prev: None,
        }
    }
}

impl<T> From<Node<T>> for Option<Rc<RefCell<Node<T>>>> {
    fn from(node: Node<T>) -> Self { Some(Rc::new(RefCell::new(node))) }
}

type NodePtr<T> = Rc<RefCell<Node<T>>>;

pub struct DoublyLinkedList<T> {
    head: Option<NodePtr<T>>,
    tail: Option<NodePtr<T>>,
}

However, I have difficulty implementing an algorithm to reverse the linked list.

I tried

    pub fn reverse(&mut self) {
        let mut current_node = self.head.clone();
        while let Some(current) = current_node {
            let mut current_borrowed = current.borrow_mut();
            std::mem::swap(&mut current_borrowed.next, &mut current_borrowed.prev);
            current_node = current_borrowed.prev.upgrade();
        }
        std::mem::swap(&mut self.head, &mut self.tail);
    }

But this doesn't work because current_borrowed.prev is Option<Weak<RefCell<Node<T>>>>, and I cannot upgrade it or downgrade current_borrowed.next.

You could also repeatedly pop from the tail of this list and append to the tail of a new list, then swap the two lists. — prog-fh
– prog-fh, Commented May 18, 2024 at 10:49
@prog-fh Yes, I thought of that, but I wanted to do it this way. Your way uses O(n) extra space, I know of a way to do it in O(1) in C++, but couldn't code it up in Rust. — KillerFC
– KillerFC, Commented May 18, 2024 at 11:07
It doesn't use O(n) extra space though, as you remove one element you have n-1 elements in the first list and 1 element in the other then (n-2, 2), … if you add that up at each step you use exactly O(n) — cafce25
– cafce25, Commented May 18, 2024 at 16:26

prog-fh · Accepted Answer · 2024-05-18 13:00:11Z

You cannot directly swap the next and prev members because they do not have the same type.
However, we can swap step by step, taking the content of these options (leaving None), and performing the upgrade/downgrade as needed before reassigning.
There is however a subtlety: because we swap the strong/weak references, the current node will be dropped when iterating to the next one!
Thus, we must keep a strong reference to the previously swapped node in order to keep it alive till the next iteration.

    pub fn reverse(&mut self) {
        let mut current_node = self.head.clone();
        let mut _keep_prev_node = None;
        while let Some(current) = current_node {
            let mut current_borrowed = current.borrow_mut();
            let next = current_borrowed.next.take();
            let prev = current_borrowed.prev.take();
            if let Some(prev) = &prev {
                current_borrowed.next = prev.upgrade();
            }
            if let Some(next) = &next {
                current_borrowed.prev = Some(Rc::downgrade(next));
            }
            current_node = next;
            _keep_prev_node = Some(current.clone());
        }
        std::mem::swap(&mut self.head, &mut self.tail);
    }

You could also repeatedly pop from the tail of this list and append to the tail of a new list, then swap the two lists.

Collectives™ on Stack Overflow

Reversing a Doubly Linked List in Rust

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related