Java ArrayList 和 LinkedList - 在最后实现细节添加元素 [英] Java ArrayList and LinkedList - adding element at end implementation details

问题描述

我对为什么 arraylist 比链表更快的理解是，对于 arraylist，您基本上只需要一个操作 - 更新数组末尾元素的引用，而对于链表，您必须做更多的事情，例如创建一个新节点，更新 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 是如何实现这些的.arraylist 如何知道最后一个"元素在哪里，它是存储最后一个元素的值还是遍历数组并在最后一个元素之后添加一个新元素?

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?

推荐答案

看源码:

ArrayList:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}      

LinkedList:

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屋！