The ArrayLinkedList data structure combines the benefit of an array and a linked list.

Every supported operation, which does not (re-)allocate the array, is done in O(1):

• inserting elements at the front and back
• popping element at the front or back
• getting the element count
• removing elements at an arbitrary index
• inserting elements at an arbitrary index
• replacing elements at an arbitrary index

It's stored like an array, but contains some additional information.

You would typically use it, where you need to be able to do multiple of the following tasks efficiently:

• accessing single elements by index
• adding and removing elements without changing order or indices
• sorting elements without changing indices or moving the content around.

Order and indexing

You might also use it as a more convenient version of a Vec<Option<T>>. When iterating over it, only the elements, which are Some are given to the user. And even the checks for Some are optimized away. So when it's likely, that most of the options of a large array are None, this might be a huge performance improvement.

Another advantage over a LinkedList is the cache locality. Everything is laid out in a contiguous region of memory. Compared to a Vec on the other hand, it might be bad. The iteration does not necessarily take place in the same order. That's mostly a problem for large arrays. The iterator would jump back and forth in the array.

In order to understand this type, it's necessary to know about the iteration order. There is a logical order, which is used by the iterators, or when doing anything with the first and last elements. You can think of it as the order of a linked list, which is just packed into an array here. And then there is indexing, which has nothing to do with the order of the linked list. The indices just return the array elements.

Index Example

So when adding an element to the linked array without specifying the index, you get the index, it was put to, as a result. The results are always added to the array in order, so the indices increase, no matter if you add the indices to the front or to the back:

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

assert_eq!(array.push_front(1), 0);
assert_eq!(array.push_back(2), 1);
assert_eq!(array.push_front(3), 2);
assert_eq!(array.push_front(4), 3);
assert_eq!(array.push_back(5), 4);

Order example

When you just apped elements from the front or back, the indices even correlate to the order:

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

array.push_front(1);
array.push_front(2);
array.push_front(3);

for (i, element) in array.iter().rev().enumerate() {
assert_eq!(*element, array[i].unwrap());
}

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

array.push_back(1);
array.push_back(2);
array.push_back(3);

for (i, element) in array.iter().enumerate() {
assert_eq!(*element, array[i].unwrap());
}

Iteration over unsorted lists

In realistic cases, you need to store the indices somewhere else, if you need them. Alternatively, you can also use

use array_linked_list::ArrayLinkedList;

let mut array = ArrayLinkedList::new();

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

for (index, element) in array.indexed().rev() {
assert_eq!(*element, array[index].unwrap());
}

Conclusion

Just remember, that indices and order are two different things, which don't correlate, and you should be safe.