1. Introduction to LinkedList
LinkedList<E> is a Java Collections Framework class that implements both the List<E> and Deque<E> interfaces. It stores elements in a sequence, permits duplicates, and supports operations at both ends of the sequence.
Its internal structure differs from ArrayList. An ArrayList stores references in a resizable array; a LinkedList connects individual node objects together. This design makes adding or removing at the head or tail efficient, but accessing an element by index requires traversing the chain.
LinkedList is useful to understand because it demonstrates a fundamental data-structure trade-off: improving one kind of operation does not automatically improve every operation. In modern Java applications, ArrayList is generally the default list choice, while ArrayDeque is often a better choice for queue and stack behavior.
2. How a LinkedList Is Built
A Java LinkedList is a doubly linked list. Each node conceptually stores three things:
- The element value or reference.
- A link to the next node.
- A link to the previous node.
The list keeps references to the first node, often called the head, and the last node, often called the tail, as well as a size count.
For a list containing Notebook, Pen, and Eraser, the links form a chain:
Unlike an array, the nodes do not need to occupy adjacent memory locations. Each node can be allocated separately in the heap, and references connect the nodes into the required order.
2.1 What the structure means
A node does not have a built-in numeric position such as index 0 or index 1. To reach an element by index, the list must follow node references from one end. The implementation can start at the head or tail, choosing the closer end, but it still may need to visit many nodes.
The doubly linked structure also makes it possible to move backward as well as forward. The previous-node link is especially useful for operations near the tail and for bidirectional iteration.
2.2 Memory overhead
Each node stores links in addition to the element reference and the object’s runtime overhead. This generally consumes more memory per element than an array-backed list. It also involves pointer chasing: accessing each next node requires following a reference, which can be less friendly to CPU caches than scanning an array.
Exact memory usage depends on the JVM, object layout, reference size, and element types. It is best to understand the direction of the trade-off rather than rely on a universal byte count.
3. LinkedList Implements Both List and Deque
The two interfaces describe different ways to use the same object:
List<E>treats the collection as an ordered, index-based sequence.Deque<E>treats it as a double-ended queue, supporting insertion and removal at both ends.
Because LinkedList implements both, it can be used as a list, queue, or stack without converting the object.
| Method | General purpose |
|---|---|
addFirst(e) | Insert at the front |
addLast(e) | Insert at the back |
removeFirst() | Remove and return the first element |
removeLast() | Remove and return the last element |
peekFirst() / peekLast() | Inspect an end without removing |
pollFirst() / pollLast() | Retrieve and remove an end, returning null if empty |
push(e) | Push onto the stack end |
pop() | Remove from the stack end |
The exact behavior of related queue methods matters. Methods such as removeFirst() throw an exception if the deque is empty, while pollFirst() returns null. Choose the form that matches the program’s desired empty-collection behavior.
4. Using LinkedList as a Queue
A queue commonly follows FIFO: first in, first out. New items enter at the back, and the next item to process leaves from the front.
The first order added is the first order removed. Adding at the tail and removing at the head are constant-time operations in LinkedList because the list already keeps references to both ends.
However, if the program only needs queue or deque behavior, ArrayDeque is generally worth considering first. It often performs better and avoids per-element node allocation.
5. Using LinkedList as a Stack
A stack commonly follows LIFO: last in, first out. The most recently pushed item is the first one popped.
In the Deque API, push and pop operate at the same end, so they provide stack-like behavior. Both are constant-time for LinkedList.
For new code, prefer the Deque interface rather than the legacy Stack class. If only stack operations are required, ArrayDeque is often the more efficient implementation.
6. Time Complexity of Common Operations
The operation costs follow from the difference between locating a node and changing the links once that node is known.
| Operation | Typical time | Explanation |
|---|---|---|
addFirst(e) | \(O(1)\) | Update the head and neighboring links |
addLast(e) | \(O(1)\) | Update the tail and neighboring links |
removeFirst() | \(O(1)\) | Unlink the head node |
removeLast() | \(O(1)\) | Unlink the tail node |
add(e) | \(O(1)\) | Append at the tail |
get(index) | \(O(n)\) | Traverse to the requested position |
set(index, e) | \(O(n)\) | Find the node, then replace its element |
add(index, e) | \(O(n)\) | Find the position, then link in a node |
remove(index) | \(O(n)\) | Find the node, then unlink it |
contains(e) | \(O(n)\) | Compare elements while traversing |
size() | \(O(1)\) | Return the stored size counter |
| Full iteration | \(O(n)\) | Visit each node once |
A nuance is important: the pointer rewiring itself is constant time when a direct reference to the relevant node is already available. The indexed methods still take linear time overall because finding the node generally requires traversal.
7. Why Indexed Loops Can Be Slow
This pattern looks natural because it works well for ArrayList:
For LinkedList, each get(i) can traverse part of the chain. Repeating that operation for every index means the program repeatedly walks through many of the same nodes. The total work can become \(O(n^2)\).
Use a for-each loop for ordinary traversal:
The for-each loop uses an iterator, which moves from node to node in sequence. A full traversal is \(O(n)\), because each node is visited once.
The compiler does not normally warn about this performance issue, because indexed access is valid for every List. The correct iteration style depends on the implementation’s performance characteristics.
8. Insertion and Removal: The Important Distinction
It is often said that linked lists are good at insertion and deletion. That statement needs context.
If the node reference is already known, adding or removing a node can be performed by changing a small number of links. This is \(O(1)\) pointer work.
But if the program only knows an index or a value, LinkedList must first find the relevant node:
add(index, element)traverses to the insertion position.remove(index)traverses to the indexed node.remove(object)searches for the first equal element.
These locating steps can take \(O(n)\), so the complete operations are linear time in general.
8.1 When iterator-based removal helps
A ListIterator or Iterator already holds traversal state. When it removes the current element through its own remove() method, LinkedList can unlink the known node without searching for it again.
A single iterator pass that removes matching elements can therefore be \(O(n)\) overall rather than repeatedly searching by value or index.
This is a particularly useful pattern when removal happens as part of a traversal.
9. ArrayList Versus LinkedList
| Aspect | ArrayList | LinkedList |
|---|---|---|
| Internal structure | Resizable array | Doubly linked nodes |
get(i) / set(i, e) | \(O(1)\) | \(O(n)\) |
| Append at end | Amortized \(O(1)\) | \(O(1)\) |
| Insert at front | \(O(n)\), due to shifting | \(O(1)\) |
| Insert in middle by index | \(O(n)\), due to shifting | \(O(n)\), due to traversal |
| Remove first element | \(O(n)\), due to shifting | \(O(1)\) |
| Remove last element | \(O(1)\) | \(O(1)\) |
| Full iteration | Usually very cache-friendly | Linear, but follows node links |
| Memory overhead | Generally lower | Generally higher, because every node has links and object overhead |
Implements Deque | No | Yes |
For most general-purpose list tasks, ArrayList is the better starting point. It supports fast indexed access and usually offers efficient traversal with lower per-element overhead.
LinkedList has a narrower advantage when operations concentrate at the ends or when an iterator-driven algorithm removes elements while traversing. Even then, ArrayDeque is often a better queue or stack implementation if the full List API is not required.
10. Choosing Between LinkedList and ArrayDeque
LinkedList and ArrayDeque can both implement deque-style workflows, but their storage strategies differ.
- LinkedList: allocates a separate node for each element and links nodes together.
- ArrayDeque: stores elements in a resizable array arranged as a circular buffer.
For queue and stack workloads, ArrayDeque is often faster and more memory-efficient because it avoids allocating a node object per element. LinkedList remains useful when the same object specifically needs both List and Deque behavior.
11. When LinkedList Is a Reasonable Choice
Consider LinkedList when at least one of these requirements genuinely matters:
- The same object must provide both the
ListandDequeinterfaces. - The workload makes heavy use of adding and removing at the head or tail.
- An iterator-based algorithm traverses the chain and removes elements as it goes.
Before choosing it, check whether ArrayList or ArrayDeque would meet the requirement with simpler or faster behavior. Theoretical operation complexity is only one part of real performance; memory overhead, cache locality, allocation, and the actual workload also matter.
12. Common Mistakes
- Assuming every insertion is fast. Insertion by index is \(O(n)\) when the node must first be located.
- Using
get(i)in a full indexed loop. This can turn a linear traversal into quadratic work. - Choosing LinkedList solely because “linked lists have fast inserts.” The search for the insertion point can dominate the operation.
- Ignoring memory overhead. Every node carries links and object overhead.
- Using LinkedList automatically for queues or stacks.
ArrayDequeis often a better fit. - Assuming LinkedList has fast lookup by value.
containsand value-based removal generally scan the chain. - Forgetting the difference between empty-deque methods. Methods such as
removeFirst()throw on an empty deque, whilepollFirst()returnsnull.
13. Best Practices
- Prefer
ArrayListfor ordinary ordered collections and frequent indexed reads. - Prefer
ArrayDequefor queue and stack operations when indexedListfunctionality is unnecessary. - Traverse LinkedList with for-each or an iterator rather than repeated
get(i)calls. - Use iterator-based removal when deleting elements during a traversal.
- Evaluate the entire workload rather than relying on the phrase “fast insertion.”
- Treat exact performance ratios and memory estimates as environment-dependent; benchmark representative workloads if performance is important.
- Program to an interface such as
List<E>orDeque<E>when that keeps the code independent of implementation details.
14. Quick Revision
LinkedList<E>is a doubly linked list in Java.- Each node conceptually stores an element, a next reference, and a previous reference.
- The list tracks its first and last nodes and its size.
- LinkedList implements both
List<E>andDeque<E>. - Adding or removing at either end is \(O(1)\).
- Indexed access and indexed insertion/removal are generally \(O(n)\) because the node must be located.
- A full iterator-based traversal is \(O(n)\).
- Repeated
get(i)calls in an indexed loop can produce \(O(n^2)\) total work. - LinkedList uses more per-element memory than ArrayList in typical implementations.
ArrayDequeis often preferred for queue and stack behavior.
15. Conclusion
Java LinkedList provides a doubly linked structure that supports efficient operations at both ends and can be used through either the List or Deque interface. Its strengths are real, but they are specific: indexed access and searching are linear, and insertion is only constant time when the relevant node is already located.
For most ordinary list use cases, ArrayList remains the practical default. For queue and stack workflows, ArrayDeque is often preferable. Understanding these trade-offs makes it easier to choose a collection based on the operations the program actually needs.
