Skip to content
Tutorials Center
My learning

Topics

Rust Reference ยท Collections

Rust LinkedList<T> type

Reference for Rust std::collections::LinkedList: push and pop at both ends, append, split_off, iteration, and why Vec or VecDeque is usually faster.

LinkedList<T> in std::collections is a doubly linked list. Every element lives in its own heap node with a pointer to the previous and next node. You can push and pop at both ends in O(1), and you can join two lists or split one in two without copying elements one by one.

In practice it is rarely the best choice. Nodes are scattered in memory, so iteration is slow compared with Vec<T> or VecDeque<T>, and there is no indexing. The standard LinkedList also has no stable cursor API for inserting in the middle, so its main advantage in textbooks (cheap insertion at a known position) is not available on stable Rust. Reach for it only when you really need O(1) append or split_off.

Rust
use std::collections::LinkedList;

let mut list: LinkedList<i32> = LinkedList::new();
list.push_back(1);
list.push_front(0);

Try it

Rust Both ends of a list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Rust append and split_off

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Syntax

Rust
pub struct LinkedList<T> { /* private */ }

impl<T> LinkedList<T> {
    pub const fn new() -> LinkedList<T>;
    pub fn push_back(&mut self, elt: T);
    pub fn push_front(&mut self, elt: T);
    pub fn pop_back(&mut self) -> Option<T>;
    pub fn pop_front(&mut self) -> Option<T>;
    pub fn front(&self) -> Option<&T>;
    pub fn back(&self) -> Option<&T>;
    pub fn front_mut(&mut self) -> Option<&mut T>;
    pub fn back_mut(&mut self) -> Option<&mut T>;
    pub fn append(&mut self, other: &mut LinkedList<T>);
    pub fn split_off(&mut self, at: usize) -> LinkedList<T>;
    pub fn len(&self) -> usize;
    pub fn is_empty(&self) -> bool;
    pub fn clear(&mut self);
    pub fn contains(&self, x: &T) -> bool where T: PartialEq;
    pub fn iter(&self) -> Iter<'_, T>;
    pub fn iter_mut(&mut self) -> IterMut<'_, T>;
}
Name Description
elt The value to add; the list takes ownership.
other The list whose nodes are moved to the end of self; it is left empty.
at Index of the first element of the returned tail.
x The value to look for with contains (compared with ==).

Returns: the pop_*, front* and back* methods return an Option that is None for an empty list. split_off returns the elements from at to the end.

Errors and panics: split_off panics if at > len(). There are no other panicking methods. contains is a linear scan, O(n).

Usage notes

  • Complexity: push/pop at either end, front, back, len and append are O(1). split_off(at) has to walk to index at, so it is O(min(at, len - at)). contains is O(n).
  • No indexing. There is no list[i] and no get(i). To reach the nth element use list.iter().nth(n), which is O(n).
  • No insertion in the middle on stable Rust. The cursor API (cursor_front_mut) exists but is unstable. If you need to insert at arbitrary positions, a Vec with insert is often still faster for realistic sizes because of cache behavior.
  • Memory: each element costs a separate allocation plus two pointers, so a LinkedList<u8> uses many times more memory than a Vec<u8>.
  • Iteration order: iter() goes front to back and is double-ended, so .rev() works. into_iter() consumes the list.
  • Prefer VecDeque<T> for queues and double-ended stacks: same O(1) ends, far better speed. See VecDeque<T>.
  • It implements Clone, Debug, Default, Eq, Ord, Hash, Extend, FromIterator and From<[T; N]> when T does.