Linked List | Dheerendra Varma

What is a Linked List?

A linked list is a sequence of nodes where each node stores a value and a pointer to the next node. Unlike arrays, elements are not contiguous in memory — each node is an independent heap allocation. This makes prepend O(1) (update one pointer) but random access O(n) (follow pointers from the head).

Rust's ownership model makes the canonical singly linked list representation straightforward: each node owns its successor through Option<Box<Node>>. The Option represents the possibility of a null terminus; Box allocates the next node on the heap and transfers ownership to the current node, giving a clean recursive ownership chain.

Applications

Hash tables use linked lists (or dynamic arrays) to chain elements that hash to the same bucket. Operating system memory allocators maintain a free list of available blocks as a linked list threaded through the free memory itself. LRU caches combine a hash map with a doubly linked list to achieve O(1) access and O(1) eviction. Polynomial arithmetic represents each term as a node with coefficient and exponent. Adjacency lists in graph representations are linked lists of neighbours.

Representations

The singly linked list is the simplest form. Each node owns the next node; the head owns the whole list.

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}
 
impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}
 
// Build list 1 -> 2 -> 3 -> None
fn build_list(vals: &[i32]) -> Option<Box<ListNode>> {
    let mut head = None;
    for &v in vals.iter().rev() {
        let mut node = Box::new(ListNode::new(v));
        node.next = head;
        head = Some(node);
    }
    head
}
 
fn print_list(head: &Option<Box<ListNode>>) {
    let mut curr = head;
    while let Some(node) = curr {
        print!("{} -> ", node.val);
        curr = &node.next;
    }
    println!("None");
}

A doubly linked list adds a backward pointer, enabling O(1) removal of a node given only its reference. Doubly linked lists are essential for LRU caches. In Rust, doubly linked lists require shared mutable references which conflict with single-ownership. The standard approach is to use index-based simulation with a Vec where each slot stores the value plus prev/next indices — avoiding unsafe or Rc<RefCell<>> complexity.

struct DoublyLinkedList {
    vals: Vec<i32>,
    prev: Vec<Option<usize>>,
    next: Vec<Option<usize>>,
    head: Option<usize>,
    tail: Option<usize>,
}

Operations and Time Complexity

Operation	Singly	Doubly	Notes
Access by index	O(n)	O(n)	Must traverse from head
Search by value	O(n)	O(n)	Linear scan
Insert at head	O(1)	O(1)	Update head pointer
Insert at tail	O(n) / O(1)*	O(1)	O(1) with tail pointer
Insert at position	O(n)	O(n)	Traverse to position first
Delete at head	O(1)	O(1)	Advance head pointer
Delete at position	O(n)	O(n) to find, O(1) to remove
Delete given node	O(n)	O(1)	Doubly: update prev/next directly

Implementation in Rust

#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}
 
impl ListNode {
    fn new(val: i32) -> Self { ListNode { val, next: None } }
}
 
struct LinkedList {
    head: Option<Box<ListNode>>,
    len: usize,
}
 
impl LinkedList {
    fn new() -> Self { LinkedList { head: None, len: 0 } }
 
    fn push_front(&mut self, val: i32) {
        let mut node = Box::new(ListNode::new(val));
        node.next = self.head.take();
        self.head = Some(node);
        self.len += 1;
    }
 
    fn push_back(&mut self, val: i32) {
        let new_node = Some(Box::new(ListNode::new(val)));
        match self.head {
            None => self.head = new_node,
            Some(_) => {
                let mut curr = self.head.as_mut().unwrap();
                while curr.next.is_some() {
                    curr = curr.next.as_mut().unwrap();
                }
                curr.next = new_node;
            }
        }
        self.len += 1;
    }
 
    fn pop_front(&mut self) -> Option<i32> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.len -= 1;
            node.val
        })
    }
 
    fn len(&self) -> usize { self.len }
 
    fn contains(&self, val: i32) -> bool {
        let mut curr = &self.head;
        while let Some(node) = curr {
            if node.val == val { return true; }
            curr = &node.next;
        }
        false
    }
}

Fundamental Algorithms and Problems

Reverse a Linked List

Reverse the list in-place using three pointers: prev (starts at None), curr (starts at head), and the saved next. At each step, redirect curr.next to prev, then advance all three pointers. When curr becomes None, prev is the new head.

fn reverse(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev: Option<Box<ListNode>> = None;
    let mut curr = head;
 
    while let Some(mut node) = curr {
        curr = node.next.take(); // save next, break current link
        node.next = prev;        // redirect to previous
        prev = Some(node);       // advance prev
    }
    prev // new head
}
 
fn main() {
    let list = build_list(&[1, 2, 3, 4, 5]);
    let reversed = reverse(list);
    print_list(&reversed); // 5 -> 4 -> 3 -> 2 -> 1 -> None
}

Detect a Cycle — Floyd's Tortoise and Hare

To demonstrate cycle detection, simulate a linked list with potential cycles using index arrays. The fast pointer moves two steps per iteration; the slow pointer moves one. If a cycle exists, the fast pointer will eventually lap the slow pointer and they meet inside the cycle. If no cycle exists, the fast pointer reaches the end.

// nexts[i] = Some(j) means node i points to node j; None means terminus
fn has_cycle(nexts: &[Option<usize>]) -> bool {
    let (mut slow, mut fast) = (0usize, 0usize);
    loop {
        slow = match nexts[slow] { Some(n) => n, None => return false };
        fast = match nexts[fast] { Some(n) => n, None => return false };
        fast = match nexts[fast] { Some(n) => n, None => return false };
        if slow == fast { return true; }
    }
}
 
fn main() {
    // 0->1->2->3->4->2 (cycle at index 2)
    let nexts = [Some(1), Some(2), Some(3), Some(4), Some(2)];
    println!("{}", has_cycle(&nexts)); // true
 
    // 0->1->2->3->None
    let nexts2 = [Some(1), Some(2), Some(3), None];
    println!("{}", has_cycle(&nexts2)); // false
}

Find the Middle Node

Two pointers at different speeds find the middle without knowing the length. The slow pointer moves one step; the fast pointer moves two. When fast reaches the end, slow is at the middle. For even-length lists, slow lands at the second middle node.

fn find_middle(head: &Option<Box<ListNode>>) -> i32 {
    let mut slow: &Option<Box<ListNode>> = head;
    let mut fast: &Option<Box<ListNode>> = head;
 
    loop {
        let f = match fast { Some(n) => n, None => break };
        let ff = match &f.next { Some(n) => n, None => break };
        fast = &ff.next;
        slow = &slow.as_ref().unwrap().next;
    }
    slow.as_ref().unwrap().val
}
 
fn main() {
    let list = build_list(&[1, 2, 3, 4, 5]);
    println!("{}", find_middle(&list)); // 3
 
    let list = build_list(&[1, 2, 3, 4]);
    println!("{}", find_middle(&list)); // 3 (second middle)
}

Merge Two Sorted Lists

Merge two sorted lists into one sorted list. Compare the heads of the two lists, take the smaller, and recursively merge the rest. The recursion depth is at most the total length of both lists. Alternatively, build the merged list iteratively using a dummy head node to avoid special-casing the head.

fn merge_sorted(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    match (l1, l2) {
        (None, r) | (r, None) => r,
        (Some(n1), Some(n2)) => {
            if n1.val <= n2.val {
                Some(Box::new(ListNode {
                    val: n1.val,
                    next: merge_sorted(n1.next, Some(n2)),
                }))
            } else {
                Some(Box::new(ListNode {
                    val: n2.val,
                    next: merge_sorted(Some(n1), n2.next),
                }))
            }
        }
    }
}
 
fn main() {
    let l1 = build_list(&[1, 3, 5]);
    let l2 = build_list(&[2, 4, 6]);
    let merged = merge_sorted(l1, l2);
    print_list(&merged); // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
}

Remove Nth Node from End — Two-Pointer Gap

Remove the nth node from the end of a list in a single pass. Advance the fast pointer n steps ahead. Then advance both pointers together until fast reaches the last node. The slow pointer is now just before the node to remove. A dummy head node handles the edge case of removing the first node cleanly.

fn remove_nth_from_end(head: Option<Box<ListNode>>, n: usize) -> Option<Box<ListNode>> {
    let mut dummy = Box::new(ListNode { val: 0, next: head });
 
    // Count length to determine target position (two-pass)
    let mut length = 0;
    {
        let mut curr = &dummy.next;
        while let Some(node) = curr { length += 1; curr = &node.next; }
    }
 
    let target = length - n; // index of node before the one to remove
    let mut curr = &mut dummy as &mut ListNode;
    for _ in 0..target {
        curr = curr.next.as_mut().unwrap();
    }
    curr.next = curr.next.take().and_then(|node| node.next);
    dummy.next
}
 
fn main() {
    let list = build_list(&[1, 2, 3, 4, 5]);
    let result = remove_nth_from_end(list, 2);
    print_list(&result); // 1 -> 2 -> 3 -> 5 -> None
}