c++ - 列表如何知道（有效地）在哪里插入却不能进行随机访问？

Question

我有点困惑。列表擅长在任何位置插入，但不擅长随机访问？

（怎么可能）如果你不能做随机访问，你怎么知道在哪里插入？

同样，如果您可以在任何位置插入，为什么不能有效地从该位置读取？

Answer 1

如果您已经有了要插入的列表节点，则插入只是分配一个列表节点并调整几个指针的问题。当然，如果您只知道要插入的索引，则缺少随机访问意味着您需要 O(n) 时间才能到达该节点，即使您只需要 O(1) 额外时间来插入之后到了那里。

Answer 2

我有点困惑。列表擅长在任何位置插入，但不擅长随机访问？

真的。但它（列表）在访问该位置后插入到该位置。访问顺序为 O(n)，插入顺序为 O(1)。

如果你不能做随机访问，你怎么知道在哪里插入？

它只是插入特定位置，开始、结束或迭代器指示的位置。

如果您可以在任何位置插入，为什么不能从该位置有效地读取？

它可以在顺序访问后插入到任何位置。

Answer 3

如果您必须寻找列表，则列表不适合在任何位置插入。它们可以快速将东西放在前面（如果你缓存它，则结束），并且在中间有一个已经找到的迭代器，插入速度很快。所以，你没有困惑，你只是误解了你被告知的内容。

Answer 4

链表

列表使用指向元素的指针进行操作——它们在内存中可以是不连续的（不是按顺序排列的）。

因此，例如，单链表将包含如下指针：

head -> element1 -> element2 -> element3 -> NULL
 ^ cur ptr

每个元素都可以定义为一个结构：

struct Element {
    Element *next;
    int data;
};

*next 指针指向列表中的下一个元素。

因此，要遍历列表到例如最后一个元素，您需要执行以下操作：

while (*curNode->next != NULL) {
    *curNode = curNode->next;
}
// curNode after traversing would be last node
curNode->data; // get data in last node

遍历后指向最后一个元素的指针如下所示：

head -> element1 -> element2 -> element3 -> NULL
                                    ^ cur ptr (3 hops)

因此，您需要进行 n 跳才能到达最后一个节点（除非您有指向最后一个元素的指针，也就是“尾”指针。）

要在某个位置插入，您需要遍历元素直到找到正确的插槽。在所描述的单链表中，它将是 O(n)。

您可以根据需要使用其他类型的列表（例如双向链表等）来改善列表的遍历时间。但请注意，连接这些列表可能会更复杂。

VS 数组/STL 向量：

数据在内存中是连续的。因此，要访问它，您可以简单地获取第一个元素的地址 + 索引以进行迭代，并取消引用该位置。因此，您可以随机即时访问。在这种情况下，复杂度将因此为 O(1)。