The labs on this site need JavaScript to run. The same content is written out below.

Learn › Java › Collections

ArrayList and LinkedList

The same operation takes a different amount of work

An ArrayList stores its elements next to each other in a single array, and a LinkedList creates a node for each element and links each node to the ones before and after it. Try getting, inserting, and removing at different positions, and you see that one does its work shifting elements and the other does its work following nodes.

Checked against real execution · Checked against the internal array of a real ArrayList on JDK 21

Concepts in this lab

ArrayList

This is a list that keeps an array inside and moves the elements to a larger array when the array is full. Access to an element by index is fast at O(1), and adding at the end is also O(1) amortized. Inserting or removing in the middle takes O(n), because the elements after that position must each be shifted by one position.

LinkedList

This is a list in which each element (node) is linked by pointing to the locations of the elements before and after it. If the position is already known, insertion and removal are O(1), but finding the nth element is O(n) because you must follow the links from the start. Each node needs extra memory and the nodes are scattered in memory, so real traversal performance is often worse than that of an array-based list.

Time complexity (big-O notation)

This notation shows how fast the number of operations of an algorithm grows as the input size n grows. O(1) means constant regardless of size, O(log n) means only one more step when the size doubles, O(n) means proportional to the size, and O(n²) means proportional to the square of the size. It is the basis for judging which approach holds up as the amount of data grows.

Amortized analysis

This method evaluates cost as an average: the total cost of a whole sequence of operations divided by the number of operations, even if an expensive operation occurs now and then. Adding at the end of an ArrayList causes an O(n) copy when the array is full, but that is rare, so the average cost per operation is O(1).

Try these

• Default settings — Insert at the beginning of an ArrayList. Every element is shifted one position to the right.
• The same insertion into a LinkedList — Only the links have to be changed. No element is shifted.
• Insert in the middle of a LinkedList — The insertion itself is fast, but the nodes have to be followed up to that position.
• Get from the middle of a LinkedList — It cannot go directly to an index, so it follows the nodes one by one.
• Get from the middle of an ArrayList — The element is accessed in one step, however many elements there are.
• Append 40 elements to an ArrayList — The elements are moved to a larger array only when the array is full. Look at the average cost.

Running with the default settings

1. add(0, 99): To store the element at index 0, that position has to be freed. From index 0 to the end, 10 elements have to be shifted.
2. The 10 elements were each copied one position to the right, and then 99 was stored at index 0, which is now empty.

Result of this run

• Inserting an element at the beginning of the ArrayList required shifting the 10 elements from that position on. The closer to the beginning and the more elements there are, the more there is to shift.

Code

List<Integer> list = new ArrayList<>();
// ... the list now holds 10 elements (indexes 0 to 9)

list.add(0, 99);        // beginning

Assumptions of this model

For a single insertion, the model assumes that the internal array of the ArrayList still has an empty position. The case in which the array is full is shown separately under "Keep appending to an empty list". The capacity of an ArrayList starting at 10 and growing to 1.5 times each time (10 → 15 → 22 → 33 → 49), and a LinkedList starting from the beginning or the end, whichever is closer to the index, are the same as in the JDK implementation. The points at which the capacity grows and the number of elements copied match the values that were checked by taking out the internal array of a real ArrayList on JDK 21 on this PC (adding 40 elements grows the array 4 times and copies 80 elements). Actual speed is not determined by the number of positions alone. An array keeps its references to the elements next to each other in memory, which favors the CPU cache, so an ArrayList is often faster than a LinkedList even when it has many elements to shift.

Previous lab: Annotations · Next lab: Inside HashMap