0

编辑：哇，我很抱歉....我以某种方式混淆了第二张图中的 LinkedList 和 ArrayList 列>_>我睡得不多....对不起...至少一个答案确实对我有所帮助方式，有详细的解释，所以这篇文章不是完全浪费......

我确实找到了一些关于此的主题，但帖子中存在矛盾，所以我想确认谁是正确的。

这个主题是我发现的： When to use LinkedList over ArrayList?

投票最多的答案是：

"对于链表

  • 得到是 O(n)
  • 添加是 O(1)
  • 删除是 O(n)
  • Iterator.remove 是 O(1)

对于数组列表

  • 得到是 O(1)
  • add 是 O(1) 摊销，但 O(n) 最坏情况，因为必须调整数组大小和复制
  • 删除是 O(n)"

但后来有人在这里发布了一个链接，上面写着： http:
//leepoint.net/notes-java/algorithms/big-oh/bigoh.html

Algorithm     ArrayList   LinkedList
access front     O(1)         O(1)
access back      O(1)         O(1)
access middle    O(1)         O(N)
insert at front  O(N)         O(1)
insert at back   O(1)         O(1)
insert in middle O(N)         O(1)
4

1 回答 1

0

There is no contradiction between the two sources cited in the question.

First a few thoughts about LinkedLists: In a linked list, we need to move a pointer through the list to get access to any particular element to either delete it, examine it, or insert a new element before it. Since the java.util.LinkedList implementation contains a reference to the front and back of the list, we have immediate accesss to the front and back of the list and this explains why any operation involving the front or back of the list is O(1). If an operation is done using an Iterator, then the pointer is already where you need it to be. So to remove an element from the middle takes O(n) time, but if the Iterator already spent O(n) operations getting to the middle, then iter.remove() can execute in O(1).

Now conisider ArrayList: Under the hood, ArrayList stores data in a primitive array. So while we can access any element in O(1) time, adding or removing an element will require that the entire array be shifted down by one element and this takes O(n) time. If we are adding or removing the last element, this does not require any shifting, so this can run in O(1).

This means that calling list.add(newItem) takes O(1), but occasionally there is no room at the end of the list, so the entire list needs to be copied into new memory before ArrayList can perform the add. However, since every time ArrayList resizes itself it doubles the previous capacity, this copy operation only happens log2 n times when adding n elements. So we still say that add runs in O(1) time. If you know how many elements you will be adding when the ArrayList is created, you can give it an initial capacity to improve performance by avoiding the copy operation.

于 2013-04-03T15:06:43.397 回答