Linked Lists

Introduction

In this lesson, we'll explore linked lists, their properties and usage in Rust.

Key Points

Linked lists: A linear data structure where each element (node) points to the next node in the sequence, forming a chain-like structure.
Singly linked lists: A linked list where each element (node) points to the next node in the sequence.
Doubly linked lists: A linked list where each element (node) points to the next and previous nodes in the sequence.

What is a linked list?

A linked list is a linear data structure where each element (node) points to the next node in the sequence, forming a chain-like structure.

Singly Linked Lists

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Box<Node>>,  // Box allows Node to be recursively defined
}

impl Node {
    fn print_list(&self) {
        let mut current = Some(self);
        while let Some(node) = current {
            print!("{} ", node.value);
            current = node.next.as_deref();  // Move to the next node
        }
        println!();
    }

    fn append(&mut self, value: i32) {
        let mut current = self;
        while let Some(ref mut next) = current.next {
            current = next;
        }
        current.next = Some(Box::new(Node {  // Allocate new node on the heap
            value,
            next: None,
        }));
    }
}

fn main() {
    let mut node = Node {
        value: 1,
        next: Some(Box::new(Node {
            value: 2,
            next: Some(Box::new(Node {
                value: 3,
                next: None,
            })),
        })),
    };

    println!("Original list:");
    node.print_list();

    node.append(4);

    println!("List after appending 4:");
    node.print_list();
}

In Rust, Box is a smart pointer that provides ownership of a heap-allocated value. It’s used when you need to store data on the heap rather than the stack. Here’s why Box is often used in linked lists:

Rust’s stack has a limited size and is meant for storing data that has a known, fixed size at compile time. Linked lists, however, can grow in size dynamically, making it impractical to allocate them entirely on the stack. Box allows you to allocate data on the heap, which is much more suitable for dynamically-sized data structures like linked lists.
Linked lists are recursive data structures. Each node contains a reference (or Box) to another node. Without heap allocation, Rust wouldn’t be able to handle the indefinite size of these recursive types because they could lead to an infinitely recursive type definition.

Box breaks this recursion by providing a way to allocate the nodes on the heap, where each Box<Node> holds a reference to another Node.
Box provides ownership of the data, ensuring that the memory is automatically cleaned up when the Box is dropped. This helps manage the memory for dynamically sized data structures without manual memory management.

Doubly Linked Lists

Each node contains a value and references to both the next and previous nodes. Similar to singly linked lists but with an additional reference for bidirectional traversal.

#[derive(Debug)]
use std::cell::RefCell;
use std::rc::Rc;

// Define the Node struct
#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Option<Rc<RefCell<Node<T>>>>,
    prev: Option<Rc<RefCell<Node<T>>>>,
}

// Define the LinkedList struct
#[derive(Debug)]
struct LinkedList<T> {
    head: Option<Rc<RefCell<Node<T>>>>,
    tail: Option<Rc<RefCell<Node<T>>>>,
}

impl<T> LinkedList<T>
where
    T: std::fmt::Debug,
{
    fn new() -> Self {
        LinkedList {
            head: None,
            tail: None,
        }
    }

    fn append(&mut self, value: T) {
        let new_node = Rc::new(RefCell::new(Node {
            value,
            next: None,
            prev: self.tail.clone(),
        }));

        match self.tail.take() {
            Some(tail) => {
                tail.borrow_mut().next = Some(new_node.clone());
            }
            None => {
                self.head = Some(new_node.clone());
            }
        }

        self.tail = Some(new_node);
    }

    fn prepend(&mut self, value: T) {
        let new_node = Rc::new(RefCell::new(Node {
            value,
            next: self.head.clone(),
            prev: None,
        }));

        match self.head.take() {
            Some(head) => {
                head.borrow_mut().prev = Some(new_node.clone());
            }
            None => {
                self.tail = Some(new_node.clone());
            }
        }

        self.head = Some(new_node);
    }

    fn print(&self) {
        let mut current = self.head.clone();
        while let Some(node) = current {
            print!("{:?} ", node.borrow().value);
            current = node.borrow().next.clone();
        }
        println!();
    }
}

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

    list.print(); // Output: 0 1 2 3
}

Explaining the code

Rc (Reference Counted) is a smart pointer that enables multiple ownership of the same data. It keeps track of the number of references to the data it points to. When the reference count drops to zero, the data is automatically de-allocated. Rc is used to allow multiple nodes to be shared between different parts of the list. This enables the nodes to be owned by more than one part of the list without copying the data.
RefCell (Reference Cell) provides interior mutability, allowing you to borrow data mutably even if the RefCell itself is immutably borrowed. It enforces borrowing rules at runtime instead of compile-time. RefCell is used to allow mutable access to the node's fields (next and prev) even though the Rc smart pointer provides shared ownership. This enables you to update the node's pointers while keeping the node shared.
append and prepend functions are used to add and remove nodes from the list. append adds a new node to the end of the list, while prepend adds a new node to the beginning of the list.

Why are Linked Lists important?

Linked lists are a fundamental data structure in computer science and are used in various scenarios. They are useful for maintaining a list of items that need to be accessed in a particular order. They can be used to implement various data structures, such as queues, stacks, and trees. They allow efficient insertions and deletions without needing to resize or reallocate memory like arrays do.

Inserting or deleting an element in a linked list is generally O(1) if you have a reference to the node, whereas in arrays, it can be O(n) due to shifting elements.

Linked lists encourage algorithmic thinking and problem-solving skills by requiring you to manage pointers and ensure data consistency and their commonly featured om technical interview questions.

Conclusion

Understanding linked lists is crucial for a well-rounded knowledge of data structures. They offer unique advantages for dynamic memory management and efficient insertion and deletion, and they form the basis for more complex data structures. By mastering linked lists, you gain insights into memory management, performance trade-offs, and algorithmic design, all of which are essential skills in computer science and software development.

Learn Data Structures and Algorithms