java arraylist vs linkedlist: Practical Usage and Code Examp

Choosing java arraylist vs linkedlist comes down to how each structure stores elements and what that means for the operations your code performs. Both implement the List interface, so in many places they are interchangeable. The difference shows up in runtime behavior: ArrayList keeps elements in a resizable array, while LinkedList stores each element in a node that references its neighbors.

Internal Storage and What It Means

ArrayList wraps an Object[] array. When the array fills up, the list allocates a new, larger array and copies the existing elements over. The growth factor in the standard Java implementation is 1.5x, so the number of copy operations stays logarithmic as elements are appended.

LinkedList uses a doubly-linked list. Each element is wrapped in a Node object that holds the element value plus references to the previous and next nodes. The list keeps references to the first and last nodes. There is no contiguous block of memory, and there is no resize operation.

This structural difference is the root cause of every other difference between the two classes.

Random Access: The get(int) Operation

ArrayList.get(int index) is a direct array read. Given an index, the JVM can compute the memory address immediately, so the operation is O(1).

LinkedList.get(int index) has to walk the chain of nodes. The implementation optimizes slightly by starting from whichever end is closer, but the operation is still O(n) in the worst case. For a list with a million elements, reading an element near the middle means following half a million node references.

List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();

// Populate both lists with the same data
for (int i = 0; i < 100_000; i++) {
    arrayList.add("item-" + i);
    linkedList.add("item-" + i);
}

// Direct index access
String fromArrayList = arrayList.get(50_000);   // O(1)
String fromLinkedList = linkedList.get(50_000); // O(n)

The get call on the linked list has to traverse from the nearest end to reach index 50,000. The array list reads the element directly from the backing array. If your algorithm indexes into the list repeatedly, ArrayList is the only reasonable choice.

Insertion and Removal: Where the Cost Comes From

For ArrayList, inserting or removing an element at an arbitrary index requires shifting every subsequent element. If you insert at index 0, all existing elements move one position to the right. This is O(n). Adding at the end is amortized O(1) because most appends do not trigger a resize.

For LinkedList, inserting or removing at a known position is O(1) if you already hold the node reference. The list only needs to update the prev and next references of the surrounding nodes. However, finding that position by index is O(n), so an operation like remove(index) still costs O(n) because of the traversal.

The practical difference appears in code like this:

// Inserting at the front of a large list
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

for (int i = 0; i < 100_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

arrayList.add(0, -1);   // O(n): shifts all 100,000 elements
linkedList.add(0, -1);  // O(1): updates the head reference

The same pattern applies to removal. Removing the first element of an ArrayList shifts everything left. Removing the first element of a LinkedList just updates the head reference. But removing an element in the middle of a LinkedList still requires walking to that position first.

Memory Footprint and Cache Behavior

ArrayList stores elements in a single contiguous array. The overhead is the array object itself plus a small amount of bookkeeping. Each element occupies one reference slot in the array.

LinkedList stores each element in a Node object. On a 64-bit JVM with compressed object pointers, each node typically carries the element reference plus two references for the previous and next nodes. That is significant per-element overhead compared to a single reference in an array.

Cache behavior matters as well. The CPU loads data in cache lines. When iterating over an ArrayList, consecutive elements are adjacent in memory, so the CPU can prefetch them efficiently. When iterating over a LinkedList, nodes are scattered across the heap, so each step may miss the cache and load a new cache line. For large lists, this makes iteration slower on linked lists even though the algorithmic complexity is the same.

Iteration and Traversal

Both classes implement Iterable, and a for-each loop works identically at the source level. The difference is in what happens during iteration.

For ArrayList, the iterator walks the backing array by index. Each next() call is an array read.

For LinkedList, the iterator follows node references. Each next() call dereferences the current node and moves to the next.

The algorithmic complexity of a full iteration is O(n) for both. The constant factor is higher for LinkedList because of the cache behavior described above.

There is also a difference with remove() during iteration. Both iterators support remove(), but the LinkedList iterator can remove the current node in O(1) because it holds the node reference, while the ArrayList iterator must shift elements.

// Removing elements during iteration
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().startsWith("skip-")) {
        it.remove();
    }
}

For LinkedList, each remove() call is O(1) because the iterator already points at the node. For ArrayList, each remove() call is O(n) because the remaining elements shift. Filtering a large ArrayList with iterator removal is therefore much slower than filtering a LinkedList.

LinkedList as a Deque

LinkedList implements both List and Deque. This means it can be used as a queue or stack without wrapping it in another class.

Deque<String> queue = new LinkedList<>();
queue.addLast("first");
queue.addLast("second");
String next = queue.removeFirst(); // "first"

ArrayList does not implement Deque. If you need queue behavior with occasional indexed access, LinkedList gives you both in one class. If you only need queue behavior, ArrayDeque is usually a better choice because it uses a resizable array and has better cache locality.

This is a real decision point: the choice is not always ArrayList versus LinkedList. Sometimes the correct answer is ArrayDeque or another collection entirely.

Choosing Between ArrayList and LinkedList

The decision criteria are concrete:

Use ArrayList when you need indexed access, iterate frequently, or append elements at the end. This covers most list use cases in real applications.
Use LinkedList when you need to insert or remove at the beginning or end frequently and also need List semantics, or when you need a Deque and a List in the same object.
Avoid LinkedList when your code calls get(int) in a loop, because each call is O(n) and the total becomes O(n²).
Avoid ArrayList when you constantly insert at the front of a very large list, because each insertion shifts the entire array.

There is a common misconception that LinkedList is faster for all insertion and removal operations. That is only true when the insertion point is already known. When the insertion point is found by index, the traversal cost dominates.

A Practical Example: Filtering a Large List

Consider a task that reads a list of records, removes entries that do not match a condition, and then processes the survivors in order.

List<Record> records = loadRecords(); // returns either ArrayList or LinkedList

Iterator<Record> it = records.iterator();
while (it.hasNext()) {
    if (!it.next().isValid()) {
        it.remove();
    }
}

for (Record r : records) {
    process(r);
}

With an ArrayList, the removal loop shifts elements many times, which is expensive for a large list. With a LinkedList, each removal is O(1) but the final iteration is slower due to cache behavior. Which one wins depends on the ratio of removals to surviving elements and the size of the list. If most elements survive, ArrayList is usually better because the iteration cost dominates. If most elements are removed, LinkedList can win because the removal cost dominates.

There is no universal answer, but the the mechanism is clear: count the cost of shifting versus the cost of node traversal and cache misses.