Data Structures and Algorithms in Rust

1. Built-in linked list data type

Rust provides a built-in linked list data type called LinkedList. It is a doubly linked list, but we can use it as a singly linked list as well.

use std::collections::LinkedList;

fn main() {

    let mut list = LinkedList::new();

    list.push_back(2);
    list.push_back(34);
    list.push_back(8);
    list.push_back(63);
    println!("Linked list: {:?}", list);

    let popped = list.pop_back();
    println!("Popped value: {}", popped.unwrap());
}

We need to import the LinkedList from the std::collections module:

use std::collections::LinkedList;

To to create a linked list we can use the new function:

    let mut list = LinkedList::new();

Operations

There are two operations in a singly linked list to interact with the data:

1. push_back: This function is used to insert a node at the end of the linked list.

    list.push_back(2);
    list.push_back(34);
    list.push_back(8);
    list.push_back(63);

2. pop_back: This function is used to delete a node from the linked list.

    let popped = list.pop_back();

2. Doubly linked list

Doubly linked lists extend the functionality of singly linked lists by providing two additional methods: push_front and pop_front.

push_front is used to insert a node at the beginning of the linked list.

    list.push_front(34);
    list.push_front(2);
    println!("Linked list: {:?}", list);

pop_front: This function is used to delete a node from the linked list.

    let popped = list.pop_front();

Let's implement our new functions:

use std::collections::LinkedList;

fn main() {

    let mut list = LinkedList::new();

    list.push_back(8);
    list.push_back(63);
    println!("Linked list: {:?}", list);

    list.push_front(34);
    list.push_front(2);
    println!("Linked list: {:?}", list);
    

    let popped = list.pop_front();
    println!("Popped value: {}", popped.unwrap());
}

When you run this code, you will notice that the when you push_back elements, they are stored in the order in which they are pushed. However, when you push_front elements, they are stored in the reverse order. This is because the push_front function is inserting the new node at the beginning of the linked list.

Linked list: [2, 34, 8, 63]

Take a look at the result. The last number you added will be the first.