Struct SkipLinkedList

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

SkipLinkedList

SkipLinkedList is a skiplist-backed linked-list that supports fast random access. The (amortized) time complexity is O(log n) for both reads and writes, regardless of the position. It is more efficient than Vec and Linkedlist for large list that requires lots of random access.

Examples

let mut list = skip_linked_list::SkipLinkedList::new();

list.push_front(1);
list.push_back(2);
list.insert(1, 3);
list.insert(1, 4);
list.insert(1, 5);
// current list is: [1, 5, 4, 3, 2]

assert_eq!(list.get(1), Some(&5));
assert_eq!(list.get(3), Some(&3));
assert_eq!(list.remove(2), 4);

Implementations

impl<T> SkipLinkedList<T>

pub fn new() -> Self

Creates a new list.

pub fn insert(&mut self, i: usize, elem: T)

Inserts an element at position index within the list, shifting all elements after it to the right.

Examples

let mut list = skip_linked_list::SkipLinkedList::new();
list.insert(0, 10);
list.insert(1, 30);
list.insert(1, 20);
assert_eq!(list.into_iter().collect::<Vec<i32>>(), vec![10, 20, 30]);

Panics

Panics if i > len.

pub fn get(&self, i: usize) -> Option<&T>

Gets the element at position index within the list.

Examples

let mut list = skip_linked_list::SkipLinkedList::new();
list.insert(0, 10);
assert_eq!(list.get(0), Some(&10));
assert_eq!(list.get(1), None);

pub fn remove(&mut self, i: usize) -> T

Removes an element at position index within the list, shifting all elements after it to the left.

Examples

let mut list = skip_linked_list::SkipLinkedList::new();
list.insert(0, 10);
list.insert(1, 20);
assert_eq!(list.remove(0), 10);
assert_eq!(list.remove(0), 20);

Panics

Panics if i >= len.

pub fn len(&self) -> usize

Returns the length of the list.

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

Inserts an element at the start of the list.

pub fn push_back(&mut self, elem: T)

Inserts an element at the end of the list.

pub fn pop_front(&mut self) -> T

Removes an element at the start of the list.

Panics

Panics if list is empty.

pub fn pop_back(&mut self) -> T

Removes an element at the end of the list.

Panics

Panics if list is empty.

pub fn iter(&self) -> Iter<'_, T>

Returns an iterator over the list.

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Returns an mut iterator over the list.

pub fn into_iter(self) -> IntoIter<T>

Consumes the list into an iterator.

impl<T> SkipLinkedList<T>

where T: Display,

pub fn visualize(&self)

Prints the internals of the list.

Trait Implementations

impl<T> Drop for SkipLinkedList<T>

fn drop(&mut self)

Executes the destructor for this type.