Doubly Linked List Implementation in Rust

1. Introduction

A doubly linked list is an advancement over the singly linked list. It consists of nodes that contain data and two pointers (or links), one pointing to the next node (next) and the other to the previous node (prev). This bi-directional linkage allows traversals in both directions, making operations like insertions, deletions, and traversals more efficient in certain scenarios. In this post, we will cover the implementation of a doubly linked list in Rust.

2. Implementation Steps

1. Define the Node struct with value, next, and prev attributes.

2. Define the DoublyLinkedList struct holding pointers to the head and tail of the list.

3. Implement the new function for initializing an empty list.

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

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

6. Implement methods to remove nodes from both the beginning (pop_front) and the end (pop).

7. Add a peek_front and peek_back method to view the first and last element without removing it.

3. Implementation in Rust Programming

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

Output:

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

Explanation:

1. We use a Node struct containing an element with two links for next and prev nodes.

2. The DoublyLinkedList holds pointers to both the head and tail of the list.

3. The new function initializes an empty list.

4. The append method adds a new node to the end