从未排序的链表中删除元素后维护元素顺序

Question

我对于未排序的链表中的一个具体问题感到好奇。假设我们有一个基于数组实现的未排序的链表。在从列表中删除元素时，保留当前元素顺序是否重要或者具有优势呢？那个空洞必须要填充，所以我们可以把列表中的最后一个元素取出来并插入到那个空洞中。是将所有元素移动到另外的位置的时间复杂度大于只移动单个元素吗？

- sunnlamp

---

你能澄清一下“基于数组实现的未排序链表”是什么意思吗？LinkedList和ArrayList是List的不同实现。给出一个通用的答案：这取决于你想要它做什么，只要在添加/删除对象时说明如何保持顺序即可。 - Emz

抱歉，你是对的。ArrayUnsortedList 是我应该指定的内容。我仍在学习如何适当地提出问题。 - sunnlamp

Answer 1

你可以在不留下空洞的情况下从链表中删除一个元素。

链表不是由连续元素的数组表示的。相反，它是一条带有链接的元素链。你可以仅通过将其相邻的元素链接到彼此来删除一个元素，这是一个常数时间操作。

现在，如果你有一个基于数组的列表，你可以选择通过将最后一个元素移动到位置来实现元素的删除。这将为你提供O(1)的删除而不是O(n)的删除。然而，你需要记录这种行为。

引用：

"将所有元素移动的时间复杂度是否大于移动单个元素的时间复杂度？"

对于基于数组的列表来说是的。移动所有后续元素的时间复杂度是O(n)，而移动单个元素的时间复杂度是O(1)。

java.util.List

如果你的列表是 java.util.List 的实现，注意 Java List 被定义为一个 有序 集合，而 List.remove(int index) 方法被定义为移除剩余元素。

- Andy Thomas

---

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - sunnlamp

对于所有大小为n的数组，如果您想通过将它们从一个数组索引复制到另一个来移动最多n个元素，则需要最多n次复制操作，使复杂度为O(n)。您可以将数组视为粘在一起的一排盒子。您无法移动盒子，但可以移动内容。假设您想要从倒数第二个盒子中删除其中一个项目，并且没有空盒子。您可以在单个操作中从最后一个盒子中移动该项目。但是，如果您移动所有其他盒子中的项目，则执行此操作所需的时间将与盒子数量成比例，最坏情况下为O(n)。 - Andy Thomas

谢谢，这实际上帮助我更好地理解了它。 - sunnlamp

Answer 2

是的，使用数组实现时，如果要移动所有元素以便插入新元素，则时间复杂度会更大，最多达到n/2（如果该元素在数组中间）。而移动一个元素则是常数时间。

- Lencalot

Answer 3

由于您正在使用数组，答案是肯定的，因为您需要进行多次赋值。

如果您使用了节点，从复杂性的角度来看会更好。

- MrBlueSky