arraylist - 基于数组的列表的插入操作分析（游标实现）

Question

因此，我正在为明天的算法分析考试而学习，并且正在阅读讲师的笔记和示例。只有一件事我不明白，就是这个问题：

问题：在基于数组的列表（游标实现）中的给定元素之后插入一个元素需要最坏的情况时间：

答案：O(1)

就个人而言，我认为最坏的情况是光标位于列表的开头，因此在插入新元素之前必须将数组中的 N-1 项复制到下一个位置，因此它是 O(N)在最坏的情况下运行。

但是，当被问到这是不是笔误时，教练说不是。

这背后的原因是什么？对于所有未来的回答者，感谢您的宝贵时间。

score 0 · Accepted Answer

假设我们必须插入元素“a”。好吧，它说给定一个元素，我们称之为'b'。这意味着您知道下一个元素是什么，我们称之为“c”。所以你所要做的就是将'a'的'next'元素设置为'c'。然后设置'b'的下一个元素等于'a'。此过程适用于任何元素。所以操作是常数时间。

score 0 · Accepted Answer

您可以使用数组来实现本质上是一个链表，其中数组中的每个元素都包含一个指向下一个元素索引的指针。

struct Element
{
    string item;
    int next;
}

给定元素 A，您可以在恒定时间内在 A 之后插入一个新元素 B。

int indexOfA = ..
int indexOfB = (next free index)
B.next = A.next;
A.next = indexOfB;

2 回答 2