Java ArrayList和LinkedList-在最终实现细节中添加元素 [英] Java ArrayList and LinkedList - adding element at end implementation details
问题描述
我对为什么arraylist比链表更快的理解是,使用arraylist基本上只需要执行一个操作-更新末尾array元素的引用,而使用链表则需要做更多的事情,例如创建一个新节点,更新2个引用,浏览链接列表并更新最后一个节点以指向新节点,等等.
My understanding of why arraylist is faster than a linkedlist is that with an arraylist you basically only need one action - update the reference at the end array element, whereas with a linked list you have to do much more e.g. create a new node, update 2 references, go through linked list and update the last node to point to the new one etc.
但是我不确定java如何实现这些.数组列表如何知道最后一个"元素在哪里,是存储最后一个元素的值还是遍历数组并在最后一个元素之后添加新元素?
However I am not sure how java implement these. How does the arraylist know where the "last" element is, does it store a value of the last element or does it traverse the array and add a new element after the last?
还有链接列表,它们是存储对列表中最后一个节点的引用,还是遍历整个列表直至结尾?
And linked lists, do they store a reference to the last node in the list, or do they traverse the entire list to get to the end?
推荐答案
查看源代码:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
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++;
}
这篇关于Java ArrayList和LinkedList-在最终实现细节中添加元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!