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.
use std::collections::LinkedList; let mut list: LinkedList<i32> = LinkedList::new(); list.push_back(1); list.push_front(0);
Try it
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.
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
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,lenandappendare O(1).split_off(at)has to walk to indexat, so it is O(min(at, len - at)).containsis O(n). - No indexing. There is no
list[i]and noget(i). To reach the nth element uselist.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, aVecwithinsertis 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 aVec<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. SeeVecDeque<T>. - It implements
Clone,Debug,Default,Eq,Ord,Hash,Extend,FromIteratorandFrom<[T; N]>whenTdoes.