Singly Linked List

A singly linked list is the simplest form of a linked list. Each node stores a value and a reference to the next node only. Traversal is strictly one-directional, starting from the head and moving toward the tail.

Singly linked lists form the foundation for many other data structures, including stacks, queues, and adjacency lists in graphs.

Structure of a Singly Linked List

Each node contains:

• Data - the value stored
• Next - a reference to the next node in the list

Head
 ↓
[1] → [2] → [3] → null

There is no reference to the previous node.

Key Characteristics

• One-directional traversal
• Dynamic size
• Efficient insertions and deletions
• No random access

Basic Operations

A singly linked list typically supports:

1. Insertion

   • At the head
   • At the tail

2. Deletion

   • By value
   • From the head

3. Traversal

4. Search

Rust Representation

In Rust, a singly linked list is commonly implemented using Option<Box<Node<T>>>, which provides ownership safety and automatic memory cleanup.

Rust Implementation

#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub next: Option<Box<Node<T>>>,
}

#[derive(Debug)]
pub struct SinglyLinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T: PartialEq> SinglyLinkedList<T> {
    pub fn new() -> Self {
        Self { head: None }
    }

    pub fn push_front(&mut self, value: T) {
        let new_node = Box::new(Node {
            value,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn push_back(&mut self, value: T) {
        let new_node = Box::new(Node { value, next: None });
    
        let mut current = &mut self.head;
        while let Some(node) = current {
            current = &mut node.next;
        }
    
        *current = Some(new_node);
    }

    pub fn remove(&mut self, value: &T) -> bool {
        let mut current = &mut self.head;
    
        while let Some(mut boxed_node) = current.take() {
            if &boxed_node.value == value {
                *current = boxed_node.next.take();
                return true;
            } else {
                *current = Some(boxed_node);
                current = &mut current.as_mut().unwrap().next;
            }
        }
    
        false
    }


    pub fn contains(&self, value: &T) -> bool {
        let mut current = self.head.as_deref();

        while let Some(node) = current {
            if &node.value == value {
                return true;
            }
            current = node.next.as_deref();
        }

        false
    }

    pub fn traverse(&self) -> Vec<&T> {
        let mut values = Vec::new();
        let mut current = self.head.as_deref();

        while let Some(node) = current {
            values.push(&node.value);
            current = node.next.as_deref();
        }

        values
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_works() {
        let mut list = SinglyLinkedList::new();

        list.push_front(2);
        list.push_front(1);
        list.push_back(3);

        assert_eq!(list.traverse(), vec![&1, &2, &3]);
        assert!(list.contains(&2));
        assert!(list.remove(&2));
        assert!(!list.contains(&2));
    }
}

Example Usage

fn main() {
    let mut list = SinglyLinkedList::new();

    list.push_front(2);
    list.push_front(1);
    list.push_back(3);

    println!("{:?}", list.traverse()); // [1, 2, 3]

    list.remove(&2);
    println!("{:?}", list.traverse()); // [1, 3]
}

Time and Space Complexity

Time Complexity

Space Complexity

Limitations of Singly Linked Lists

• No backward traversal
• No random access
• Slight memory overhead per node

These limitations are addressed by doubly linked lists, which add a backward pointer.

Playground Links

Rust - Linked List