rust

Unexpected default drop behavior in doubly-linked list

I'm working on some course material, where I'll demo the Box, Rc, and RefCell types by gradually developing a singly-linked stack and a doubly linked deque. The default Drop implementation for the Stack (understandably) is recursive and hence blows the stack on large enough lists. (I then develop a custom Drop impl that is not recursive.) However, the default Drop implementation for the doubly linked deque works just fine (if, perhaps inefficiently?) and I would like to understand why.

The structs are as follows.

Singly-linked stack:

struct Stack<E> {
    head: Option<Box<StackNode<E>>>,
    size: usize,
}

struct StackNode<E> {
    elem: E,
    next: Option<Box<StackNode<E>>>,
}

Doubly-linked deque:

struct Deque<E> {
    head: Option<Rc<RefCell<DequeNode<E>>>>,
    tail: Option<Rc<RefCell<DequeNode<E>>>>,
    size: usize,
}

struct DequeNode<E> {
    next: Option<Rc<RefCell<DequeNode<E>>>>,
    prev: Option<Rc<RefCell<DequeNode<E>>>>,
    elem: E,
}

(I'm "eliding" the implementations, assuming they're not relevant.)

Solution

  • Your doubly-linked list implementation uses strong references Rc in both the forward and backward direction. That means that each node in the list is keeping its peers alive, which in turn keep it alive. Without a custom Drop implementation, more than one node will just leak. A default Drop would drop head and tail, but that would not destroy the first node because the second node would still have a strong reference.

    If you want an implementation that recurses and potentially blows the stack on Drop, you could make the back references Weak instead.