Linked List Implementation in Rust

1. Introduction

A linked list is a linear data structure where each element is a separate object called a node. Each node comprises a value and a reference (or link) to the next node in the sequence. Linked lists provide an efficient way to dynamically allocate data structures, as opposed to arrays, which have a fixed size. In this post, we will discuss the implementation of a singly linked list in Rust.

2. Implementation Steps

1. Define the Node struct to store the linked list elements and the link to the next node.

2. Define the LinkedList struct with an Option to a Node as its head.

3. Implement a new function to initialize the linked list.

4. Implement append to add an element to the end of the linked list.

5. Implement prepend to add an element at the beginning.

6. Implement pop to remove the last element.

7. Implement pop_front to remove the first element.

8. Implement peek to see the first element without removing it.

3. Implementation in Rust Programming

type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
    value: T,
    next: Link<T>,
}
pub struct LinkedList<T> {
    head: Link<T>,
}
impl<T> LinkedList<T> {
    // Initialize an empty linked list
    pub fn new() -> Self {
        LinkedList { head: None }
    }
    // Append an element at the end
    pub fn append(&mut self, value: T) {
        let new_node = Box::new(Node {
            value,
            next: None,
        });
        let mut current = &mut self.head;
        while let Some(ref mut node) = *current {
            current = &mut node.next;
        }
        *current = Some(new_node);
    }
    // Prepend an element at the beginning
    pub fn prepend(&mut self, value: T) {
        let new_node = Box::new(Node {
            value,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }
    // Remove and return the last element
    pub fn pop(&mut self) -> Option<T> {
        let mut current = &mut self.head;
        let mut prev = None;
        while let Some(ref mut node) = *current {
            if node.next.is_none() {
                match prev {
                    Some(prev) => prev.next = node.next.take(),
                    None => self.head.take(),
                };
                return Some(node.value);
            }
            prev = *current;
            current = &mut node.next;
        }
        None
    }
    // Remove and return the first element
    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.value
        })
    }
    // Peek at the first element without removing it
    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.value)
    }
}
fn main() {
    let mut list = LinkedList::new();
    list.append("Element 1");
    list.prepend("Element 0");
    list.append("Element 2");
    println!("Peek: {:?}", list.peek());
    println!("Pop Front: {:?}", list.pop_front());
    println!("After Pop Front, Peek: {:?}", list.peek());
    println!("Pop: {:?}", list.pop());
    println!("After Pop, Peek: {:?}", list.peek());
}

Output:

Peek: Some("Element 0")
Pop Front: Some("Element 0")
After Pop Front, Peek: Some("Element 1")
Pop: Some("Element 2")
After Pop, Peek: Some("Element 1")

Explanation:

1. The Node struct contains an element and a link to the next node. The Link type alias is used for clarity and helps to simplify the code.

2. LinkedList struct holds the head node which points to the beginning of the list.

3. The new function initializes an empty linked list.

4. append method traverses to the end of the list and adds a new node.

5. prepend method creates a new node and places it at the beginning, adjusting the head accordingly.

6. pop method traverses the list to the last element, removes it and adjusts the previous node's link.

7. pop_front directly removes the head node and adjusts the head to the next node.

8. The peek method lets us view the head's value without modifying the list.

9. The main function demonstrates various operations on the linked list and prints the results.