LinkedList is the other List implementation in the standard library, and it works very differently from ArrayList. Instead of storing items in a backing array, it strings them together as a chain of node objects, each one pointing to the next and previous neighbor. That choice changes the cost of almost every operation, and it also lets LinkedList double as a queue or stack because it implements the Deque interface as well. This lesson covers the internal structure, the cost of each common operation, and the narrow set of situations where LinkedList is actually the right pick over ArrayList.

A LinkedList is a doubly-linked chain of node objects. Every node holds three things: the element it stores, a reference to the next node, and a reference to the previous node. The list itself only needs to remember two pointers, the head (first node) and the tail (last node), plus a size counter.

If we add three product names to a fresh LinkedList:

The list prints in order, but the in-memory layout has nothing to do with array slots. Each element lives inside its own node object, allocated wherever the heap had room, and the nodes are wired together with references.

The diagram shows the key idea. Each node knows about its two neighbors, but knows nothing about position 0, 1, or 2. There is no underlying array, no contiguous block of memory. The list reaches any middle element by starting at either end and walking node by node.

Two consequences fall out of that layout. First, inserting at the head or tail is just rewiring two or three references, no matter how big the list is. Second, reaching position i requires walking i steps from one end, which differs sharply from how ArrayList indexes its backing array.

Each node carries the element plus two references and an object header. A LinkedList<Integer> of one million boxed integers uses roughly four times more memory than an int[] of the same length.

LinkedList is unusual among List implementations because it also implements the Deque interface, which is the double-ended queue from java.util. That means the same object can be treated as a list, as a queue (FIFO), or as a stack (LIFO). The class adds methods like addFirst, addLast, removeFirst, removeLast, peek, poll, push, and pop on top of the regular List methods.

A small order-processing queue makes the dual nature concrete. New orders go to the tail; the worker pulls the next order from the head.

Each addLast rewires the tail. Each removeFirst unhooks the head and promotes its successor. None of these operations care about how many orders are in the queue, because the list never has to walk anywhere to do them. The full Deque API isn't covered here. A LinkedList reference can act as either a List or a Deque without conversion.

A second variation is the browsing history list, where each newly viewed product gets pushed onto the front:

Every addFirst is constant-time, no matter how long the history gets. Doing the same thing with an ArrayList and add(0, item) would shift the entire array on every insert, which gets expensive once the list has thousands of entries.

The two-pointer-per-node structure makes some operations very cheap and others surprisingly expensive. The clearest way to keep them straight is to think about what the list has to do for each call.

LinkedList is smart enough to start the walk from whichever end of the chain is closer to the target index, so get(size - 1) is O(1) and get(size / 2) walks about half the list. The Big-O is still O(n), but the constant factor is half of what it would be without that trick.

linkedList.get(i) is O(n), unlike arrayList.get(i) which is O(1). A loop calling get(i) for each index turns an O(n) traversal into O(n^2). Use a for-each loop or an iterator instead.

A short program shows the trap. Iterating with get(i) looks innocent because it works with ArrayList, but on a LinkedList it's quadratic.

Both loops print the same thing. With three items the speed difference is invisible. With three million items, the index-based loop takes minutes; the for-each loop takes a fraction of a second. The compiler doesn't warn about this, because both forms are legal List code. The fix is to use the iterator when walking the whole thing.

add(int index, E element) and remove(int index) are both O(n) on a LinkedList. The reason is worth understanding.

The actual rewiring of node pointers is O(1). Given a reference to the node at position i, splicing a new node in or removing an existing node is just three or four pointer assignments. The cost is in getting to that node in the first place. add(int index, E element) first walks the chain to position index, which is O(n), then does the O(1) splice. The walk dominates, so the whole operation is O(n).

The first call inserts Highlighter at index 2. The list walks from the head to position 2, then splices a new node between Pen and Eraser. The second call removes index 0, which is O(1) because the head pointer already points there. The third call, remove("Eraser"), has to find the matching element first, which is an O(n) scan even though the unhook is O(1).

This is where LinkedList is misleading. The common claim is that "linked lists are great for inserts and removes". That's true when a node reference is already in hand, such as during an iterator walk. It's not true when only the position or the value is known, because finding the right node is itself O(n).

LinkedList.remove(Object o) and LinkedList.remove(int index) are both O(n). The pointer rewiring is O(1), but locating the right node takes a linear walk.

For true O(1) removal during iteration, use the ListIterator, which remembers where it is in the chain:

The iterator walks the chain once. At each step, it.remove() unhooks the current node in O(1) because the iterator already holds a direct reference to it. The whole filter is O(n) overall, with no hidden quadratic cost.

A focused comparison drives the choice between ArrayList and LinkedList:

The headline comparison is get(i). ArrayList indexes in constant time because it knows the offset inside the backing array. LinkedList has to walk the chain. For anything that looks like "loop over the list and read element by element", ArrayList is much faster, and it also uses less memory.

The places where LinkedList actually has an edge are narrow. They mostly come down to head/tail operations:

For almost everything else, ArrayList is the better default. Before using LinkedList, consider whether ArrayDeque would be a better fit for the same workload.

Even where LinkedList is theoretically a good match for the workload, the per-node allocation and the pointer chasing hurt cache performance. Benchmarks of real Java code often show ArrayDeque beating LinkedList on queue and stack workloads by 2-3x.

A small undo-stack example that's a fair fit for LinkedList:

push is addFirst internally, and pop is removeFirst. Both run in constant time. The same code with ArrayList and add(0, item) would shift every element on every push.

In modern Java code, LinkedList is rarely appropriate. The cases where it fits are narrow:

Even in those cases, ArrayDeque often does the same job faster, given the full List API isn't required. A reasonable approach: start with ArrayList. If profiling shows that head insertions or removals are the bottleneck, look at ArrayDeque first. Use LinkedList only when both List and Deque behavior on the same object are required.

LinkedList is a common wrong answer in interviews and code reviews. "Linked list = fast inserts" from a data structures class skips over the cost of getting to the insert point and the cost of allocating a node per element. The valid reasons are head/tail operations and iterator-driven removal.