Struct ArrayLinkedList

Source

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

Expand description

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

Implementations§

Source §

impl<T> ArrayLinkedList<T>

Source

pub fn new() -> Self

Constructs a new, empty ArrayLinkedList.

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

Source

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.

Source

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);

Source

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());

Source

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);

Source

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);

Source

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());

Source

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();
for (a, b) in array.iter().zip(&array2) {
    assert_eq!(a, b)
}

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);
for (a, b) in array.iter().zip(&array2) {
    assert_eq!(a, b)
}

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!(array.iter().zip(&array2).any(|(a, b)| a != b));

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

Source

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();
for (a, b) in array.iter().zip(&array2) {
    assert_eq!(a, b)
}

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

assert_eq!(element, element2);
for (a, b) in array.iter().zip(&array2) {
    assert_eq!(a, b)
}

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

Source

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));

Source

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));

Source

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

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

Source

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

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

Source

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

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

Source

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

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

Source

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

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

Source

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

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

Source

pub fn is_empty(&self) -> bool

Checks if the list is empty.

Source

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.

Source