Module singly_linked_list

A safe, owned, singly-linked list

About

The primary goal with this implementation is to offer a simple linked list with no unsafe code. The list does this with Box-type pointers to owned, heap-allocated objects.

Design

This exceedingly simple, safe, singly-linked list consists of one primary LinkedList struct that provides stack and queue operations.

The list operates on a single, private Node struct that contains only a data field (generic over T) and a next pointer as Option<Box<Node<T>>>. Due to the owned nature of the pointers and safe-code-only design restriction, it is not possible to sort this list in place.

Iterators

This list does not have any positional implementation, meaning that you cannot get pointers to arbitrary nodes within the list. The list does provide an iter() method that yields an iterator over immutable references to Node data, consistent with Rust naming convention. Providing an iter_mut() that yields mutable references to the underlying Node data in safe Rust is currently beyond the scope of this structure. See the doubly-linked variant which uses a CursorMut API for mutable references to Node data.

TODO:

• Implement add/remove operations at arbitrary “indexes” (non-positional)

Examples

This example illustrates stack (FILO) operations

    use dsa_rust::sequences::singly_linked_list::LinkedList;

    let mut list: LinkedList<char> = LinkedList::new();

    list.push('c');
    list.push('b');
    list.push('a'); // list: a, b, c

    for e in list.iter() {
        println!("{e}")
    }

    // Tests that the head is really the head
    assert_eq!(list.peek().unwrap(), &'a');
    assert_eq!(list.pop().unwrap(), 'a'); // list: b, c

    list.push('d'); // list: d, b, c

    list.pop(); // list: b, c
    list.pop(); // list: c
    assert_eq!(list.peek().unwrap(), &'c');
    assert_eq!(list.pop().unwrap(), 'c'); // list: None

    assert_eq!(list.peek(), None); // Looks like theres None left
    assert_eq!(list.pop(), None); // dont wanna unwrap() on None!

This example illustrates queue (FIFO) operations

    use dsa_rust::sequences::singly_linked_list::LinkedList;

    let mut list: LinkedList<char> = LinkedList::new();

    list.enqueue('a');
    list.enqueue('b');
    list.enqueue('c'); // list: a, b, c

    // Tests that the head is really the head
    assert_eq!(list.peek().unwrap(), &'a');
    assert_eq!(list.dequeue().unwrap(), 'a'); // list: b, c

    list.enqueue('d'); // list: b, c, d

    list.dequeue(); // list: c, d
    list.dequeue(); // list: d
    assert_eq!(list.peek().unwrap(), &'d');
    assert_eq!(list.dequeue().unwrap(), 'd'); // list: None

    assert_eq!(list.peek(), None); // Looks like theres None left
    assert_eq!(list.dequeue(), None); // dont wanna unwrap() on None!

This example illustrates a sorting workaround

    use dsa_rust::sequences::singly_linked_list::LinkedList;

    // 1) Create a new list of u8 values
    let mut list: LinkedList<u8> = LinkedList::new();

    // 2) (Add elements to the list)

    // 3) Push the list to an easily-sortable structure
    let mut data: Vec<_> = list.iter().cloned().collect();

    // 4) Sort the Vec in O(n log n) time
    data.sort();

    // 5) Reconstruct the list as a sorted variant
    let mut sorted_list = LinkedList::new();
    for node in data {
        //
        // Use push() to create list in descending order
        // Use enqueue() to create list in ascending order
        sorted_list.enqueue(node);
    }

Structs

Iter

LinkedList

The ❤️ of the module

Functions

example