Using Java LinkedList as a Stack

When you need LIFO (last-in, first-out) behavior in Java, the Stack class is a familiar choice, but it carries legacy baggage. Using LinkedList as a stack is a common alternative that gives you a fully featured stack without inheriting from Vector. LinkedList implements both List and Deque, and the Deque interface defines stack operations such as push, pop, and peek. This article explains how to use LinkedList as a stack, compares it with the dedicated Stack class, and covers the performance and design tradeoffs to consider.

Stack Operations on LinkedList

The Deque interface, which LinkedList implements, provides the methods you need for stack behavior. The push(E e) method adds an element to the head of the deque, pop() removes and returns the head, and peek() retrieves the head without removing it. Because LinkedList implements Deque, you can assign a LinkedList instance to a Deque variable and work with the stack-style operations.

Deque<String> stack = new LinkedList<>();
stack.push("first");
stack.push("second");
stack.push("third");

String top = stack.peek();   // "third"
String removed = stack.pop(); // "third"

The push method is equivalent to addFirst, and pop is equivalent to removeFirst. This means the stack is implemented at the front of the list, which is efficient for a doubly linked list because both ends are directly accessible. Each operation runs in constant time, O(1), regardless of the number of elements.

LinkedList vs. the Legacy Stack Class

Java's Stack class has been around since JDK 1.0 and extends Vector. That inheritance brings several issues. First, Stack's methods are synchronized, which can add overhead in single-threaded contexts. Second, because it inherits from Vector, you can call List methods like add(int, E) or get(int) on a Stack, violating the strict LIFO contract. The Deque interface, on the other hand, explicitly defines stack operations and does not expose positional access methods.

If you need a thread-safe stack, use ConcurrentLinkedDeque or synchronize an ArrayDeque externally rather than relying on the legacy Stack class. For single-threaded code, LinkedList or ArrayDeque are both better choices than Stack.

Performance and Memory Considerations

LinkedList stores each element in a separate node object that contains references to the previous and next nodes. This has two consequences. First, memory overhead is higher than an array-based structure like ArrayDeque or Stack (which is backed by an array). Each node consumes additional bytes for the object header and two references. Second, node allocation happens on every push, which can increase garbage collection pressure compared to an array that occasionally resizes.

However, push and pop on a LinkedList are true O(1) operations because the head node is directly accessible. In contrast, ArrayDeque also offers O(1) push/pop but uses a circular array that may need to resize when full. The resize operation is amortized O(1), but it can cause occasional latency spikes. LinkedList never needs to resize, so its per-operation time is more predictable.

If you are dealing with a large number of elements and memory is a concern, ArrayDeque is usually more compact. If you need to frequently insert or remove elements in the middle of the collection in addition to stack operations, LinkedList provides that flexibility without the cost of shifting elements. But for a pure stack, ArrayDeque is often the better default.

When to Use LinkedList as a Stack

Choosing LinkedList over ArrayDeque or Stack depends on your specific requirements. Use LinkedList when you need a stack that also supports other list operations, such as iterating in either direction, removing elements from the middle, or inserting at arbitrary positions. Because LinkedList implements List, you can pass it to methods that expect a List while still using it as a stack.

Use ArrayDeque when you only need stack or queue behavior and want lower memory overhead and better cache locality. The array-based implementation is generally faster for sequential access because it avoids pointer chasing. The Stack class should be avoided in new code unless you are maintaining legacy systems that already depend on it.

A practical pattern is to declare the variable as Deque and instantiate it with LinkedList or ArrayDeque depending on your needs. This keeps the stack contract explicit and allows you to swap implementations without changing the calling code.

Deque<Integer> stack = new LinkedList<>();
// Deque<Integer> stack = new ArrayDeque<>();

Common Pitfalls When Using LinkedList as a Stack

One mistake is using add and remove instead of push and pop. The add(E e) method on a Deque adds to the tail, not the head. If you use add to insert elements and pop to remove them, pop removes from the head, so the collection behaves like a queue rather than a stack. Use push for adding and pop for removing when you intend stack semantics.

Another pitfall is assuming LinkedList is thread-safe. It is not. If multiple threads access the same stack, you must synchronize externally or use a concurrent implementation like ConcurrentLinkedDeque. The legacy Stack class is synchronized, but that synchronization is often coarse and does not protect compound operations such as if (!stack.isEmpty()) stack.pop(). You still need your own locking for atomicity.

Finally, be careful with null elements. LinkedList allows nulls, but if you use peek and get null, you cannot distinguish between an empty stack and a stack whose top element is null. For that reason, many stack implementations forbid null elements. If you need to allow nulls, use a sentinel or check isEmpty() before peek.

Choosing the Right Stack Implementation for Your Use Case

In modern Java, the recommended way to implement a stack is to use ArrayDeque for most scenarios because it offers good performance and low memory overhead. However, LinkedList is a legitimate choice when you need the additional flexibility of a doubly linked list. The decision should be based on whether you need list-like flexibility, middle insertion, or memory efficiency.

If you are writing a library that exposes a stack, define the parameter type as Deque and let the caller choose the implementation. This follows the principle of programming to interfaces and gives you the freedom to change the underlying data structure without breaking clients. Using a LinkedList as a stack is particularly useful when you already have a LinkedList instance and want to reuse it for stack operations without copying data.

For example, you might have a LinkedList that holds a history of user actions. You can treat it as a stack to undo the most recent action, then still iterate over the list to display the full history. This dual use is a strong reason to choose LinkedList over ArrayDeque, which does not implement List.

The Impact of Resizing on Stack Behavior

When using an array-based stack like ArrayDeque, resizing is an internal operation that copies elements to a larger array. This copy is O(n) and can cause a temporary pause. In contrast, LinkedList never resizes; each push allocates a new node, and each pop removes a node that becomes eligible for garbage collection. This makes the per-operation time more consistent, which can be important in real-time systems or when you need predictable latency.

However, node allocation also means more frequent garbage collection. If you are pushing and popping millions of elements in a tight loop, the allocation overhead can be significant. In such cases, an array-based stack that reuses the backing array is often faster. The tradeoff is between predictable per-operation time (LinkedList) and lower overall allocation overhead (ArrayDeque).

You can mitigate allocation overhead with LinkedList by pooling nodes, but that adds complexity and is rarely worth it unless profiling shows a clear bottleneck. For most applications, the difference is negligible, and readability should guide your choice.

Edge Cases: Empty Stack and Null Elements

Calling pop() on an empty LinkedList throws NoSuchElementException. peek() is different: it returns null when the deque is empty. The same distinction applies to ArrayDeque; the legacy Stack class throws EmptyStackException from both pop() and peek(). To avoid exceptions, check isEmpty() before popping in code that may encounter an empty stack.

Null elements are allowed in LinkedList, but they can cause ambiguity. Because peek() returns null for an empty deque, a null top element is indistinguishable from an empty stack. If your application uses null as a meaningful value, check isEmpty() before peek() or avoid nulls altogether. If you want a stack that rejects nulls, ArrayDeque does so out of the box; wrapping a LinkedList and rejecting nulls in every insertion method is another option, though usually unnecessary.

Using LinkedList as a Stack in Recursive Algorithms

A common use case for a custom stack is replacing recursion to avoid stack overflow errors. For example, depth-first search on a tree can be implemented iteratively with an explicit stack. Using LinkedList as the stack is straightforward and avoids the Java call-stack limit.

Deque<TreeNode> stack = new LinkedList<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    // process node
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
}

This pattern is common in graph traversal and expression evaluation. The LinkedList implementation works fine, but ArrayDeque would be equally suitable and often more memory-efficient. The choice does not affect the algorithm's correctness, only its performance profile.

If you are dealing with very deep traversals, the number of elements in the stack can grow large. LinkedList's per-node overhead becomes more pronounced as the stack grows. For millions of nodes, ArrayDeque will typically use significantly less memory. Measure your specific workload if memory is a concern.

Maintainability and Code Clarity

Using Deque as the declared type, regardless of the concrete class, makes your code clearer because it signals stack semantics. The push and pop method names are self-documenting. In contrast, using LinkedList directly and calling addFirst and removeFirst is less obvious. Prefer the interface type in variable declarations and method parameters.

When you need to pass the stack to a method that expects a List, you can still do so if the concrete type is LinkedList, but you lose the stack contract. That is a tradeoff: you gain flexibility but risk accidental misuse. If you want to keep LIFO intent clear, use Deque as the declared type and keep a separate LinkedList reference only when list behavior is explicitly required.

In summary, using a LinkedList as a stack is a valid pattern that gives you a deque-based stack with O(1) push/pop and the ability to use list operations when needed. It is not always the best choice, but it is a solid option when you need the combined capabilities of a list and a stack. For pure stack scenarios, ArrayDeque is usually more efficient, and the legacy Stack class should be avoided. Understanding these tradeoffs lets you choose the right data structure for your specific requirements.