Struct array_linked_list::ArrayLinkedList

pub struct ArrayLinkedList<T> { /* fields omitted */ }

The ArrayLinkedList type, which combines the advantages of dynamic arrays and linked lists.

Implementations

impl<T> ArrayLinkedList<T>

pub fn new() -> Self

Constructs a new, empty ArrayLinkedList.

The linked array will not allocate until elements are pushed onto it.

pub fn with_capacity(capacity: usize) -> Self

Constructs a new, empty ArrayLinkedList<T> with the specified capacity.

The array will be able to hold exactly capacity elements without reallocating.

pub fn push_front(&mut self, value: T) -> usize

Adds an element at the front of the array and returns its index. The indices are returned in a raising order, starting with zero. See the module description for more information.

This operation should compute in O(1) time.

Examples

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

assert_eq!(array.push_front(2), 0);
assert_eq!(array.front().unwrap(), &2);

assert_eq!(array.push_front(1), 1);
assert_eq!(array.front().unwrap(), &1);

pub fn push_back(&mut self, value: T) -> usize

Adds an element at the back of the array and returns its index. The indices are returned in a raising order, starting with zero. See the module description for more information.

This operation should compute in O(1) time.

Examples

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

assert_eq!(array.push_back(1), 0);
assert_eq!(array.push_back(3), 1);
assert_eq!(3, *array.back().unwrap());

pub fn insert_after(&mut self, prev_index: usize, value: T) -> Option<usize>

Inserts an element after the element at the specified index. Returns the index of the inserted element on success. If no element was found at the specified index, None is returned.

Panics

Panics if prev_index >= capacity

Examples

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

let first = array.push_back(1);
let second = array.push_back(2);
let third = array.push_back(3);

array.insert_after(second, 100);

assert_eq!(array.pop_front(), Some(1));
assert_eq!(array.pop_front(), Some(2));
assert_eq!(array.pop_front(), Some(100));
assert_eq!(array.pop_front(), Some(3));
assert_eq!(array.pop_front(), None);

pub fn insert_before(&mut self, next_index: usize, value: T) -> Option<usize>

Inserts an element before the element at the specified index. Returns the index of the inserted element on success. If no element was found at the specified index, None is returned.

Panics

Panics if next_index >= capacity

Examples

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

let first = array.push_back(1);
let second = array.push_back(2);
let third = array.push_back(3);

array.insert_before(second, 100);

assert_eq!(array.pop_front(), Some(1));
assert_eq!(array.pop_front(), Some(100));
assert_eq!(array.pop_front(), Some(2));
assert_eq!(array.pop_front(), Some(3));
assert_eq!(array.pop_front(), None);

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

Removes the element at the given index and returns it, or None if it is empty. The indices of other items are not changed. Indices, which have never been used (see capacity), will not be available, but panic instead.

Indices are not the position they appear in, when iterating over them. So you can’t use enumerate to get the index to delete. But the iteration order of the elements (in both directions) is preserved. See the module description for more information.

This operation should compute in O(1) time.

Panics

Panics if index >= capacity

Examples

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

let first = array.push_front(1);
let second = array.push_back(2);
let third = array.push_front(3);


assert_eq!(array.len(), 3);

assert_eq!(array.remove(second).unwrap(), 2);
assert_eq!(array[second], None);
assert_eq!(array.len(), 2);
assert_eq!(array.remove(second), None);
assert_eq!(array.len(), 2);

assert_eq!(array.remove(first).unwrap(), 1);
assert_eq!(array.len(), 1);
assert_eq!(array.remove(third).unwrap(), 3);
assert_eq!(array.len(), 0);
assert!(array.is_empty());

pub fn replace_front(&mut self, index: usize, value: T) -> Option<T>

Adds element at specified index at the front of the list. Useful for updating contents.

It basically does the same as remove and push_back, even if the specified index is already removed.

Panics

Panics if index >= capacity

Examples

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

array.push_front(1);
let first_index = array.push_back(2);
array.push_front(3);
let second_index = array.push_front(4);
array.push_back(5);

let mut array2 = array.clone();
assert_eq!(array, array2);

let first_element = array.replace_front(first_index, 100);
let first_element2 = array2.remove(first_index);
array2.push_front(100);
assert_eq!(first_element, first_element2);
assert_eq!(array, array2);

let second_element = array.replace_front(first_index, 0);
let second_element2 = array2.remove(first_index);
array2.push_back(0);
assert_eq!(second_element, second_element2);
assert_ne!(array, array2);

assert_eq!(array.len(), 5);
assert_eq!(array2.len(), 5);

pub fn replace_back(&mut self, index: usize, value: T) -> Option<T>

Adds element at specified index at the front of the list. Useful for updating contents.

It basically does the same as remove and push_back, even if the specified index is already removed.

Panics

Panics if index >= capacity

Examples

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

array.push_front(1);
array.push_back(2);
let middle_index = array.push_back(3);
array.push_front(4);
array.push_back(5);

let mut array2 = array.clone();
assert_eq!(array, array2);

let element = array.replace_back(middle_index, 100);
let element2 = array2.remove(middle_index);
array2.push_back(100);
assert_eq!(element, element2);
assert_eq!(array, array2);

assert_eq!(array.len(), 5);
assert_eq!(array2.len(), 5);

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

Removes the first element from the array and returns it, or None if it is empty.

This operation should compute in O(1) time.

Examples

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();
assert_eq!(array.pop_front(), None);
array.push_back(1);
array.push_back(3);
assert_eq!(array.pop_front(), Some(1));

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

Removes the last element from the array and returns it, or None if it is empty.

This operation should compute in O(1) time.

Examples

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();
assert_eq!(array.pop_back(), None);
array.push_back(1);
array.push_back(3);
assert_eq!(array.pop_back(), Some(3));

pub fn front_index(&self) -> Option<usize>

The index of the first list element. Returns None if array is empty.

pub fn back_index(&self) -> Option<usize>

The index of the last list element. Returns None if array is empty.

pub fn front(&self) -> Option<&T>

The first list element. Returns None if array is empty.

pub fn back(&self) -> Option<&T>

The last list element. Returns None if array is empty.

pub fn front_mut(&mut self) -> Option<&mut T>

The first list element as a mutable reference. Returns None if array is empty.

pub fn back_mut(&mut self) -> Option<&mut T>

The last list element as a mutable reference. Returns None if array is empty.

pub fn is_empty(&self) -> bool

Checks if the list is empty.

pub fn clear(&mut self)

Clears the linked array, removing all values.

Note that this method has no effect on the allocated capacity of the array. So all indices, which have already been used (see capacity), are still available.

pub fn len(&self) -> usize

Returns the number of elements in the linked array.

pub fn capacity(&self) -> usize

Returns the number of elements the vector can hold without reallocating.

Methods, which take indices, require the specified index to be below the capacity.

All the following methods require indices:

• insert_before
• insert_after
• remove
• replace_front
• replace_back

Besides that, some of the iterators are constructed using indices in the same range.

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

Returns a borrowing iterator over its elements.

pub fn indexed<'a>(
    &'a self
) -> impl Iterator<Item = (usize, &'a T)> + DoubleEndedIterator

Returns a borrowing iterator over its indexed elements.

pub fn indices<'a>(
    &'a self
) -> impl Iterator<Item = usize> + DoubleEndedIterator + 'a

Returns a borrowing iterator over its indices.

pub fn iter_after<'a>(
    &'a self,
    index: usize
) -> impl Iterator<Item = &'a T> + DoubleEndedIterator

Returns a borrowing iterator over its elements, starting after the element at the specified index.

Panics

Panics if index >= capacity

pub fn indexed_after<'a>(
    &'a self,
    index: usize
) -> impl Iterator<Item = (usize, &'a T)> + DoubleEndedIterator

Returns a borrowing iterator over its indexed elements, starting after the element at the specified index.

Panics

Panics if index >= capacity

pub fn indices_after<'a>(
    &'a self,
    index: usize
) -> impl Iterator<Item = usize> + DoubleEndedIterator + 'a

Returns a borrowing iterator over its indices, starting after the element at the specified index.

Panics

Panics if index >= capacity

pub fn iter_before<'a>(
    &'a self,
    index: usize
) -> impl Iterator<Item = &'a T> + DoubleEndedIterator

Returns a borrowing iterator over its elements, ending before the element at the specified index.

Panics

Panics if index >= capacity

pub fn indexed_before<'a>(
    &'a self,
    index: usize
) -> impl Iterator<Item = (usize, &'a T)> + DoubleEndedIterator

Returns a borrowing iterator over its indexed elements, ending before the element at the specified index.

Panics

Panics if index >= capacity

pub fn indices_before<'a>(
    &'a self,
    index: usize
) -> impl Iterator<Item = usize> + DoubleEndedIterator + 'a

Returns a borrowing iterator over its indices, ending before the element at the specified index.

Panics

Panics if index >= capacity

pub fn into_indexed(
    self
) -> impl Iterator<Item = (usize, T)> + DoubleEndedIterator

Returns an owning iterator returning its indexed elements.

pub fn into_indices(self) -> impl Iterator<Item = usize> + DoubleEndedIterator

Returns an owning iterator returning its indices.

Trait Implementations

impl<T: Clone> Clone for ArrayLinkedList<T>

fn clone(&self) -> ArrayLinkedList<T>

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for ArrayLinkedList<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Index<usize> for ArrayLinkedList<T>

type Output = Option<T>

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for ArrayLinkedList<T>

fn index_mut(&mut self, index: usize) -> &mut Option<T>

Performs the mutable indexing (container[index]) operation.

impl<'a, T> IntoIterator for &'a ArrayLinkedList<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Values<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for ArrayLinkedList<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoValues<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq<ArrayLinkedList<T>> for ArrayLinkedList<T>

fn eq(&self, other: &ArrayLinkedList<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &ArrayLinkedList<T>) -> bool

This method tests for !=.

impl<T> StructuralPartialEq for ArrayLinkedList<T>