LinkedList structure and its real access cost

Understanding LinkedList structure and its real access cost

A java.util.LinkedList is not a row of slots but a chain of small objects. Each element sits in its own Node, which holds the item plus a next and a prev reference, while the list object itself keeps only first, last and size. Nothing in that layout lets the JVM compute where element 7 lives, so there is no address arithmetic to perform: the only way to reach a position is to start at an end and follow references one at a time.

get(int) exists because LinkedList implements List, and it hides a loop. The lookup compares the index against size >> 1 and walks forward from first or backward from last, whichever end is nearer, so one get costs up to about n/2 hops and the middle index is the worst case rather than the last one. Halving the walk changes the constant, not the complexity: an indexed loop calling get(i) restarts the walk every iteration and visits roughly n squared over 4 nodes, where a for-each keeps a single cursor and visits n. The same hidden walk lives inside add(index, e), remove(int), remove(Object), indexOf and contains, so "linked lists insert in constant time" is only true once you already hold the position.

Past complexity there is a hardware cost. Every element needs a separate heap object with roughly 24 bytes of bookkeeping, and those nodes land wherever the allocator put them, so each hop is a dependent load the CPU cannot prefetch and you risk a cache miss per element even during a clean for-each. An ArrayList keeps references contiguous and shifts them with System.arraycopy, which is why it usually wins even on mid-list inserts: moving a block of memory is cheaper than chasing pointers to find where to insert. LinkedList earns its keep when you hold a cursor and splice repeatedly, or when you want a List that is also a Deque and never index into it.

import java.util.LinkedList;
import java.util.List;

public class LinkedListAccessCost {

    // Mirrors LinkedList's own node lookup: walk from whichever end is nearer.
    static int nodesVisited(int size, int index) {
        return index < (size >> 1) ? index + 1 : size - index;
    }

    public static void main(String[] args) {
        List<String> chain = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            chain.add("n" + i);
        }
        System.out.println("size = " + chain.size());

        for (int index : new int[] {0, 4, 5, 9}) {
            System.out.println("get(" + index + ") -> " + chain.get(index)
                    + ", nodes visited: " + nodesVisited(chain.size(), index));
        }

        int indexedLoop = 0;
        for (int i = 0; i < chain.size(); i++) {
            indexedLoop += nodesVisited(chain.size(), i);
        }
        System.out.println("indexed loop visits " + indexedLoop + " nodes");
        System.out.println("for-each loop visits " + chain.size() + " nodes");
    }
}

Worked examples

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class PositionedEdits {
    public static void main(String[] args) {
        LinkedList<String> words = new LinkedList<>(List.of("a", "b", "c", "d"));

        ListIterator<String> it = words.listIterator();
        while (it.hasNext()) {
            String w = it.next();
            if (w.equals("b") || w.equals("d")) {
                it.add(w.toUpperCase());
            }
        }
        System.out.println(words);

        ListIterator<String> back = words.listIterator(words.size());
        StringBuilder reversed = new StringBuilder();
        while (back.hasPrevious()) {
            reversed.append(back.previous());
        }
        System.out.println(reversed);
    }
}

import java.util.LinkedList;
import java.util.List;

public class EndsVersusMiddle {
    public static void main(String[] args) {
        LinkedList<Integer> nums = new LinkedList<>();
        for (int i = 1; i <= 6; i++) {
            nums.addLast(i);
        }

        StringBuilder order = new StringBuilder();
        while (!nums.isEmpty()) {
            order.append(nums.removeFirst());
            if (!nums.isEmpty()) {
                order.append(nums.removeLast());
            }
        }
        System.out.println("drained from both ends: " + order);

        LinkedList<Integer> mid = new LinkedList<>(List.of(10, 20, 30, 40));
        mid.add(2, 25);
        mid.addFirst(5);
        System.out.println(mid);
        System.out.println("indexOf(30) = " + mid.indexOf(30));
    }
}

Important notes

Common mistakes

Try it yourself