Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Java LinkedList: Usage, Performance, and Tradeoffs

How Java LinkedList stores elements, common operation costs, and when ArrayList is a better choice.

~5 min readJava
#LinkedList#Java Collections#Data Structures#Performance
Illustration of a Java LinkedList structure showing nodes connected by pointers, with a comparison to an array.

The java.util.LinkedList class implements both the List and Deque interfaces, providing a doubly-linked list that supports efficient insertion and removal at both ends. This article explains how LinkedList behaves, where its performance advantages apply, and when another collection such as ArrayList is a better fit.

How LinkedList Stores Elements

Unlike ArrayList, which stores elements in a contiguous array, LinkedList stores each element in a separate node object. Each node holds a reference to the element, a reference to the previous node, and a reference to the next node. This structure makes LinkedList a doubly-linked list.

Node overhead is an important tradeoff. Every element requires a separate node object plus two extra reference fields compared with an ArrayList element reference. For a collection of large objects, this overhead is relatively small, but for many small objects, the memory footprint can be noticeably larger than an ArrayList of the same size.

Common Operations and Their Costs

The performance of LinkedList operations depends on the position of the element you are accessing or modifying.

Adding and Removing at the Ends

Adding an element at the beginning or end of the list is an O(1) operation because LinkedList keeps references to both the first and last nodes. The same applies to removing the first or last element. This is the primary reason to choose LinkedList over ArrayList when your workload involves frequent insertions or deletions at the front.

java
LinkedList<String> list = new LinkedList<>(); list.addFirst("first"); list.addLast("last"); String first = list.removeFirst(); String last = list.removeLast();

Accessing Elements by Index

Accessing an element at a specific index is O(n) because the list must traverse from either the head or the tail, whichever is closer. The implementation checks the index against the size and starts from the appropriate end. For random access patterns, ArrayList is far more efficient because it can compute the memory offset directly.

java
LinkedList<String> list = new LinkedList<>(); // ... add elements ... String element = list.get(1000); // traverses up to 1000 nodes

Inserting and Removing in the Middle

If you already have a reference to a node (for example, via an iterator), inserting or removing at that position is O(1). However, finding the node by index still requires traversal. In practice, if you frequently need to insert or remove in the middle, think carefully about your access pattern; a structure other than a plain ArrayList may be a better fit.

LinkedList vs ArrayList: When to Choose Which

The decision between LinkedList and ArrayList is not about one being universally faster. It depends on your dominant operation mix.

OperationArrayListLinkedList
Get by indexO(1)O(n)
Add at endAmortized O(1)O(1)
Add at beginningO(n) (shifts)O(1)
Remove from middle by indexO(n) (shifts)O(n) (traverse)
Memory per elementLow (array)High (node)

Use ArrayList when you need fast indexed access and your list size is relatively stable. Use LinkedList when you frequently add or remove from the front or when you need a double-ended list. However, for most list-like use cases, ArrayList is the default recommendation because it provides better cache locality and lower memory overhead.

Iteration and Modification: Fail-Fast Behavior

Like most Java collections, LinkedList is fail-fast. If you modify the list structurally (adding or removing elements) while iterating over it using an Iterator, the iterator will throw a ConcurrentModificationException. This behavior is not specific to LinkedList; it is a general contract in the Java Collections Framework.

To modify the list during iteration, use the iterator's own remove method, which adjusts the internal modification count safely.

java
LinkedList<String> list = new LinkedList<>(); list.add("a"); list.add("b"); Iterator<String> it = list.iterator(); while (it.hasNext()) { String s = it.next(); if (s.equals("a")) { it.remove(); // safe } }

Using LinkedList as a Queue or Deque

Because LinkedList implements Deque, it can be used as a queue or stack. The Deque interface provides methods like offerFirst, offerLast, pollFirst, and pollLast, which are useful for double-ended operations. In single-threaded code, LinkedList is a straightforward choice for a simple queue, but for concurrent scenarios you should use ConcurrentLinkedDeque or a blocking queue from the java.util.concurrent package.

If you need only queue or deque behavior, ArrayDeque is often a better default: it has lower memory overhead and better cache behavior than LinkedList. Choose LinkedList when you also need list operations such as indexed access or insertion/removal through an iterator.

java
Deque<String> deque = new LinkedList<>(); deque.offerFirst("first"); deque.offerLast("last"); String first = deque.pollFirst(); String last = deque.pollLast();

Performance and Memory Considerations

LinkedList has two major performance drawbacks compared to ArrayList: cache locality and memory overhead. Array elements are stored contiguously, so the CPU cache can prefetch them efficiently. Linked nodes are scattered across memory, causing cache misses during traversal. This makes even O(n) operations on ArrayList often faster in practice than the same operations on LinkedList, especially for large lists.

Memory overhead is also higher. Each stored element requires a separate node object with an object header, an element reference, and two link references. The exact overhead varies by JVM, but for lists containing millions of small objects it can be substantial. If memory is a constraint, ArrayList is almost always the better choice.

Common Pitfalls and Misconceptions

A frequent misconception is that LinkedList is faster for all insertion and removal operations. That is only true when you are operating at the ends or when you already hold a node reference. Inserting in the middle still requires traversal, which is O(n). Another pitfall is using get(index) in a loop, which turns an O(n) operation into O(n²) because each call traverses from the beginning.

java
// Bad: O(n²) for n elements for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); } // Better: use an iterator or enhanced for-loop for (String s : list) { System.out.println(s); }

When LinkedList Is the Right Choice

Choose LinkedList when you frequently add and remove from the front of a list, or when you need both List and Deque behavior from the same object. It also works well when you need to insert elements in the middle but already have an iterator positioned at the insertion point. If your workload is primarily queue or deque operations without list access, consider ArrayDeque instead. For all other list operations, ArrayList provides better performance and lower memory usage. The decision should be driven by your actual access patterns, not by a general preference for one collection over another.

Try matching browser tools

All tools

Small utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Java guides

More in Java

All Java guides

The guides filed next to this one in Java, in library order.