Step 5 of 6

LinkedList, and why it's rare

The standard library also has std::collections::LinkedList<T>, a doubly linked list. Each element lives in its own heap allocation, a node, which holds the value and pointers to the previous and next nodes.

What that buys you:

• push_front, push_back, pop_front, pop_back: O(1), like VecDeque.
• append(&mut other): moves all of another list onto the end in O(1), by relinking two pointers. Nothing is copied.
• split_off(at): cuts the list in two (O(n) to walk to the cut point).

What it costs:

• No indexing. Getting the i-th element means walking i nodes: O(n).
• One allocation per element, plus two pointers of overhead each.
• Poor cache use. The CPU reads memory in chunks; a Vec's items sit side by side, so one read brings in many of them. A list's nodes are scattered around the heap, so walking it is a chain of slow memory reads. In practice, iterating a Vec is many times faster than iterating a list of the same length.

use std::collections::LinkedList;

fn main() {
    let mut playlist: LinkedList<&str> = LinkedList::new();
    playlist.push_back("Intro");
    playlist.push_back("Verse");
    playlist.push_front("Countdown");

    let mut encore = LinkedList::from(["Chorus", "Outro"]);
    playlist.append(&mut encore); // O(1): relinks, copies nothing

    println!("{:?}", playlist);
    println!("encore is now empty: {}", encore.is_empty());
    println!("third: {:?}", playlist.iter().nth(2));
    let tail = playlist.split_off(3);
    println!("{:?} | {:?}", playlist, tail);
}

["Countdown", "Intro", "Verse", "Chorus", "Outro"]
encore is now empty: true
third: Some("Verse")
["Countdown", "Intro", "Verse"] | ["Chorus", "Outro"]

There's no playlist[2]; the compiler refuses it:

use std::collections::LinkedList;

fn main() {
    let list: LinkedList<i32> = LinkedList::from([1, 2, 3]);
    println!("{}", list[1]);
}

error[E0608]: cannot index into a value of type `LinkedList<i32>`

Why you'll rarely use it

The standard library's own documentation says it's almost always better to use Vec or VecDeque. The usual textbook argument for linked lists is "O(1) insert and remove in the middle", but that needs a pointer to the spot first, and std's LinkedList can't even remove from the middle on stable Rust (its cursor API is still unstable). Finding the spot is O(n) anyway, and Vec's insert (a fast memory move) usually beats walking a list to get there.

In a code review, a LinkedList usually gets the comment "use VecDeque". It's worth knowing it exists, what append costs, and why it loses. Writing your own linked structures (with Option<Box<Node>>) is a different story: that's how trees work, and you'll build one in the graphs module.

Common mistakes

• Reaching for LinkedList for a queue. VecDeque does the same O(1) operations at both ends, faster.
• list.iter().nth(i) in a loop. Each call walks from the front: a loop over all positions is O(n²).
• Forgetting that append empties the other list. It takes &mut other and moves the nodes out of it.

Your task

Fill in the blanks with the right LinkedList methods so the bus route program prints:

["Garage", "Depot", "Market St", "Harbor", "Airport"]
Some("Garage")
4

Challenge 2

The radio station's playlist is a LinkedList<String>. The DJ wants to move the last k songs to the front, keeping their order: with [a, b, c, d, e] and k = 2 the list becomes [d, e, a, b, c].

Write fn move_last_to_front(list: &mut LinkedList<String>, k: usize) with split_off and append (no copying of songs). If k is 0 or at least the list's length, leave the list as it is.

Challenge 3

Code review. A teammate wrote the ticket line below with a LinkedList. It works, but profiling shows ticket_at takes most of the time once 100,000 people are waiting: each call walks the list from the front.

Rewrite TicketLine to use a VecDeque<u32> instead (no LinkedList anywhere), keeping every method's behavior. ticket_at(i) must become O(1). The tests call it 100,000 times on a line of 100,000 tickets.

Previous: Range queries with BTreeMap and BTreeSet Next: Choosing a collection