Course contentsShow
← Computer Science
Lesson 363 of 2,8729. Stacks and QueuesFree lesson

Linked List-Based Stack Implementation

Implement a stack using a linked list where push and pop operate at the head for O(1) performance.

Linked List-Based Stack Implementation

What you'll learn: How to build a stack using a linked list with efficient O(1) push and pop operations.


Why Use a Linked List for a Stack?

You've already seen the array-based stack, which has a fixed capacity (or requires expensive resizing). A linked list-based stack grows and shrinks dynamically without worrying about pre-allocated space or copying elements around.

The key insight: always push and pop at the head of the linked list. The head pointer acts like your "top of stack."


The Core Idea

Think of your linked list as a tower of blocks where you can only touch the top block:

  • Push: Create a new node and make it the new head (it points to the old head). O(1) time.
  • Pop: Remove the head node and update the head pointer to the next node. O(1) time.
  • Peek: Just read the data in the head node without removing it. O(1) time.

Because you only manipulate the head pointer, every operation is constant time—no traversal needed!


Why the Head, Not the Tail?

If you tried to pop from the tail of a singly linked list, you'd need to traverse the entire list to find the second-to-last node (O(n)). But removing from the head? Instant. You just update one pointer.


Structure Overview

You maintain:

  • A head pointer (the top of your stack)
  • Optionally, a size counter

Push and pop manipulate only the head, keeping the linked list acting exactly like a stack: Last In, First Out (LIFO).


Key Takeaway: A linked list-based stack uses the head as the top of the stack, making push and pop O(1) operations with dynamic memory that grows as needed.