[Java Basics] ArrayList and LinkedList in Java: Working with Collections

An array in Java has a length that is fixed when the object is created and can never change afterwards. That single restriction is the reason java.util exists: as soon as a program does not know in advance how many elements it will hold, an array stops being the right tool and a List takes over.

ArrayList and LinkedList are the two List implementations every Java developer meets first, and almost every tutorial closes the comparison with "LinkedList is faster for insertion and deletion". That claim is misleading often enough to be worth dismantling, so this article counts the operations each implementation actually performs instead of repeating the slogan.

Every output line, compiler error, stack trace and counter value below was produced by compiling and running the code on OpenJDK 21.0.6.

Why a fixed-length array is not enough

An array is sized once. Ask for a fourth slot in a three-slot array and the JVM stops you:

public class FixedArray {
    public static void main(String[] args) {
        String[] names = new String[3];
        names[0] = "ada";
        names[1] = "linus";
        names[2] = "grace";
        names[3] = "ken";
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
	at FixedArray.main(FixedArray.java:7)

To hold a fourth name you have to allocate a bigger array, copy the three existing references into it, and reassign the variable. Doing that by hand once is tedious; doing it every time the data grows, while also tracking how many slots are actually in use, is a small data structure. ArrayList is exactly that data structure, already written and already tested.

A List differs from an array in four ways that matter:

That third row has consequences of its own, and the section on autoboxing below is entirely about them.

The Collection and List interfaces

List is not a class, it is an interface, and it sits at the bottom of a short chain of interfaces. Each one adds a capability, and everything above List is shared with the other collection types.

That chain is not a diagram someone drew from memory. It can be read straight out of the runtime:

import java.util.*;

public class Shape {
    static void show(Class<?> c) {
        StringBuilder sb = new StringBuilder(c.getSimpleName() + " -> ");
        for (Class<?> i : c.getInterfaces()) sb.append(i.getSimpleName()).append(" ");
        Class<?> sup = c.getSuperclass();
        if (sup != null) sb.append("| extends ").append(sup.getSimpleName());
        System.out.println(sb.toString().trim());
    }

    public static void main(String[] args) {
        show(Collection.class);
        show(List.class);
        show(SequencedCollection.class);
        show(ArrayList.class);
        show(LinkedList.class);
    }
}

Collection -> Iterable
List -> SequencedCollection
SequencedCollection -> Collection
ArrayList -> List RandomAccess Cloneable Serializable | extends AbstractList
LinkedList -> List Deque Cloneable Serializable | extends AbstractSequentialList

Read from the top down, each interface adds one idea:

The two marker interfaces at the bottom are the ones that tell you what you are really holding. ArrayList implements RandomAccess, which is the JDK's way of saying "indexed access on this list is cheap". LinkedList does not implement it, and implements Deque instead. Nothing in the language enforces that, but code in the JDK branches on it, and so should yours when you choose which one to construct.

Declare the interface, construct the class

The practical consequence of that hierarchy is a habit worth forming immediately: declare the variable as List, and pick the implementation only in the new expression.

List<String> names = new ArrayList<>();

Everything downstream of that line - other methods, return types, fields - sees a List. Swapping ArrayList for LinkedList then touches exactly one word. Declaring the variable as ArrayList locks the choice in everywhere the variable travels, and buys nothing in return.

The one thing you give up is access to methods the interface does not declare. LinkedList has push, which comes from Deque and not from List, so a List-typed variable cannot see it:

List<String> names = new LinkedList<>();
names.push("ada");

IfaceOnly.java:6: error: cannot find symbol
        names.push("ada");
             ^
  symbol:   method push(String)
  location: variable names of type List<String>
1 error

That error is the type system doing its job. If you genuinely need push, the type you want is Deque, not LinkedList.

Creating a list and the methods you will actually use

A List needs a type argument, and it has to be a reference type. Primitives are rejected outright:

List<int> numbers = new ArrayList<>();

PrimList.java:5: error: unexpected type
        List<int> numbers = new ArrayList<>();
             ^
  required: reference
  found:    int
1 error

With that out of the way, the whole core API fits in one program:

import java.util.*;

public class Basics {
    public static void main(String[] args) {
        List<String> langs = new ArrayList<>();
        System.out.println("isEmpty on a new list: " + langs.isEmpty() + ", size " + langs.size());

        langs.add("Java");
        langs.add("Kotlin");
        langs.add("Scala");
        langs.add(1, "Groovy");
        System.out.println("after adds: " + langs + ", size " + langs.size());

        System.out.println("get(0)          = " + langs.get(0));
        System.out.println("set(2, \"Clojure\") returns " + langs.set(2, "Clojure") + " -> " + langs);
        System.out.println("indexOf(Scala)  = " + langs.indexOf("Scala"));
        System.out.println("contains(Java)  = " + langs.contains("Java"));
        System.out.println("remove(\"Groovy\") = " + langs.remove("Groovy") + " -> " + langs);
        System.out.println("remove(0)        = " + langs.remove(0) + " -> " + langs);

        List<String> dup = new ArrayList<>(List.of("a", "b", "a", "b"));
        System.out.println("  " + dup + " indexOf(b)=" + dup.indexOf("b") + " lastIndexOf(b)=" + dup.lastIndexOf("b"));

        try {
            langs.get(9);
        } catch (IndexOutOfBoundsException e) {
            System.out.println("get(9) threw " + e);
        }
    }
}

isEmpty on a new list: true, size 0
after adds: [Java, Groovy, Kotlin, Scala], size 4
get(0)          = Java
set(2, "Clojure") returns Kotlin -> [Java, Groovy, Clojure, Scala]
indexOf(Scala)  = 3
contains(Java)  = true
remove("Groovy") = true -> [Java, Clojure, Scala]
remove(0)        = Java -> [Clojure, Scala]
  [a, b, a, b] indexOf(b)=1 lastIndexOf(b)=3
get(9) threw java.lang.IndexOutOfBoundsException: Index 9 out of bounds for length 2

Four details in that output are worth stopping on:

• add(1, "Groovy") inserts at a position and shifts everything after it right; add("Scala") appends.
• set returns the element it replaced, not the list and not a boolean.
• remove(Object) returns boolean, remove(int) returns the removed element. Two different methods with the same name, and the next-to-last section of this article is about what that costs you.
• indexOf returns -1 when the element is absent, and a list happily holds duplicates - indexOf finds the first, lastIndexOf the last.

Here is the whole set in one table:

contains and indexOf compare with equals, not with ==, which is why a List of String finds a value you built at runtime. The rules a class must follow for that to behave correctly matter far more for hash-based collections, and article 34 covers them.

How ArrayList actually stores its elements

Inside every ArrayList there is one field doing the real work: Object[] elementData. size counts how many of its slots are in use, and elementData.length is the capacity. The two are almost never equal.

You do not have to take that on faith. Reflection can read the field out of a live list after every add:

import java.lang.reflect.Field;
import java.util.ArrayList;

public class Capacity {
    public static void main(String[] args) throws Exception {
        Field f = ArrayList.class.getDeclaredField("elementData");
        f.setAccessible(true);

        ArrayList<Integer> list = new ArrayList<>();
        int previous = ((Object[]) f.get(list)).length;
        System.out.println("size 0   capacity " + previous);

        for (int i = 1; i <= 200; i++) {
            list.add(i);
            int capacity = ((Object[]) f.get(list)).length;
            if (capacity != previous) {
                System.out.println("size " + list.size() + "  capacity " + previous + " -> " + capacity);
                previous = capacity;
            }
        }
    }
}

Reading a private field of java.util needs the module opened on the command line, otherwise it throws InaccessibleObjectException:

java --add-opens java.base/java.util=ALL-UNNAMED Capacity

size 0   capacity 0
size 1  capacity 0 -> 10
size 11  capacity 10 -> 15
size 16  capacity 15 -> 22
size 23  capacity 22 -> 33
size 34  capacity 33 -> 49
size 50  capacity 49 -> 73
size 74  capacity 73 -> 109
size 110  capacity 109 -> 163
size 164  capacity 163 -> 244

Three facts fall out of those ten lines.

A new ArrayList allocates nothing. new ArrayList<>() starts with a shared zero-length array. The first add is what allocates, and it allocates ten slots.

Growth is by half, not by double. From ten onwards the sequence is 10, 15, 22, 33, 49, 73, 109, 163, 244, which is oldCapacity + (oldCapacity >> 1) applied over and over - a 1.5x factor, with the shift rounding down. The bars above are drawn to scale so the geometric shape is visible rather than asserted.

Each grow allocates and copies. Growing means a new array plus a copy of every live element into it. Counting those copies for a list built to 100,000 elements by repeated add:

Building 100000 elements
  grow() calls                       = 24
  ArrayList.add(e)    element copies = 213413
  copies per element                 = 2.13

Twenty-four allocations and about 2.1 copied references per element added, across the entire build. That is what "amortised constant time" means in practice: individual add calls are occasionally expensive, and the average stays small because the capacity jumps by half of a number that is itself growing.

Two knobs follow from this. If you know roughly how many elements are coming, new ArrayList<>(100) allocates the array once and skips the whole sequence. And capacity never shrinks on its own - clear() empties the list but keeps the array:

after 100 adds: size=100 capacity=109
after clear():  size=0 capacity=109
after trimToSize(): size=0 capacity=0

trimToSize() is the only thing that gives the memory back, and it is rarely worth calling.

How LinkedList actually stores its elements

LinkedList stores nothing in an array. Each element gets its own Node object holding three references: the element itself, the previous node and the next node. The list keeps a reference to the first node and to the last one, plus a size counter.

That layout has one genuine advantage and one genuine cost, and both are structural.

The advantage is that adding or removing at either end is a couple of pointer assignments, with no shifting and no reallocation, ever. That is why LinkedList also implements Deque:

import java.util.*;

public class Queue {
    public static void main(String[] args) {
        Deque<String> jobs = new ArrayDeque<>();
        jobs.addLast("build");
        jobs.addLast("test");
        jobs.addFirst("checkout");
        System.out.println("queue: " + jobs);
        while (!jobs.isEmpty()) System.out.println("  running " + jobs.removeFirst());
    }
}

queue: [checkout, build, test]
  running checkout
  running build
  running test

Note which class that example constructs. ArrayDeque is a Deque too and is backed by a circular array, and its own javadoc says it is "likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue". LinkedList is the Deque you reach for when you also need it to be a List.

The cost is that there is no such thing as jumping to index i. To reach a position, LinkedList has to follow next references one at a time. The implementation is slightly cleverer than a naive walk - it starts from whichever end is nearer the index - but that only halves the distance, it does not change the shape of the work.

ArrayList vs LinkedList: which should you use?

This is where the standard advice goes wrong. The claim "LinkedList is faster for insertion and deletion" is true only for a much narrower case than it sounds, and false in the case people usually have in mind.

Insertion and deletion in the middle of a list are two steps, not one: find the position, then change the structure. LinkedList wins the second step and loses the first, and for a middle position the first step costs as much as the whole ArrayList operation.

The figures below are operation counts, not timings. A count is reproducible on any machine, in any load, on any JVM build; a stopwatch reading is not. They come from a program that reproduces line for line what the JDK does - System.arraycopy of size - index references for ArrayList.add(int, E), of (size - 1) - index for ArrayList.remove(int), and for LinkedList.node(int) a walk from whichever end is nearer - on a list of 100,000 elements:

Read the fourth row twice. Removing from the middle costs LinkedList exactly the same count as ArrayList - it just spends it walking instead of copying. And a walk is the more expensive of the two: System.arraycopy is a single bulk memory move over a contiguous block, while following 49,999 next references touches that many separately allocated objects scattered across the heap, each one a probable cache miss. The two rows are equal on the counter and not remotely equal on hardware.

The rows where LinkedList genuinely wins are the last two, and both are about the ends of the list, not the middle.

⚠️ The third row is the one that turns a working program into a slow one. An ordinary for (int i = 0; i < list.size(); i++) list.get(i) loop is linear on an ArrayList and quadratic on a LinkedList. Iterating with the enhanced for loop avoids it entirely, because the iterator holds its position instead of re-walking from an end.

So the practical rule is short:

• Default to ArrayList. It wins on indexed access, on appending, on memory per element, and on locality. Almost all real list code appends and iterates.
• Reach for LinkedList only when you want Deque behaviour - work at both ends, no indexing - and even then compare it against ArrayDeque first.
• LinkedList's cheap insert needs a position you already hold. That means an Iterator or a ListIterator parked where you want to edit. If your code says list.add(i, x) or list.remove(i), you do not hold a position, you hold an index, and the walk is back.

One more thing the table does not show: per-element overhead. Every element in a LinkedList is a separate Node object with an object header and three references, on top of the element itself. An ArrayList stores one reference per element in a shared array. For a large list that is a real multiple in memory, and memory is what the cache is made of.

Iterating a list

Three ways, in the order you should reach for them.

List<String> names = new ArrayList<>(List.of("ada", "linus", "grace"));

for (String n : names) {
    System.out.println(n);
}

names.forEach(System.out::println);

for (int i = 0; i < names.size(); i++) {
    System.out.println(i + ": " + names.get(i));
}

The enhanced for loop is the default. It compiles down to an Iterator, which is why it works on any Iterable and why it is safe on a LinkedList - the iterator keeps its position and moves one next at a time. Use the indexed loop only when you actually need i, and then remember it is the quadratic form on a LinkedList.

Both contains and indexOf are linear scans on either implementation, and both call equals on the stored elements. Counting the real calls with an element class whose equals increments a counter, on a list of 1000:

ArrayList size 1000
  first   indexOf -> 0, equals() calls = 1
  middle  indexOf -> 500, equals() calls = 501
  last    indexOf -> 999, equals() calls = 1000
  missing indexOf -> -1, equals() calls = 1000
LinkedList size 1000
  first   indexOf -> 0, equals() calls = 1
  middle  indexOf -> 500, equals() calls = 501
  last    indexOf -> 999, equals() calls = 1000
  missing indexOf -> -1, equals() calls = 1000

Identical, and both proportional to the position. A List is the wrong structure for "is this value present" when the list is large and the question is asked often - that is what article 34 is for.

Removing elements while you iterate

Removing from a list while walking it is the single most common way to break list code. This throws:

import java.util.*;

public class Cme {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("ada", "linus", "grace", "ken"));
        for (String n : names) {
            if (n.startsWith("l")) {
                names.remove(n);
            }
        }
        System.out.println(names);
    }
}

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1095)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1049)
	at Cme.main(Cme.java:6)

Note the frame in the middle: ArrayList$Itr.next. There is no thread in this program, and nothing is concurrent about it. The name refers to modifying the list while an iterator over it is live, which is exactly what the enhanced for loop is doing on your behalf.

The mechanism is two integers. The list keeps modCount, incremented on every structural change. The iterator copies that value into expectedModCount when it is created, and compares the two on every next(). Both fields can be read with reflection, which makes the whole thing concrete:

1 names.iterator()        modCount=0 expected=0
2 it.next() -> ada        modCount=0 expected=0
3 names.remove("ada")     modCount=1 expected=0
4 it.next()               throws ConcurrentModificationException

1 ok.iterator()           modCount=0 expected=0
2 j.next() -> ada         modCount=0 expected=0
3 j.remove()              modCount=1 expected=1
4 j.next() -> linus       modCount=1 expected=1

Iterator.remove() bumps modCount and then copies it back into expectedModCount, so the two stay in step. Removing through the list does the first half and not the second. LinkedList behaves identically, with its own iterator class in the trace:

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:977)
	at java.base/java.util.LinkedList$ListItr.next(LinkedList.java:899)
	at LlCme.main(LlCme.java:6)

The two cases that do not throw, and are still wrong

The check runs inside next(), not inside hasNext(). So removing the second-to-last element ends the loop early and silently:

List<String> quiet = new ArrayList<>(List.of("a", "b", "c", "d"));
for (String s : quiet) if (s.equals("c")) quiet.remove(s);
System.out.println(quiet);

[a, b, d]

That one happens to produce the right answer, purely by accident: after the removal size is 3 and the cursor is 3, so hasNext() returns false and next() is never called again. Change the data and it throws.

The other case is the indexed loop, which never involves an iterator and so never throws - it just skips elements:

List<String> skip = new ArrayList<>(List.of("ada", "linus", "lisa", "grace", "ken"));
for (int i = 0; i < skip.size(); i++) {
    if (skip.get(i).startsWith("l")) skip.remove(i);
}
System.out.println(skip);

[ada, lisa, grace, ken]

Removing index 1 shifts lisa down into index 1, and i++ moves straight past it to index 2. Every element sitting immediately after a removed one is skipped, so lisa survives a filter that was meant to delete it.

The four correct ways

// 1. removeIf - shortest, and the one to reach for
list.removeIf(s -> s.startsWith("l"));

// 2. Iterator.remove - when the condition needs more than a predicate
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    if (it.next().startsWith("l")) it.remove();
}

// 3. walk the indices downwards, so removals never move an unvisited element
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i).startsWith("l")) list.remove(i);
}

// 4. build a new list and keep the original intact
List<String> kept = new ArrayList<>();
for (String s : list) if (!s.startsWith("l")) kept.add(s);

All four turn [ada, linus, lisa, grace, ken] into [ada, grace, ken]. removeIf calls its predicate exactly once per element - verified by counting the calls, five for a list of five - and updates modCount once, after the pass.

A list of Integer: autoboxing and the remove trap

A List holds objects, so a list of numbers is a List of Integer. Autoboxing hides the conversion in both directions:

List<Integer> scores = new ArrayList<>();
scores.add(90);            // autoboxed: Integer.valueOf(90)
scores.add(85);
int first = scores.get(0); // unboxed: first.intValue()
System.out.println("first + 5 = " + (first + 5));
System.out.println("element class = " + scores.get(0).getClass().getName());

first + 5 = 95
element class = java.lang.Integer

Convenient, and mostly invisible - until an element is null. An Integer reference can be null; an int cannot, so the unboxing fails:

unboxing null threw java.lang.NullPointerException
  message: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.List.get(int)" is null

remove(int) and remove(Object)

Now the trap. List declares two remove methods: remove(int index) and remove(Object o). On a List of String they can never be confused. On a List of Integer they collide, and the compiler picks the one you probably did not mean:

import java.util.*;

public class RemoveTrap {
    public static void main(String[] args) {
        List<Integer> ids = new ArrayList<>(List.of(10, 20, 30, 40));

        List<Integer> a = new ArrayList<>(ids);
        a.remove(2);
        System.out.println("remove(2)                  -> " + a);

        List<Integer> b = new ArrayList<>(ids);
        b.remove(Integer.valueOf(20));
        System.out.println("remove(Integer.valueOf(20))-> " + b);

        List<Integer> c = new ArrayList<>(ids);
        System.out.println("remove(Object 20) returned " + c.remove((Object) 20) + " -> " + c);

        List<Integer> d = new ArrayList<>(ids);
        try {
            d.remove(20);
        } catch (IndexOutOfBoundsException e) {
            System.out.println("remove(20) threw " + e);
        }
    }
}

remove(2)                  -> [10, 20, 40]
remove(Integer.valueOf(20))-> [10, 30, 40]
remove(Object 20) returned true -> [10, 30, 40]
remove(20) threw java.lang.IndexOutOfBoundsException: Index 20 out of bounds for length 4

a.remove(2) deleted 30, the element at index 2. It did not look for the value 2. Overload resolution prefers a method that needs no boxing, so an int literal always selects remove(int), and the compiler never warns - both overloads are applicable and one is a better match.

The fix is to make the argument an Object so the other overload is chosen. remove(Integer.valueOf(20)) is the clearest form; the cast remove((Object) 20) works too. And when the index is out of range, as in the last case, you at least get an exception rather than a silently wrong deletion - which is the lucky version of this bug.

Integer identity

One more autoboxing detail worth knowing while working with a List of Integer:

127 == 127 (Integer) : true
128 == 128 (Integer) : false
indexOf(128) = 1 (indexOf uses equals, not ==)

Integer.valueOf caches the range -128 to 127, so small boxed values compare equal with == by accident and larger ones do not. The list methods are unaffected because they all use equals. Your own code is not: never compare boxed values with ==.

List.of and Arrays.asList are not ArrayList

Two extremely common one-liners produce lists that are not what people assume.

import java.util.*;

public class Immutable {
    public static void main(String[] args) {
        List<String> of = List.of("a", "b", "c");
        System.out.println("List.of class      = " + of.getClass().getName());

        String[] arr = {"a", "b", "c"};
        List<String> asList = Arrays.asList(arr);
        System.out.println("Arrays.asList class = " + asList.getClass().getName());
        asList.set(0, "z");
        System.out.println("after set: list " + asList + ", backing array " + Arrays.toString(arr));
    }
}

List.of class      = java.util.ImmutableCollections$ListN
Arrays.asList class = java.util.Arrays$ArrayList
after set: list [z, b, c], backing array [z, b, c]

Neither is a java.util.ArrayList. Here is what each one refuses:

List.of is fully immutable, and it rejects null so aggressively that even contains(null) throws NullPointerException. Arrays.asList is fixed-size rather than immutable: it is a thin view over the array you passed, so set works and writes straight through to the array, as the output above shows.

When you want a real, mutable list from a literal, wrap it:

List<String> copy = new ArrayList<>(List.of("a", "b", "c"));
copy.add("d");
System.out.println(copy);

[a, b, c, d]

That is the idiom to memorise. List.of for constants you never modify; new ArrayList<>(List.of(...)) for everything else.

FAQ

What is the difference between size and capacity?

size() is how many elements the list holds and is part of the List interface. Capacity is elementData.length inside an ArrayList, is not visible through any public method, and is always greater than or equal to size(). LinkedList has no capacity at all - it allocates one node per element and nothing spare.

Which is faster, ArrayList or LinkedList?

ArrayList, for nearly everything real code does. It wins indexed access outright, wins appending, uses far less memory per element, and its elements sit contiguously so the CPU cache works for you rather than against you. LinkedList wins only when you work at both ends without indexing, or when you already hold an Iterator positioned where you want to edit - and for the first of those, ArrayDeque is usually the better answer.

Why does remove(1) delete the wrong element in a list of Integer?

Because it is not the method you think you are calling. remove(1) with an int literal binds to remove(int index) and deletes the element at index 1. To remove the value 1, force the other overload: remove(Integer.valueOf(1)).

Is ArrayList thread-safe?

No. Neither is LinkedList. Concurrent modification from two threads can corrupt the internal state, and ConcurrentModificationException is a best-effort check for the single-threaded case, not a guarantee for the multi-threaded one. Collections.synchronizedList(...) and the classes in java.util.concurrent are the answers, and they belong in a later course.

Can a list hold different types?

A List of Object can:

List<Object>          -> [text, 42, 3.5]
  String text
  Integer 42
  Double 3.5

It is legal, and it is almost always a design mistake - you lose every compile-time guarantee and have to cast on the way out. Model the thing properly with a class instead.

How do I sort a list?

list.sort(null) sorts in natural order, list.sort(Comparator.reverseOrder()) reverses it, and Collections.sort(list) is the older equivalent of the first:

sort(null)            -> [ada, grace, linus]
reverseOrder          -> [linus, grace, ada]

Sorting mutates the list in place, so it fails on List.of.

Conclusion

ArrayList and LinkedList are two ways of implementing the same List contract, and the choice between them is much less balanced than it is usually presented. ArrayList keeps every element in one array, grows it by half when it fills, and reaches any index in a single read. LinkedList keeps one node object per element, which makes both ends cheap and every position in between expensive to find. Declare List, construct ArrayList, and only move away from that when you have a concrete reason at the ends of the list.

The rest of the essentials are habits: use the enhanced for loop, use removeIf or Iterator.remove to delete during a walk, remember that remove(1) on a list of Integer is a position and not a value, and remember that List.of is immutable while Arrays.asList is merely fixed-size.

Article 34 turns from positions to keys with HashMap - how a Map stores entries, why lookup does not have to scan, and the hashCode and equals contract that makes it work.