Rust - LinkedList Use - Dot Net Perls

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.

vec

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.

VecDeque

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).

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.

Dot Net Perls is a collection of pages with code examples, which are updated to stay current. Programming is an art, and it can be learned from examples.

Donate to this site to help offset the costs of running the server. Sites like this will cease to exist if there is no financial support for them.

Sam Allen is passionate about computer languages, and he maintains 100% of the material available on this website. He hopes it makes the world a nicer place.

This page was last updated on Jan 6, 2025 (new).

Home

Changes