LinkedList<T>

A LinkedList<T> stores elements in separate, heap-allocated nodes. Each node knows its own value and holds a pointer to the next node and the previous one. The list itself only keeps track of the head, the tail, and the length. Because the nodes are scattered in memory, adding or removing at either end is always a matter of adjusting a few pointers — constant time, no shifting.

That pointer-based layout is also the reason you rarely see LinkedList in production Rust code. Random access does not exist; reaching the 100th element means walking through 99 nodes. Every node adds at least two pointer-sized fields of overhead, and the lack of memory contiguity defeats the CPU cache.

Internal structure

The standard library's LinkedList<T> is defined roughly as:

// Simplified; the real definition uses NonNull and PhantomData.
struct Node<T> {
    prev: Option<NonNull<Node<T>>>,
    next: Option<NonNull<Node<T>>>,
    element: T,
}
pub struct LinkedList<T, A: Allocator = Global> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    alloc: A,
    marker: PhantomData<Box<Node<T>, A>>,
}

Each node is allocated individually through the global allocator (or a custom one on nightly). The links use NonNull raw pointers; the list owns every node, so dropping the LinkedList walks the chain and deallocates each node.

A tiny list with two elements looks like this in memory:

head ──▸ [prev: null, next: ──────▸ [prev: ──▸ head, next: null, value: "world"]
            value: "hello"]        ◂── tail

The len field is updated eagerly on every mutation, so .len() and .is_empty() are O(1) without counting.

Creating a LinkedList

LinkedList::new() gives you an empty list. Since Rust 1.56 you can also create one directly from an array or any iterator.

use std::collections::LinkedList;
let empty: LinkedList<i32> = LinkedList::new();
let from_array = LinkedList::from([1, 2, 3]);
let from_iter: LinkedList<_> = (0..5).collect();

The from implementations use FromIterator under the hood, which pushes elements onto the back one by one. For a known list of items this is straightforward and clear.

Core operations on the ends

The headline feature of a linked list is O(1) push and pop at both ends. The API mirrors what you would find on a double-ended queue.

use std::collections::LinkedList;
let mut list = LinkedList::new();
list.push_back(1);
list.push_front(0);
list.push_back(2);
// list: 0 ↔ 1 ↔ 2
assert_eq!(list.front(), Some(&0));
assert_eq!(list.back(), Some(&2));
assert_eq!(list.pop_front(), Some(0));
assert_eq!(list.pop_back(), Some(2));
// list now contains only 1

front(), front_mut(), back(), and back_mut() return Option<&T> / Option<&mut T>. They never panic — an empty list simply returns None.

pop_front and pop_back return Option<T>. The element is removed from the list and the node is deallocated. The caller takes ownership of the value.

Moving elements between lists with append

append takes all the nodes from another LinkedList and splices them onto the end of self in O(1) time. No allocation, no copying — the pointer to the other list's head is rewired to self's tail.

use std::collections::LinkedList;
let mut a = LinkedList::from(['h', 'e']);
let mut b = LinkedList::from(['l', 'l', 'o']);
a.append(&mut b);
// a: 'h' ↔ 'e' ↔ 'l' ↔ 'l' ↔ 'o'
assert!(b.is_empty());

After the operation b is empty. This is the operation that genuinely shines with a linked list; no array-based container can merge two collections without reallocation.

Splitting a list with split_off

split_off(at) splits the list at a given index. The first at elements stay in self, the remainder (starting at index at) is returned as a new LinkedList. This operation is O(n) because the list must walk to the split point, but once there the split itself is just a few pointer updates — no element copies.

use std::collections::LinkedList;
let mut list = LinkedList::from([10, 20, 30, 40]);
let tail = list.split_off(2);
// list: 10 ↔ 20
// tail: 30 ↔ 40

split_off panics if at > len. It is a common choice when you need to divide a work queue or partition elements based on an index that you already know — the O(n) walk is often acceptable.

Iterating over a LinkedList

The list provides three iterator types: Iter (immutable references), IterMut (mutable references), and IntoIter (owned values). All three implement DoubleEndedIterator because the list is doubly linked, so you can iterate from front to back or back to front without extra cost.

use std::collections::LinkedList;
let mut list = LinkedList::from([1, 2, 3]);
// Immutable iteration forward
for val in list.iter() {
    println!("{val}");
}
// Mutable iteration — you can change values in place
for val in list.iter_mut() {
    *val *= 10;
}
// list now: 10, 20, 30
// Reverse iteration
let reversed: Vec<_> = list.iter().rev().copied().collect();
assert_eq!(reversed, vec![30, 20, 10]);
// Consuming iteration
let sum: i32 = list.into_iter().sum();
assert_eq!(sum, 60);

Walking the list forward or backward is O(n). There is no way to skip ahead; an iterator is a thin wrapper around the current node pointer.

Nightly features: cursors and drain_filter

On nightly Rust you can enable linked_list_cursors to get cursor_front / cursor_back and their mutable counterparts. A cursor behaves like a position marker that can move forward and backward, insert before/after the current node, or delete the current node — all O(1) after the initial O(n) walk to the desired position.

#![feature(linked_list_cursors)]
use std::collections::LinkedList;
let mut list = LinkedList::from([1, 2, 3, 4]);
let mut cursor = list.cursor_front_mut();
cursor.move_next(); // at element 2
cursor.insert_before(5); // list: 1 ↔ 5 ↔ 2 ↔ 3 ↔ 4
cursor.remove_current(); // removes 2, list: 1 ↔ 5 ↔ 3 ↔ 4

The nightly-only drain_filter method lets you remove elements that match a predicate. It yields the removed elements as an iterator, reusing the existing nodes.

#![feature(drain_filter)]
use std::collections::LinkedList;
let mut numbers = LinkedList::from([1, 2, 3, 4, 5, 6]);
let evens: LinkedList<_> = numbers.drain_filter(|x| *x % 2 == 0).collect();
// numbers: 1, 3, 5
// evens:  2, 4, 6

These features are not yet stable, so production code usually uses Vec or VecDeque with retain and drain instead.

Searching and containment

contains does a linear scan and returns true if any element is equal to the given value. It requires T: PartialEq.

use std::collections::LinkedList;
let list = LinkedList::from(["apple", "banana", "cherry"]);
assert!(list.contains(&"banana"));
assert!(!list.contains(&"grape"));

There is no find method that returns a reference to the element; the idiomatic approach is to use .iter().find().

When LinkedList performs poorly

The Rust standard library documentation itself warns: It is almost always better to use Vec or VecDeque. The reasons are mechanical, not stylistic.

• Memory overhead. Each node stores two pointers (prev, next) plus the element. For a LinkedList<u8>, the overhead is at least 16 bytes on a 64-bit system — 16× the payload — plus alignment padding that can push a single node to 24 bytes. A Vec<u8> stores exactly one byte per element with no per-element pointer overhead.
• Allocation pressure. Every push allocates a new heap node. A Vec amortizes growth, allocating in bulk. Many small allocations fragment memory and stress the allocator.
• Cache misses. Walking a linked list means chasing pointers to unpredictable memory locations. A Vec's contiguous layout lets the CPU prefetch multiple elements into cache at once. For iteration-heavy workloads the speed difference is often 10–50× in favour of Vec or VecDeque.

Common beginner misconceptions

• "Inserting in the middle is O(1)." Only if you already have a cursor or iterator pointing to the insertion point. Finding that point is O(n). In a Vec, insertion at an arbitrary position is O(n) because of element shifting — often still faster than the pointer-chasing walk of a linked list for small-to-medium sizes.
• "Linked lists use less memory because they don't over-allocate." A Vec may hold unused capacity, but a LinkedList pays a per-element overhead that often dwarfs the wasted capacity. For a LinkedList<u32>, every 4 bytes of payload comes with ~16 bytes of pointer overhead.

The genuine use cases

There are a handful of situations where a linked list is the right tool, and they almost all involve avoiding bulk memory moves.

• Frequent splitting and merging of large collections. If your workload repeatedly breaks sequences into pieces and reassembles them, append and split_off avoid copying elements. A Vec would need to allocate new storage and move every element.
• Intrusive data structures in embedded or kernel code. In these environments you often embed the list pointers directly inside existing structs. The standard LinkedList does not support intrusive linking, but a custom linked list built on raw pointers does — and knowing how LinkedList works provides the mental model to build one.
• Lock-free concurrent queues. Many concurrent designs rely on singly- or doubly-linked nodes for atomic pointer swaps. The standard LinkedList is not lock-free, but understanding its pointer logic is foundational for exploring lock-free structures.

Summary

LinkedList<T> is a textbook data structure with a very specific performance profile. It gives you O(1) pushes and pops at both ends and O(1) appending of entire lists, but it charges for those operations with high memory overhead, poor cache behaviour, and no random access. The standard library includes it because those trade-offs occasionally align with real needs — splitting, merging, and intrusive structures — but the documentation is honest that you will likely reach for Vec or VecDeque first.

If you are prototyping a queue or a deque, start with VecDeque. If you need to store a sequence and access it by index, use Vec. If you later find that splitting or merging large lists dominates your runtime, revisit LinkedList and its append / split_off methods.