在数组末尾插入元素和在链表中插入元素，哪个更快？

Question

哪个更快——在数组末尾插入元素还是在链表中？

- Praveen Kishor

---

你所说的数组是指 ArrayList 还是实际的 Array？因为向数组中任何位置添加元素的速度是相同的，但它无法变得更长。 - Richard Tingle

重点在于：细微的细节很重要。因此，您可能希望更新您的问题以确保非常精确。您还需要查看：https://dev59.com/P3RB5IYBdhLWcg3wpotm - GhostCat

可能是以下问题的重复：Java ArrayList vs LinkedList 的性能比较，仅涉及创建/插入和排序，Java ArrayList 和 LinkedList - 在末尾添加元素的实现细节，何时使用 LinkedList 而不是 ArrayList？，ArrayList vs LinkedList Java，java linkedlist 添加元素时比 arraylist 慢？。 - Basil Bourque

Answer 1

我猜你说“数组”时可能是指ArrayList，因为在Java中，你不能往已满的数组里“添加”。

首先，如果你要“在结尾插入”，实际上你是在结尾追加，而不是“插入”。这一区别很重要，因为在ArrayList的任意位置执行“插入”操作的时间复杂度是O(n)，因为必须将右侧的所有元素都“移动”一位以留出插入元素的位置。

向（双向）LinkedList添加始终是一个O(1)（常数时间）操作。

向ArrayList添加通常是一个O(1)操作，但如果支撑数组已满，则可能是一个O(n)操作，因为必须分配新数组并复制每个元素。在数组未满的一般情况下，ArrayList的性能比LinkedList（稍微）快，但差距非常小。

它们的平摊成本相同，但如果需要每次都是恒定时间，只有LinkedList可以做到。

- Bohemian

---

回答问题，如果在数组的“末尾”添加元素，当索引值>=数组长度或<0时会导致IndexOutOfBoundsException异常，否则时间复杂度为O(1)。 - Lew Bloch

我猜你说的“array”是指ArrayList，因为在Java中你不能向一个满的数组中“添加”元素。谁说它已经满了？ - Michael

Answer 2

将元素添加到Array的末尾比将元素添加到LinkedList中更快，因为将元素添加到LinkedList中始终意味着在列表末尾创建一个单元格，然后向其中添加值。在数组中，您只需向现有单元格添加值即可。但是，在Array中，如果已满且没有空间，则会出现IndexOutOfBoundsException，而在LinkedList中，您永远不会遇到此问题，因为列表将根据您的需求不断增长。此外，LinkedList和ArrayList之间存在明显的区别，ArrayList具有随机访问功能，这意味着对任何元素的访问始终为O（1），而在LinkedList中，它始终是顺序访问，这意味着访问时间将根据索引而异，并且在最坏的情况下为O（n）。但是，将元素附加到LinkedList始终为O（1），但在ArrayList中不是这样。如果ArrayList未满，则为O（1），但如果已满，则首先会增加一个以上的单元格，然后才会添加该值，因此最坏的情况是O（n）。

- Michael Gantman