问为什么无序链接列表？对于无序结构来说，这是数组/11特性的良好平衡吗？

EN

如果这被认为是非主题的话，我很抱歉，尽管我希望数据结构的设计与这里发布的编程实践有足够的相关性。

我正在学习C和C++，并且已经讨论了数组和内存分配，我们开始研究链接列表。讲师指出了它们的优点，主要是能够在不复制整个结构的情况下添加/删除节点--我可以看到，为了将节点添加到数组中，我们需要空闲内存的existing_array_size + node_size，尽管我们随后将删除整个existing_array_size。即使删除一个条目，我们也可能希望再次复制整个结构。

使用链接列表，我们支付执行时间的代价(通过遍历潜在的n节点来查找和删除一个节点)，以提高内存的效率。

val of ll0
ptr to ll1
...
val of ll1
ptr to ll2
...
...
val of lln
null ptr

一切都很好。然而，我突然想到(可能是因为对它完全陌生，没有正确理解，请原谅我)，我们为n+1点浪费了大量的记忆(我预计会争论这是否真的是‘浪费’。该方法是必要的，但不包含任何实际价值的内容)。

对于我来说更明显的结构是，特别是无序列表的，如下所示，以一个ptr to start为例

(start) ptr to end
val of 0
val of 1
...
val of n
(end) null ptr

到目前为止，这只是一个数组..。让我们删除一个值：

(start) ptr to end
val of 0
val of 1
...
(deleted0) val of m (= null)
...
val of n
(end) ptr to deleted0

现在插入一个值x

(start) ptr to end
val of 0
val of 1
...
val of m (= x)
...
val of n
(end) null ptr

我现在只看到一个问题，当我键入它时，如果我们需要插入而没有删除，或者必须保留多个指向删除的指针，如果它在end下面，则不能允许我们覆盖内存中的其他项。

那么，在这种情况下，为什么不像一个链表那样，把整个结构作为一个“节点”呢？删除2项：

(start) ptr to end
val of 0
val of 1
...
val of m (= x)
...
(deleted0) val of a (= null)
...
(deleted1) val of b (= null)
...
val of n
(end) ptr to start1
...
...
(start1) ptr to end1
(end1) ptr to deleted0
ptr to deleted1

好的，假设我们现在有一些空白，因为删除，但没有插入。也许我们想稍微清理一下，通过在start1结构中填充start2等来“收缩”是相当简单的。我想我们别无选择，只能再次复制它。

请注意，end不是' end '，而是值的末尾，我们在那里查找指向结构内空闲空间的指针。

• 在避免在insert/delete上复制时，这与链接列表相比具有相同的优势。
• 内部的“空闲”空间不会被释放给其他变量，但我们可以认为这是一种结构的成本，可以与(但在所有情况下都要小得多，除了最坏的情况)相比，比链接列表要小得多。
• 插入所需的指令与链接列表中的指令一样少。
• 删除所需的时间比11少一个。
• 内存中的大小大于数组，但小于链接列表*。
• 从不完全复制，所需的最大空间趋向于大的n，并且与num_insertions/num_deletions成正比。

*“最坏的情况”是删除所有其他元素时，我们实际上有一个链接列表，其中所有指针都在末尾。

在开始愤怒地打字之前，你可能不会费心看这么远：

，那么我的问题是什么？！

简单:这个想法有什么问题(当然，除非使用了非常类似的东西，在这种情况下--它叫什么？)--我们是否总是清楚地知道我们是想要插入/删除的速度，还是要节省内存中的通常空间，所以这是多余的吗？

谢谢，很抱歉这篇文章太长了，我觉得这需要几个例子来说明。