因此，我的 comp sci 课程中的一个主题是关于时间复杂性，以及使用数组和链表作为比较某些操作的好方法以及哪种容器更擅长这样做，因此您可以选择适当的数据结构。我了解大多数操作背后的原因，但我不确定其中一个操作是在数组中插入和追加。
这两种情况的最坏情况是 O(n)。我相信我理解为什么插入是 O(n)，因为最坏的情况是，您在前面插入会导致您将所有元素移到正确的位置，这意味着它是线性的并且取决于数组中元素的数量。对于追加，我很好奇为什么它不是 O(1)，因为考虑到空间，无论大小如何，在最后添加一个元素都需要一次操作。
这就是问题所在，如果没有足够的空间，您必须将阵列复制到更大的阵列以应对最坏的情况？
[...] 如果没有足够的空间，您必须将数组复制到更大的数组以应对最坏的情况？
答对了。
典型的数组是一块具有确定大小的连续内存，该大小在编译或运行时确定。没有将元素删除或插入数组这样的事情，而只是简单地写入已经分配的内存。
链表是内存块的非连续集合，它们通过它们的地址连接。有这样的事情，例如将元素删除和插入到链表中。
数组相对于链表的好处是更容易遍历和紧凑（不需要额外的内存来存储下一个 [或前一个] 元素的地址）。但是，与链表不同，这不能轻易扩展。
然而，为了更准确地讨论数据结构固有的算法的时间复杂性，我们需要首先定义数据结构。
双向链表？我们是否存储第一个和最后一个元素的地址（如队列）？二叉树（这是一种链表）？