Doubly Linked List

A doubly linked list is a linear data structure where each node maintains two references: one to the next node and one to the previous node. This allows traversal in both directions, unlike a singly linked list.

Doubly linked lists trade slightly higher memory usage for increased flexibility and simpler deletion logic.

Structure of a Doubly Linked List

Each node contains:

• Data - the stored value
• Prev - reference to the previous node
• Next - reference to the next node

null ← [1] ⇄ [2] ⇄ [3] → null
          ↑
        Head

Traversal can move forward or backward.

Key Characteristics

• Bidirectional traversal
• Easier deletion of arbitrary nodes
• Dynamic size
• Slightly higher memory overhead than singly linked lists

Basic Operations

A doubly linked list typically supports:

1. Insertion

   • At the head
   • At the tail

2. Deletion

   • From the head
   • From the tail
   • By value

3. Traversal

   • Forward
   • Backward

Rust Representation Notes

In Rust, implementing a doubly linked list requires careful ownership handling. For an educational implementation, we use:

• Rc<RefCell<Node<T>>> for shared ownership
• Weak references for backward links to avoid reference cycles

This mirrors how doubly linked structures are safely modeled in Rust.

Rust Implementation

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub prev: Option<Weak<RefCell<Node<T>>>>,
    pub next: Option<Rc<RefCell<Node<T>>>>,
}

#[derive(Debug)]
pub struct DoublyLinkedList<T> {
    head: Option<Rc<RefCell<Node<T>>>>,
    tail: Option<Rc<RefCell<Node<T>>>>,
}

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

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

        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(Rc::downgrade(&new_node));
                self.head = Some(new_node);
                self.tail.get_or_insert(old_head);
            }
            None => {
                self.tail = Some(new_node.clone());
                self.head = Some(new_node);
            }
        }
    }

    pub fn push_back(&mut self, value: T) {
        let new_node = Rc::new(RefCell::new(Node {
            value,
            prev: None,
            next: None,
        }));

        match self.tail.take() {
            Some(old_tail) => {
                new_node.borrow_mut().prev = Some(Rc::downgrade(&old_tail));
                old_tail.borrow_mut().next = Some(new_node.clone());
                self.tail = Some(new_node);
                self.head.get_or_insert(old_tail);
            }
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node);
            }
        }
    }

    pub fn pop_front(&mut self) -> Option<T>
    where
        T: Clone,
    {
        self.head.take().map(|old_head| {
            if let Some(next) = old_head.borrow_mut().next.take() {
                next.borrow_mut().prev = None;
                self.head = Some(next);
            } else {
                self.tail.take();
            }
            old_head.borrow().value.clone()
        })
    }

    pub fn pop_back(&mut self) -> Option<T>
    where
        T: Clone,
    {
        self.tail.take().map(|old_tail| {
            if let Some(prev) = old_tail.borrow().prev.as_ref().and_then(|w| w.upgrade()) {
                prev.borrow_mut().next = None;
                self.tail = Some(prev);
            } else {
                self.head.take();
            }
            old_tail.borrow().value.clone()
        })
    }

    pub fn contains(&self, value: &T) -> bool {
        let mut current = self.head.clone();

        while let Some(node) = current {
            if &node.borrow().value == value {
                return true;
            }
            current = node.borrow().next.clone();
        }

        false
    }

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

        while let Some(node) = current {
            values.push(node.borrow().value.clone());
            current = node.borrow().next.clone();
        }

        values
    }

    pub fn traverse_backward(&self) -> Vec<T>
    where
        T: Clone,
    {
        let mut values = Vec::new();
        let mut current = self.tail.clone();

        while let Some(node) = current {
            values.push(node.borrow().value.clone());
            current = node
                .borrow()
                .prev
                .as_ref()
                .and_then(|w| w.upgrade());
        }

        values
    }
}

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

    #[test]
    fn it_works() {
        let mut list = DoublyLinkedList::new();

        list.push_front(2);
        list.push_front(1);
        list.push_back(3);

        assert_eq!(list.traverse_forward(), vec![1, 2, 3]);
        assert_eq!(list.traverse_backward(), vec![3, 2, 1]);

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

Example Usage

fn main() {
    let mut list = DoublyLinkedList::new();

    list.push_front(2);
    list.push_front(1);
    list.push_back(3);

    println!("Forward: {:?}", list.traverse_forward());   // [1, 2, 3]
    println!("Backward: {:?}", list.traverse_backward()); // [3, 2, 1]

    list.pop_front();
    list.pop_back();

    println!("After removals: {:?}", list.traverse_forward()); // [2]
}

Time and Space Complexity

Time Complexity

Space Complexity

Singly vs Doubly Linked List

Playground Links

Rust - Doubly Linked List