Java ArrayList and LinkedList - adding element at end implementation details

Question

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.

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?

The JDK comes with the sources. Read them, and you'll find out. — JB Nizet
– JB Nizet, Commented Jan 24, 2013 at 8:17

jlordo · Accepted Answer · 2013-01-24 08:18:59Z

2

Look at the source:

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++;
}

answered Jan 24, 2013 at 8:18

jlordo

37.9k7 gold badges63 silver badges84 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Roland · Accepted Answer · 2013-01-24 08:33:06Z

1

An array-list is only faster at certain operations. If you add an element in the middle of an array the arraylist needs to copy basically all data into a new array. It is only if the arraylist already have allocated room for new data it is fast when inserting data where it is empty (usually in the end). Read/update by index is very-fast.

A LinkedList is fast when inserting since it never require the whole array to be copied. But accessing data in a linked list is slow since you need to "walk" all the elements until you are at the element you want to find.

answered Jan 24, 2013 at 8:33

Roland

5,46810 gold badges40 silver badges61 bronze badges

Comments

Andremoniy · Accepted Answer · 2013-01-24 08:18:34Z

0

You can always look at the sources of java.* classes.

However, answering particular your question: there is int field in ArrayList class, which contains current size of filled internal array area. When you add new value in ArrayList object, this field increments and then directly addresses to that element in internal array.

answered Jan 24, 2013 at 8:18

Andremoniy

35.2k25 gold badges143 silver badges259 bronze badges

Collectives™ on Stack Overflow

Java ArrayList and LinkedList - adding element at end implementation details

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related