Circular Linked List Implementation in Rust

1. Introduction

A Circular Linked List is a variation of the standard Linked List wherein the last node points back to the first node, forming a closed loop. This circular structure offers advantages for scenarios where a round-robin access pattern is advantageous. In this post, we will delve into the implementation of a Circular Linked List in Rust.

2. Implementation Steps

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

2. Define the CircularLinkedList struct holding a pointer to the head of the list.

3. Implement the new function to initialize an empty list.

4. Implement the append function to add an element to the list.

5. Implement the pop function to remove and return the first element.

6. Add a peek function to view the first element without removing it.

7. Implement logic ensuring that the tail node always points back to the head.

3. Implementation in Rust Programming

type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
    value: T,
    next: Link<T>,
}
pub struct CircularLinkedList<T> {
    head: Link<T>,
    tail: *mut Node<T>,
}
impl<T> CircularLinkedList<T> {
    // Initialize an empty list
    pub fn new() -> Self {
        CircularLinkedList { head: None, tail: std::ptr::null_mut() }
    }
    // Add an element to the list
    pub fn append(&mut self, value: T) {
        let mut new_node = Box::new(Node {
            value,
            next: None,
        });
        let raw_node = Box::into_raw(new_node);
        unsafe {
            if !self.tail.is_null() {
                (*self.tail).next = Some(Box::from_raw(raw_node));
            } else {
                self.head = Some(Box::from_raw(raw_node));
            }
            self.tail = raw_node;
            (*self.tail).next = self.head.clone();
        }
    }
    // Remove and return the first element
    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            if !self.tail.is_null() && unsafe { (*self.tail).next.as_ref() == Some(&*old_head) } {
                unsafe {
                    self.tail = std::ptr::null_mut();
                }
            } else {
                self.head = old_head.next.clone();
                unsafe {
                    if !self.tail.is_null() {
                        (*self.tail).next = self.head.clone();
                    }
                }
            }
            old_head.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 = CircularLinkedList::new();
    list.append("Element 1");
    list.append("Element 2");
    list.append("Element 3");
    println!("Peek: {:?}", list.peek());
    println!("Pop: {:?}", list.pop());
    println!("After Pop, Peek: {:?}", list.peek());
}

Output:

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

Explanation:

1. The Node struct holds the element data and a pointer to the next node.

2. The CircularLinkedList struct holds pointers to the head of the list and the tail. The tail is maintained as a raw pointer to allow for safe circular references.

3. The new function initializes an empty list.

4. In the append method, we add a node to the list while ensuring the tail's next pointer always points back to the head, maintaining the circular nature.

5. The pop function removes the head node, adjusts the head pointer, and updates the tail's next pointer if necessary.

6. The peek function allows checking the first element without removing it.