ArrayLinkedList 数据结构结合了数组和链表的优点。

所有不支持（重新）分配数组的操作都在 O(1) 时间内完成

• 在前后插入元素
• 从前或后弹出元素
• 获取元素数量
• 在任意索引处删除元素
• 在任意索引处插入元素
• 在任意索引处替换元素

它像数组一样存储，但包含一些额外信息。

您通常会在需要高效执行以下多个任务的情况下使用它

• 通过索引访问单个元素
• 添加和删除元素而不改变顺序或索引
• 排序元素而不改变索引或移动内容。

顺序和索引

您也可以将其用作 Vec<Option<T>> 的更方便版本。在迭代时，只有 Some 的元素才传递给用户。甚至 Some 的检查也被优化掉了。因此，当大多数大数组选项可能是 None 时，这可能是一个巨大的性能提升。

与 LinkedList 相比，另一个优点是缓存局部性。所有内容都布局在内存的连续区域中。与另一个 Vec 相比，这可能不好。迭代不一定按相同的顺序进行。这主要是一个大数组的问题。迭代器会在数组中来回跳跃。

为了理解此类型，有必要了解迭代顺序。存在一个逻辑顺序，用于迭代器或对第一个和最后一个元素执行任何操作。您可以将其视为链表的顺序，这里只是打包到数组中。然后是索引，它与链表的顺序无关。索引只是返回数组元素。

索引示例

因此，在将元素添加到未指定索引的链表数组中时，您将获得放置元素的索引作为结果。结果总是按顺序添加到数组中，因此索引增加，无论您是在前面还是后面添加索引

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

顺序示例

当您只是从前或后添加元素时，索引甚至与顺序相关联

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

对未排序列表进行迭代

在实际情况下，如果您需要索引，则需要将其存储在其他地方。或者，您也可以使用

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

结论

请记住，索引和顺序是两回事，它们不相关，您可以放心。