1035 Advanced

1035-doubly-linked — Doubly-Linked List

Functional Programming

Tutorial

The Problem

Doubly-linked lists support O(1) insertion and removal at any node when you already hold a reference to that node. This makes them ideal for LRU cache eviction (move a node to the front when accessed), editor cursor movement, and undo/redo history. The challenge in Rust is that each node needs a pointer to both its predecessor and successor, creating a cycle of shared ownership that cannot be expressed with simple Box<T>.

The standard safe solution uses Rc<RefCell<Node<T>>> — reference counting for shared ownership and interior mutability for the back-pointer updates.

🎯 Learning Outcomes

• Use Rc<RefCell<Node<T>>> as the node link type for shared mutable ownership

• Understand why doubly-linked lists require shared ownership (both neighbors own the node)

• Implement push_back, push_front, pop_back, pop_front, and iteration

• Understand the memory overhead of Rc<RefCell<_>> versus raw pointers

• Know when to use Arc<Mutex<_>> instead for thread-safe variants

Code Example

#![allow(clippy::all)]
// 1035: Doubly-Linked List — Rc<RefCell<Node>> Approach
// Safe doubly-linked list using reference counting + interior mutability

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

type Link<T> = Option<Rc<RefCell<DNode<T>>>>;

struct DNode<T> {
    value: T,
    prev: Link<T>,
    next: Link<T>,
}

struct DoublyLinkedList<T> {
    head: Link<T>,
    tail: Link<T>,
    len: usize,
}

impl<T> DoublyLinkedList<T> {
    fn new() -> Self {
        DoublyLinkedList {
            head: None,
            tail: None,
            len: 0,
        }
    }

    fn push_back(&mut self, value: T) {
        let new_node = Rc::new(RefCell::new(DNode {
            value,
            prev: self.tail.clone(),
            next: None,
        }));

        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_node.clone());
            }
            None => {
                self.head = Some(new_node.clone());
            }
        }
        self.tail = Some(new_node);
        self.len += 1;
    }

    fn push_front(&mut self, value: T) {
        let new_node = Rc::new(RefCell::new(DNode {
            value,
            prev: None,
            next: self.head.clone(),
        }));

        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(new_node.clone());
            }
            None => {
                self.tail = Some(new_node.clone());
            }
        }
        self.head = Some(new_node);
        self.len += 1;
    }

    fn pop_front(&mut self) -> Option<T>
    where
        T: Default,
    {
        self.head.take().map(|old_head| {
            let mut old_head_ref = old_head.borrow_mut();
            match old_head_ref.next.take() {
                Some(new_head) => {
                    new_head.borrow_mut().prev = None;
                    self.head = Some(new_head);
                }
                None => {
                    self.tail = None;
                }
            }
            self.len -= 1;
            std::mem::take(&mut old_head_ref.value)
        })
    }

    fn pop_back(&mut self) -> Option<T>
    where
        T: Default,
    {
        self.tail.take().map(|old_tail| {
            let mut old_tail_ref = old_tail.borrow_mut();
            match old_tail_ref.prev.take() {
                Some(new_tail) => {
                    new_tail.borrow_mut().next = None;
                    self.tail = Some(new_tail);
                }
                None => {
                    self.head = None;
                }
            }
            self.len -= 1;
            std::mem::take(&mut old_tail_ref.value)
        })
    }

    fn to_vec(&self) -> Vec<T>
    where
        T: Clone,
    {
        let mut result = Vec::new();
        let mut current = self.head.clone();
        while let Some(node) = current {
            result.push(node.borrow().value.clone());
            current = node.borrow().next.clone();
        }
        result
    }

    fn len(&self) -> usize {
        self.len
    }
}

impl<T: fmt::Debug + Clone> fmt::Debug for DoublyLinkedList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{:?}", self.to_vec())
    }
}

fn basic_operations() {
    let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    list.push_front(0);

    assert_eq!(list.to_vec(), vec![0, 1, 2, 3]);
    assert_eq!(list.len(), 4);

    assert_eq!(list.pop_front(), Some(0));
    assert_eq!(list.pop_back(), Some(3));
    assert_eq!(list.to_vec(), vec![1, 2]);
}

fn bidirectional_traversal() {
    let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
    for i in 1..=5 {
        list.push_back(i);
    }

    // Forward traversal
    let forward = list.to_vec();
    assert_eq!(forward, vec![1, 2, 3, 4, 5]);

    // Backward traversal
    let mut backward = Vec::new();
    let mut current = list.tail.clone();
    while let Some(node) = current {
        backward.push(node.borrow().value);
        current = node.borrow().prev.clone();
    }
    assert_eq!(backward, vec![5, 4, 3, 2, 1]);
}

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

    #[test]
    fn test_basic() {
        basic_operations();
    }

    #[test]
    fn test_bidirectional() {
        bidirectional_traversal();
    }

    #[test]
    fn test_empty() {
        let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.pop_back(), None);
        assert_eq!(list.len(), 0);
    }

    #[test]
    fn test_single() {
        let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
        list.push_back(42);
        assert_eq!(list.pop_front(), Some(42));
        assert!(list.head.is_none());
        assert!(list.tail.is_none());
    }
}

(* 1035: Doubly-Linked List *)
(* OCaml: immutable doubly-linked lists are impractical *)
(* We use a zipper (functional approach) or mutable records *)

(* Approach 1: Zipper as functional doubly-linked list *)
type 'a zipper = {
  left: 'a list;   (* reversed left part *)
  focus: 'a;
  right: 'a list;
}

let of_list = function
  | [] -> None
  | x :: xs -> Some { left = []; focus = x; right = xs }

let move_right z =
  match z.right with
  | [] -> None
  | x :: xs -> Some { left = z.focus :: z.left; focus = x; right = xs }

let move_left z =
  match z.left with
  | [] -> None
  | x :: xs -> Some { left = xs; focus = x; right = z.focus :: z.right }

let to_list z =
  List.rev z.left @ [z.focus] @ z.right

let zipper_test () =
  let z = Option.get (of_list [1; 2; 3; 4; 5]) in
  assert (z.focus = 1);
  let z = Option.get (move_right z) in
  assert (z.focus = 2);
  let z = Option.get (move_right z) in
  assert (z.focus = 3);
  let z = Option.get (move_left z) in
  assert (z.focus = 2);
  assert (to_list z = [1; 2; 3; 4; 5])

(* Approach 2: Mutable doubly-linked using records *)
type 'a dnode = {
  mutable value: 'a;
  mutable prev: 'a dnode option;
  mutable next: 'a dnode option;
}

type 'a dlist = {
  mutable head: 'a dnode option;
  mutable tail: 'a dnode option;
  mutable length: int;
}

let create () = { head = None; tail = None; length = 0 }

let push_back dl v =
  let node = { value = v; prev = dl.tail; next = None } in
  (match dl.tail with
   | Some t -> t.next <- Some node
   | None -> dl.head <- Some node);
  dl.tail <- Some node;
  dl.length <- dl.length + 1

let push_front dl v =
  let node = { value = v; prev = None; next = dl.head } in
  (match dl.head with
   | Some h -> h.prev <- Some node
   | None -> dl.tail <- Some node);
  dl.head <- Some node;
  dl.length <- dl.length + 1

let to_list_forward dl =
  let rec go acc = function
    | None -> List.rev acc
    | Some n -> go (n.value :: acc) n.next
  in
  go [] dl.head

let mutable_dlist_test () =
  let dl = create () in
  push_back dl 1;
  push_back dl 2;
  push_back dl 3;
  push_front dl 0;
  assert (to_list_forward dl = [0; 1; 2; 3]);
  assert (dl.length = 4)

let () =
  zipper_test ();
  mutable_dlist_test ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Cycle handling: OCaml's GC handles reference cycles automatically; Rust's Rc cycles leak unless Weak<T> is used for back-pointers.

Interior mutability: Rust needs RefCell to mutate nodes through shared Rc references; OCaml uses mutable record fields directly.

Thread safety: Rust can upgrade to Arc<Mutex<_>> for thread-safe doubly-linked lists; OCaml uses Mutex explicitly.

Overhead: Rust's Rc<RefCell<_>> adds two heap allocations and reference counting per node; OCaml has one heap allocation per node.

OCaml Approach

OCaml's mutable doubly-linked list uses ref for the pointers:

type 'a node = {
  mutable value: 'a;
  mutable prev: 'a node option;
  mutable next: 'a node option;
}

OCaml's GC handles cycles — a doubly-linked list forms a reference cycle but the GC's cycle collector reclaims it. Rust's Rc<RefCell<_>> creates reference cycles that cause memory leaks unless you use Weak<T> for back-pointers.

Full Source

#![allow(clippy::all)]
// 1035: Doubly-Linked List — Rc<RefCell<Node>> Approach
// Safe doubly-linked list using reference counting + interior mutability

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

type Link<T> = Option<Rc<RefCell<DNode<T>>>>;

struct DNode<T> {
    value: T,
    prev: Link<T>,
    next: Link<T>,
}

struct DoublyLinkedList<T> {
    head: Link<T>,
    tail: Link<T>,
    len: usize,
}

impl<T> DoublyLinkedList<T> {
    fn new() -> Self {
        DoublyLinkedList {
            head: None,
            tail: None,
            len: 0,
        }
    }

    fn push_back(&mut self, value: T) {
        let new_node = Rc::new(RefCell::new(DNode {
            value,
            prev: self.tail.clone(),
            next: None,
        }));

        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_node.clone());
            }
            None => {
                self.head = Some(new_node.clone());
            }
        }
        self.tail = Some(new_node);
        self.len += 1;
    }

    fn push_front(&mut self, value: T) {
        let new_node = Rc::new(RefCell::new(DNode {
            value,
            prev: None,
            next: self.head.clone(),
        }));

        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(new_node.clone());
            }
            None => {
                self.tail = Some(new_node.clone());
            }
        }
        self.head = Some(new_node);
        self.len += 1;
    }

    fn pop_front(&mut self) -> Option<T>
    where
        T: Default,
    {
        self.head.take().map(|old_head| {
            let mut old_head_ref = old_head.borrow_mut();
            match old_head_ref.next.take() {
                Some(new_head) => {
                    new_head.borrow_mut().prev = None;
                    self.head = Some(new_head);
                }
                None => {
                    self.tail = None;
                }
            }
            self.len -= 1;
            std::mem::take(&mut old_head_ref.value)
        })
    }

    fn pop_back(&mut self) -> Option<T>
    where
        T: Default,
    {
        self.tail.take().map(|old_tail| {
            let mut old_tail_ref = old_tail.borrow_mut();
            match old_tail_ref.prev.take() {
                Some(new_tail) => {
                    new_tail.borrow_mut().next = None;
                    self.tail = Some(new_tail);
                }
                None => {
                    self.head = None;
                }
            }
            self.len -= 1;
            std::mem::take(&mut old_tail_ref.value)
        })
    }

    fn to_vec(&self) -> Vec<T>
    where
        T: Clone,
    {
        let mut result = Vec::new();
        let mut current = self.head.clone();
        while let Some(node) = current {
            result.push(node.borrow().value.clone());
            current = node.borrow().next.clone();
        }
        result
    }

    fn len(&self) -> usize {
        self.len
    }
}

impl<T: fmt::Debug + Clone> fmt::Debug for DoublyLinkedList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{:?}", self.to_vec())
    }
}

fn basic_operations() {
    let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    list.push_front(0);

    assert_eq!(list.to_vec(), vec![0, 1, 2, 3]);
    assert_eq!(list.len(), 4);

    assert_eq!(list.pop_front(), Some(0));
    assert_eq!(list.pop_back(), Some(3));
    assert_eq!(list.to_vec(), vec![1, 2]);
}

fn bidirectional_traversal() {
    let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
    for i in 1..=5 {
        list.push_back(i);
    }

    // Forward traversal
    let forward = list.to_vec();
    assert_eq!(forward, vec![1, 2, 3, 4, 5]);

    // Backward traversal
    let mut backward = Vec::new();
    let mut current = list.tail.clone();
    while let Some(node) = current {
        backward.push(node.borrow().value);
        current = node.borrow().prev.clone();
    }
    assert_eq!(backward, vec![5, 4, 3, 2, 1]);
}

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

    #[test]
    fn test_basic() {
        basic_operations();
    }

    #[test]
    fn test_bidirectional() {
        bidirectional_traversal();
    }

    #[test]
    fn test_empty() {
        let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.pop_back(), None);
        assert_eq!(list.len(), 0);
    }

    #[test]
    fn test_single() {
        let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
        list.push_back(42);
        assert_eq!(list.pop_front(), Some(42));
        assert!(list.head.is_none());
        assert!(list.tail.is_none());
    }
}

(* 1035: Doubly-Linked List *)
(* OCaml: immutable doubly-linked lists are impractical *)
(* We use a zipper (functional approach) or mutable records *)

(* Approach 1: Zipper as functional doubly-linked list *)
type 'a zipper = {
  left: 'a list;   (* reversed left part *)
  focus: 'a;
  right: 'a list;
}

let of_list = function
  | [] -> None
  | x :: xs -> Some { left = []; focus = x; right = xs }

let move_right z =
  match z.right with
  | [] -> None
  | x :: xs -> Some { left = z.focus :: z.left; focus = x; right = xs }

let move_left z =
  match z.left with
  | [] -> None
  | x :: xs -> Some { left = xs; focus = x; right = z.focus :: z.right }

let to_list z =
  List.rev z.left @ [z.focus] @ z.right

let zipper_test () =
  let z = Option.get (of_list [1; 2; 3; 4; 5]) in
  assert (z.focus = 1);
  let z = Option.get (move_right z) in
  assert (z.focus = 2);
  let z = Option.get (move_right z) in
  assert (z.focus = 3);
  let z = Option.get (move_left z) in
  assert (z.focus = 2);
  assert (to_list z = [1; 2; 3; 4; 5])

(* Approach 2: Mutable doubly-linked using records *)
type 'a dnode = {
  mutable value: 'a;
  mutable prev: 'a dnode option;
  mutable next: 'a dnode option;
}

type 'a dlist = {
  mutable head: 'a dnode option;
  mutable tail: 'a dnode option;
  mutable length: int;
}

let create () = { head = None; tail = None; length = 0 }

let push_back dl v =
  let node = { value = v; prev = dl.tail; next = None } in
  (match dl.tail with
   | Some t -> t.next <- Some node
   | None -> dl.head <- Some node);
  dl.tail <- Some node;
  dl.length <- dl.length + 1

let push_front dl v =
  let node = { value = v; prev = None; next = dl.head } in
  (match dl.head with
   | Some h -> h.prev <- Some node
   | None -> dl.tail <- Some node);
  dl.head <- Some node;
  dl.length <- dl.length + 1

let to_list_forward dl =
  let rec go acc = function
    | None -> List.rev acc
    | Some n -> go (n.value :: acc) n.next
  in
  go [] dl.head

let mutable_dlist_test () =
  let dl = create () in
  push_back dl 1;
  push_back dl 2;
  push_back dl 3;
  push_front dl 0;
  assert (to_list_forward dl = [0; 1; 2; 3]);
  assert (dl.length = 4)

let () =
  zipper_test ();
  mutable_dlist_test ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_basic() {
        basic_operations();
    }

    #[test]
    fn test_bidirectional() {
        bidirectional_traversal();
    }

    #[test]
    fn test_empty() {
        let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.pop_back(), None);
        assert_eq!(list.len(), 0);
    }

    #[test]
    fn test_single() {
        let mut list: DoublyLinkedList<i32> = DoublyLinkedList::new();
        list.push_back(42);
        assert_eq!(list.pop_front(), Some(42));
        assert!(list.head.is_none());
        assert!(list.tail.is_none());
    }
}

Deep Comparison

Doubly-Linked List — Comparison

Core Insight

Doubly-linked lists require bidirectional pointers — each node is shared by its neighbors. In Rust, this violates single-ownership rules, requiring Rc (shared ownership) + RefCell (interior mutability). OCaml either uses mutable records (imperative) or zippers (functional alternative).

OCaml Approach

• Mutable records: mutable prev/next fields with option types

• GC handles cycles — no reference counting needed

• Zipper alternative: { left; focus; right } for functional bidirectional access

• Standard library has no doubly-linked list

Rust Approach

• Rc<RefCell<Node<T>>> — reference-counted cells with runtime borrow checking

• clone() on Rc creates shared references

• borrow() / borrow_mut() for access (panics if rules violated at runtime)

• Must be careful to break cycles to avoid memory leaks

• std::collections::LinkedList exists but is rarely recommended

Comparison Table

Feature	OCaml (mutable)	Rust (`Rc<RefCell>`)
Shared ownership	GC handles it	`Rc` reference counting
Interior mutability	`mutable` keyword	`RefCell` runtime checks
Cycle handling	GC collects cycles	Must break manually
Borrow checking	None (runtime safe)	Runtime via RefCell
Ergonomics	Simple mutation	Verbose `.borrow_mut()`
Recommendation	Fine for imperative	Use `Vec`/`VecDeque` instead

Exercises

Add Weak<RefCell<DNode<T>>> back-pointers instead of Rc for the prev link to prevent memory leaks in cyclic structures.

Implement an LRU cache using the doubly-linked list with a HashMap<K, Rc<RefCell<DNode<(K, V)>>>> for O(1) node lookup.

Write an iterator that traverses the list in reverse order using the prev pointers.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust