Struct List

Source

pub struct List<E: Clone + Sized> { /* private fields */ }

Expand description

A persistent (immutable) stack/list data structure.

List is implemented as a singly-linked list with structural sharing, making it efficient for stack-like operations. All operations return a new list, leaving the original unchanged.

§Performance

push: O(1)
pop: O(1)
top: O(1)
len: O(1) - length is cached
rev: O(n)
to_vec: O(n)

Implementations§

Source §

impl<E: Clone + Sized> List<E>

Source

pub fn empty() -> Self

Creates a new empty list.

§Examples

use pfds::List;
 
let list: List<i32> = List::empty();
assert!(list.is_empty());
assert_eq!(list.len(), 0);

Source

pub fn push(&self, e: E) -> Self

Creates a new list with the given element added to the front (top).

This operation is O(1) and shares structure with the original list.

§Arguments

e - The element to add to the front of the list

§Examples

use pfds::List;
 
let list = List::empty().push(1).push(2).push(3);
assert_eq!(list.len(), 3);
assert_eq!(*list.top(), 3); // Last pushed element is at the top

Source

pub fn pop(&self) -> Self

Creates a new list with the top element removed.

This operation is O(1) and shares structure with the original list.

§Panics

Panics if the list is empty.

§Examples

use pfds::List;
 
let list = List::empty().push(1).push(2);
let list2 = list.pop();
assert_eq!(list.len(), 2);  // Original unchanged
assert_eq!(list2.len(), 1);
assert_eq!(*list2.top(), 1);

Source

pub fn top(&self) -> &E

Returns a reference to the top element of the list.

This operation is O(1).

§Panics

Panics if the list is empty.

§Examples

use pfds::List;
 
let list = List::empty().push(42);
assert_eq!(*list.top(), 42);

Source

pub fn is_empty(&self) -> bool

Returns true if the list is empty.

This operation is O(1).

§Examples

use pfds::List;
 
let empty = List::<i32>::empty();
assert!(empty.is_empty());
 
let non_empty = empty.push(1);
assert!(!non_empty.is_empty());

Source

pub fn len(&self) -> usize

Returns the number of elements in the list.

This operation is O(1) as the length is cached.

§Examples

use pfds::List;
 
let list = List::empty().push(1).push(2).push(3);
assert_eq!(list.len(), 3);

Source

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

Converts the list to a vector.

Elements are returned with the top element first. This operation is O(n).

§Examples

use pfds::List;
 
let list = List::empty().push(1).push(2).push(3);
let vec = list.to_vec();
assert_eq!(vec, vec![3, 2, 1]); // Top element (3) is first

Source

pub fn rev(&self) -> List<E>

Creates a new list that is the reverse of the current list.

This operation is O(n).

§Examples

use pfds::List;
 
let list = List::empty().push(1).push(2).push(3);
let reversed = list.rev();
assert_eq!(reversed.to_vec(), vec![1, 2, 3]);

Source

pub fn iter<'a>(&self) -> Iter<'a, E> ⓘ

Returns an iterator over the list elements.

The iterator yields elements from top to bottom.

§Examples

use pfds::List;
 
let list = List::empty().push(1).push(2).push(3);
let collected: Vec<_> = list.iter().collect();
assert_eq!(collected, vec![3, 2, 1]);