我读了THIS和
并了解LinkedList add(E element)是O(1)
和ArrayList add(E element)分摊为O(1),但最差情况为O(n),因为必须调整数组大小并复制
但是,当我尝试检查它时
public class ArrayListVSLinkeedList {
public ArrayListVSLinkeedList() {
final int COUNTER = 15000000;
List<Integer> arrayList = new ArrayList<Integer>();
long tStart_add = System.currentTimeMillis();
for (int i = 0; i < COUNTER; i++) {
arrayList.add(i);
}
long tEnd_add = System.currentTimeMillis();
long tDelta_add = tEnd_add - tStart_add;
System.out.println("Adding to ArrayList: " +tDelta_add);
List<Integer> linkedList = new LinkedList<Integer>();
tStart_add = System.currentTimeMillis();
for (int i = 0; i < COUNTER; i++) {
linkedList.add(i);
}
tEnd_add = System.currentTimeMillis();
tDelta_add = tEnd_add - tStart_add;
System.out.println("Adding to LinkedList: " +tDelta_add);
}
public static void main(String[] args) {
new ArrayListVSLinkeedList();
}
}
我收到输出:
添加到ArrayList: 9122
添加到链接列表: 19859
我知道,这不是真正的基准,但是...
最后,将元素添加到ArrayList的末尾要比LinkedList快。为什么会这样?
最佳答案
这仅仅是由于实施。
看看ArrayList.add
的实现:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
ArrayList
在内部保存一个数组,该数组的元素是对该列表所管理的对象的引用。方法ensureCapacityInternal
仅检查此内部数组是否仍然足够大以添加另一个元素。如果是这样,则添加该元素,然后该方法返回。这非常快(并且-btw-是O(1))。
如果该数组已满,则将分配一个更大的新数组,每个引用都将从旧数组复制到新数组。之后,将添加该元素。这当然是O(n)。但是这种情况很少发生,并且由于调整大小策略(将大小增加一倍),这种情况将越来越少。
另一方面,让我们看一下
LinkedList.add
的实现:public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
在这里,您看到为每个添加的元素必须创建一个新的节点对象,然后将其添加为最后一个元素。没有调整大小,因此该方法始终为O(1),但是创建节点对象要比简单地存储引用花费更多的时间。