Struct SinglyLinkedList 

pub struct SinglyLinkedList<T> { /* private fields */ }

A singly-linked list implementation with efficient insertion at the front and back.

The SinglyLinkedList stores elements in a linear sequence where each element points to the next one. It provides O(1) push and pop_front operations.

Type Parameters

• T: The type of elements stored in the list.

Examples

use plain_ds::SinglyLinkedList;

let mut list = SinglyLinkedList::new();
list.push(1);
list.push(2);
list.push(3);

assert_eq!(list.pop(), Some(3));
assert_eq!(list.len(), 2);

Implementations

impl<T> SinglyLinkedList<T>

pub fn new() -> Self

Creates empty singly-linked list.

pub fn from_slice(slice: &[T]) -> Self

where T: Clone,

Creates list from slice.

Efficiency: O(n)

pub fn to_vec(&self) -> Vec<T>

where T: Clone,

Collect list values into a vector.

Efficiency: O(n)

pub fn push_front(&mut self, payload: T)

Adds a new node to the front of the list.

Efficiency: O(1)

pub fn insert(&mut self, index: usize, payload: T) -> Result<()>

Insert a new node at the specified location in the list. Error returns, if the index out of bounds.

Efficiency: O(n)

pub fn find_if(&self, predicate: impl Fn(&T) -> bool) -> Option<usize>

where T: PartialEq,

Finds the first node whose payload satisfies the predicate and returns its index. Returns None if there is no such node.

Efficiency: O(n)

pub fn sort(&mut self)

where T: PartialOrd + Default,

Sorts the list in ascending order using merge sort algorithm.

Efficiency: O(n log n)

Space complexity: O(log n) due to recursion stack

Trait Implementations

impl<'a, T: 'a> List<'a, T> for SinglyLinkedList<T>

fn len(&self) -> usize

Returns list size.

Efficiency: O(1)

fn head(&self) -> Option<&T>

Returns the payload value of the first node in the list.

Efficiency: O(1)

fn last(&self) -> Option<&T>

Returns the payload value of the last node in the list.

Efficiency: O(1)

fn iter(&self) -> impl Iterator<Item = &'a T>

Returns an iterator over the immutable items of the list.

fn iter_mut(&mut self) -> impl Iterator<Item = &'a mut T>

Returns an iterator over the mutable items of the list.

fn into_iter(self) -> impl Iterator<Item = T>

Returns an iterator that consumes the list.

fn push(&mut self, payload: T)

Adds a new node to the end of the list.

Efficiency: O(1)

fn pop_back(&mut self) -> Option<T>

Removes a node from the end of the list and returns its payload value.

Efficiency: O(n)

fn pop_front(&mut self) -> Option<T>

Removes a node from the front of the list and returns its payload value.

Efficiency: O(1)

fn remove(&mut self, index: usize) -> Result<T>

Removes a node from the specified location in the list. Error returns, if the index out of bounds.

Efficiency: O(n)

fn is_empty(&self) -> bool

Checks if the list is empty.

fn get(&self, index: usize) -> Result<&'a T>

Returns a list item by index, or error if index out of bounds.

fn get_mut(&mut self, index: usize) -> Result<&'a mut T>

Returns a mutable list item by index, or error if index out of bounds.

fn clear(&mut self)

Removes all items from the list.

fn find(&self, value: &T) -> Option<usize>

where T: PartialEq<T>,

Finds the first node whose payload is equal to the given value and returns its index. Returns None if there is no such node.