Introduction

In Rust, LinkedList is a doubly-linked list. It allows for efficient insertion and removal of elements at both ends of the list. LinkedList is part of the standard library's std::collections module and is useful when you need a list with fast, flexible insertion and deletion operations.

Using LinkedList

To use LinkedList, you need to import it from the std::collections module. You can create a LinkedList by using the LinkedList::new method. Elements can be added using methods like push_back and push_front, and accessed or removed using methods like pop_back and pop_front.

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_back(1);
    list.push_back(2);
    list.push_front(0);

    println!("List: {:?}", list);
    println!("First element: {:?}", list.pop_front());
}
// Output:
// List: [0, 1, 2]
// First element: Some(0)

Key Methods

Below are some of the key methods exposed by the LinkedList class:

LinkedList::new

Creates a new, empty LinkedList.

use std::collections::LinkedList;

fn main() {
    let list: LinkedList<i32> = LinkedList::new();
    println!("Created an empty list: {:?}", list);
}
// Output:
// Created an empty list: []

LinkedList::push_back

Adds an element to the back of the LinkedList.

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_back(10);
    list.push_back(20);
    println!("List after push_back: {:?}", list);
}
// Output:
// List after push_back: [10, 20]

LinkedList::push_front

Adds an element to the front of the LinkedList.

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_front(5);
    list.push_front(15);
    println!("List after push_front: {:?}", list);
}
// Output:
// List after push_front: [15, 5]

LinkedList::pop_back

Removes and returns the last element from the LinkedList. Returns None if the list is empty.

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_back(30);
    list.push_back(40);
    println!("Popped element: {:?}", list.pop_back());
    println!("List after pop_back: {:?}", list);
}
// Output:
// Popped element: Some(40)
// List after pop_back: [30]

LinkedList::pop_front

Removes and returns the first element from the LinkedList. Returns None if the list is empty.

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_front(50);
    list.push_front(60);
    println!("Popped element: {:?}", list.pop_front());
    println!("List after pop_front: {:?}", list);
}
// Output:
// Popped element: Some(60)
// List after pop_front: [50]

Example Usage

Example 1: Basic Usage

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_back(1);
    list.push_back(2);
    list.push_front(0);

    println!("List: {:?}", list);
    println!("First element: {:?}", list.pop_front());
}
// Output:
// List: [0, 1, 2]
// First element: Some(0)

Example 2: Inserting at Both Ends

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_back(5);
    list.push_front(3);
    list.push_back(7);
    println!("List: {:?}", list);
}
// Output:
// List: [3, 5, 7]

Example 3: Removing Elements

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_back(10);
    list.push_back(20);
    list.push_back(30);

    println!("Removed from front: {:?}", list.pop_front());
    println!("Removed from back: {:?}", list.pop_back());
    println!("List: {:?}", list);
}
// Output:
// Removed from front: Some(10)
// Removed from back: Some(30)
// List: [20]

Example 4: Iterating Over Elements

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);

    for element in &list {
        println!("{}", element);
    }
}
// Output:
// 1
// 2
// 3

Example 5: Using Double-Ended Iterator

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);

    let mut iter = list.iter();
    println!("First: {:?}", iter.next());
    println!("Last: {:?}", iter.next_back());
}
// Output:
// First: Some(1)
// Last: Some(3)

Considerations

LinkedList is useful for cases where you need frequent insertions and deletions at both ends of the list.
It is generally not as memory efficient as Vec for random access or iteration.
Operations like insertions and deletions in the middle of the list are more efficient than in Vec, but still linear in complexity.