Doubly Linked Lists
Learn about doubly linked lists with forward and backward traversal. Understand the trade-offs between singly and doubly linked lists.
Singly linked lists only let us move forward. But what if we need to go backward? Doubly linked lists solve this by adding a second pointer to each node, enabling bidirectional traversal.
What is a Doubly Linked List?
A doubly linked list is a linked list where each node has two pointers:
- next: Points to the next node
- prev: Points to the previous node
Doubly Linked List:
null ← prev | data | next →
+-----+------+-----+ +-----+------+-----+ +-----+------+-----+
null←-| prev| 10 |next-|---->| prev| 20 |next-|---->| prev| 30 |next-|--→ null
+-----+------+-----+ +-----+------+-----+ +-----+------+-----+
head → ↑ ↑ ↑ ↑
| | | |
+-------------+ +-------------+
backward links backward links
Node Structure
use std::rc::Rc;
use std::cell::RefCell;
type Link<T> = Option<Rc<RefCell<Node<T>>>>;
struct Node<T> {
data: T,
prev: Link<T>,
next: Link<T>,
}
impl<T> Node<T> {
fn new(data: T) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Node {
data,
prev: None,
next: None,
}))
}
}
Rust Doubly Linked Lists
Doubly linked lists are challenging in Rust due to ownership rules. We use Rc (Reference Counting) for shared ownership and RefCell for interior mutability. For production code, consider using Vec or VecDeque instead.
Doubly Linked List Class
pub struct DoublyLinkedList<T> {
head: Link<T>,
tail: Link<T>,
size: usize,
}
impl<T> DoublyLinkedList<T> {
pub fn new() -> Self {
Self {
head: None,
tail: None,
size: 0,
}
}
pub fn len(&self) -> usize {
self.size
}
pub fn is_empty(&self) -> bool {
self.size == 0
}
}
Maintaining both head and tail pointers enables O(1) operations at both ends.
Core Operations
Insert at Head - O(1)
impl<T> DoublyLinkedList<T> {
pub fn insert_at_head(&mut self, data: T) {
let new_node = Node::new(data);
match self.head.take() {
Some(old_head) => {
old_head.borrow_mut().prev = Some(new_node.clone());
new_node.borrow_mut().next = Some(old_head);
self.head = Some(new_node);
}
None => {
self.tail = Some(new_node.clone());
self.head = Some(new_node);
}
}
self.size += 1;
}
}
Insert 5 at head:
Before:
head → [10] ⇄ [20] ⇄ [30] ← tail
After:
head → [5] ⇄ [10] ⇄ [20] ⇄ [30] ← tail
Steps:
1. new_node.next = head (5 → 10)
2. head.prev = new_node (5 ← 10)
3. head = new_node
Insert at Tail - O(1)
impl<T> DoublyLinkedList<T> {
pub fn insert_at_tail(&mut self, data: T) {
let new_node = Node::new(data);
match self.tail.take() {
Some(old_tail) => {
old_tail.borrow_mut().next = Some(new_node.clone());
new_node.borrow_mut().prev = Some(old_tail);
self.tail = Some(new_node);
}
None => {
self.head = Some(new_node.clone());
self.tail = Some(new_node);
}
}
self.size += 1;
}
}
O(1) Tail Insertion
Unlike singly linked lists, doubly linked lists with a tail pointer can insert at the tail in O(1) time without traversing the entire list.
Delete at Head - O(1)
impl<T: Clone> DoublyLinkedList<T> {
pub fn delete_at_head(&mut self) -> Option<T> {
self.head.take().map(|old_head| {
match old_head.borrow_mut().next.take() {
Some(new_head) => {
new_head.borrow_mut().prev = None;
self.head = Some(new_head);
}
None => {
self.tail = None;
}
}
self.size -= 1;
Rc::try_unwrap(old_head).ok().unwrap().into_inner().data
})
}
}
Delete at Tail - O(1)
This is where doubly linked lists shine over singly linked lists:
impl<T: Clone> DoublyLinkedList<T> {
pub fn delete_at_tail(&mut self) -> Option<T> {
self.tail.take().map(|old_tail| {
match old_tail.borrow_mut().prev.take() {
Some(new_tail) => {
new_tail.borrow_mut().next = None;
self.tail = Some(new_tail);
}
None => {
self.head = None;
}
}
self.size -= 1;
Rc::try_unwrap(old_tail).ok().unwrap().into_inner().data
})
}
}
Delete at tail:
Before:
[10] ⇄ [20] ⇄ [30] ← tail
Steps:
1. tail = tail.prev (tail now points to 20)
2. tail.next = None (remove link to 30)
After:
[10] ⇄ [20] ← tail
Traverse Forward
impl<T: std::fmt::Display> DoublyLinkedList<T> {
pub fn traverse_forward(&self) {
let mut current = self.head.clone();
while let Some(node) = current {
print!("{} ", node.borrow().data);
current = node.borrow().next.clone();
}
println!();
}
}
Traverse Backward
impl<T: std::fmt::Display> DoublyLinkedList<T> {
pub fn traverse_backward(&self) {
let mut current = self.tail.clone();
while let Some(node) = current {
print!("{} ", node.borrow().data);
current = node.borrow().prev.clone();
}
println!();
}
}
Time Complexity Comparison
| Operation | Singly Linked | Doubly Linked | |-----------|---------------|---------------| | Insert at head | O(1) | O(1) | | Insert at tail | O(n)* | O(1) | | Delete at head | O(1) | O(1) | | Delete at tail | O(n) | O(1) | | Delete given node | O(n) | O(1) | | Traverse backward | O(n²)** | O(n) |
*O(1) with tail pointer **Must restart from head for each step
Practical Applications
Browser History
pub struct BrowserHistory {
current: Link<String>,
}
impl BrowserHistory {
pub fn new(homepage: String) -> Self {
Self {
current: Some(Node::new(homepage)),
}
}
pub fn visit(&mut self, url: String) {
let new_page = Node::new(url);
if let Some(curr) = &self.current {
new_page.borrow_mut().prev = Some(curr.clone());
curr.borrow_mut().next = Some(new_page.clone());
}
self.current = Some(new_page);
}
pub fn back(&mut self, steps: usize) -> String {
let mut remaining = steps;
while remaining > 0 {
if let Some(curr) = &self.current {
if let Some(prev) = &curr.borrow().prev {
self.current = Some(prev.clone());
remaining -= 1;
} else {
break;
}
} else {
break;
}
}
self.current.as_ref()
.map(|n| n.borrow().data.clone())
.unwrap_or_default()
}
pub fn forward(&mut self, steps: usize) -> String {
let mut remaining = steps;
while remaining > 0 {
if let Some(curr) = &self.current {
if let Some(next) = &curr.borrow().next {
self.current = Some(next.clone());
remaining -= 1;
} else {
break;
}
} else {
break;
}
}
self.current.as_ref()
.map(|n| n.borrow().data.clone())
.unwrap_or_default()
}
}
Simplified Alternative: Using Vec
For most use cases in Rust, a Vec or VecDeque is more practical:
use std::collections::VecDeque;
pub struct SimpleDoublyLinkedList<T> {
items: VecDeque<T>,
}
impl<T> SimpleDoublyLinkedList<T> {
pub fn new() -> Self {
Self {
items: VecDeque::new(),
}
}
pub fn insert_at_head(&mut self, data: T) {
self.items.push_front(data);
}
pub fn insert_at_tail(&mut self, data: T) {
self.items.push_back(data);
}
pub fn delete_at_head(&mut self) -> Option<T> {
self.items.pop_front()
}
pub fn delete_at_tail(&mut self) -> Option<T> {
self.items.pop_back()
}
pub fn len(&self) -> usize {
self.items.len()
}
}
Trade-offs
Advantages of Doubly Linked Lists:
- O(1) deletion from both ends
- Bidirectional traversal
- O(1) deletion given a node reference
- Natural fit for LRU cache, deque
Disadvantages:
- Extra memory per node (one more pointer)
- More complex code (more pointers to maintain)
- Slightly more overhead per operation
- In Rust: requires Rc<RefCell<>> or unsafe code
Pointer Management
With more pointers to manage, it's easier to introduce bugs. Always update all relevant pointers: prev and next for the new node, and next/prev for adjacent nodes. Drawing diagrams helps avoid mistakes.
Rust Recommendation
In Rust, for most practical applications requiring a deque-like structure, use std::collections::VecDeque instead of implementing a doubly linked list from scratch. VecDeque provides the same O(1) operations at both ends with better cache locality and simpler code.
Key Takeaways
- Doubly linked lists have prev and next pointers in each node
- With head and tail pointers, both ends support O(1) operations
- Bidirectional traversal enables backward iteration
- Essential for LRU caches, deques, and undo functionality
- Trade-off: more memory and complexity for better deletion performance
- In Rust, VecDeque is often a better choice than manual implementation
Doubly linked lists are the foundation for many advanced data structures. The extra pointer per node is a small price for the flexibility of bidirectional traversal and efficient deletion from both ends.