`LinkedList`

The LinkedList in Rust stores elements like a Vector does, but it has different performance characteristics. It can be found in the std collections module.

LinkedList is usually slower than Vector, except for appending other LinkedLists, or placing elements at the start. It stores elements separately in Nodes, not in a single buffer.

Example

This Rust program uses the LinkedList, and shows how to add and remove elements from the LinkedList. It uses append() which combines 2 LinkedLists efficiently.

Part 1 We create a LinkedList with new(). No capacity can be specified—there is no underlying buffer. We add elements with push_back.

Part 2 For inserting elements at the start (prepend) we can use push_front. This is similar to how VecDeque works.

Part 3 For removing at the end and the start, we can use pop_back and pop_front. These methods also return the removed values.

Part 4 A key performance advantage of LinkedList is that it allows fast appending of other LinkedLists—we can use append() for this.

Part 5 As with Vec, we can use a for-loop with iter() or into_iter(). Here we use the implicit iterator (into_iter).

use std::collections::*;

fn main() {
    // Part 1: create new LinkedList and use push_back to add elements.
    let mut k = LinkedList::new();
    k.push_back(500);
    k.push_back(200);
    k.push_back(0);
    println!("push_back:  {:?}", k);

    // Part 2: use push_front to add an element to the start.
    k.push_front(-100);
    println!("push_front: {:?}", k);

    // Part 3: use pop_back and pop_front to remove 1 element from the end and start.
    k.pop_back();
    k.pop_front();
    println!("pop_back, pop_front: {:?}", k);

    // Part 4: create a second LinkedList, and append it to the first.
    let mut k2 = LinkedList::from([1000, 2000, 3000]);
    k.append(&mut k2);

    // Part 5: loop over elements in the LinkedList and print them.
    for element in k {
        println!("Element: {element}");
    }
}push_back:  [500, 200, 0]
push_front: [-100, 500, 200, 0]
pop_back, pop_front: [500, 200]
Element: 500
Element: 200
Element: 1000
Element: 2000
Element: 3000

Usage notes

Usually it is better to use Vec or VecDeque. Modern computer architectures are optimized for collections that use an underlying buffer. LinkedList is thus usually slower.

Summary

With LinkedList we have a collection that can be efficiently added to at both its start and end. It also supports fast appending a second collection, which is not possible with Vectors.