Implement a Stack Using a Linked List

77.8k
0

A stack data structure must be implemented with a singly linked list. Stack follows the Last-In-First-Out property, also called LIFO, where the last inserted value is removed first.

The stack must support insertion at the top, deletion from the top, reading the top value, checking emptiness, and reporting the current size. Each linked list node stores one integer value and a pointer to the next node. A pointer named top must always refer to the current top node of the stack. An empty stack has top = null.

Example 1

Input: push(10), push(20), push(30), peek(), pop(), size()
Output: peek = 30, pop = 30, size = 2
Explanation: Values enter at the top in order 10, 20, 30. The last inserted value 30 is read first and removed first.

Example 2

Input: isEmpty(), pop(), peek()
Output: isEmpty = true, pop = -1, peek = -1
Explanation: An empty stack has no top node. Pop and peek operations return -1 for underflow handling.

Approach

A stack only needs access to the newest value. A linked list already has a natural front position, so the head node can play the role of the stack top. New values can be attached before the current head, and removals can detach the current head.

The small trick is keeping one pointer named top. During push, a new node points to the old top before top moves to the new node. During pop, the answer is saved from top, and top moves to the next node. No traversal is required for either operation.

A size counter is maintained beside the top pointer. The counter allows the size operation to answer in constant time instead of walking through all nodes.

Algorithm

  • Define the Linked List Node:

    • Store the stack value inside the node.

    • Store a pointer to the next node so multiple stack values can be connected.

  • Initialize the Stack:

    • Set the top pointer to null to represent an empty stack.

    • Initialize the stack size as zero to track the total number of stored values.

  • Push Operation:

    • Create a new node containing the incoming value.

    • Connect the new node to the current top node.

    • Update the top pointer to the new node.

    • Increase the stack size by one.

  • Pop Operation:

    • Check whether the stack is empty before removing a value.

    • Store the value present at the top node.

    • Move the top pointer to the next node.

    • Decrease the stack size by one.

    • Return the removed value.

  • Peek Operation:

    • Check whether the stack is empty before accessing the top value.

    • Return the value stored in the top node.

    • Keep the linked-list connections and stack size unchanged.

  • Empty Operation:

    • Check whether the top pointer is null.

    • Return true when no node exists; otherwise, return false.

  • Size Operation:

    • Return the maintained stack-size value.

    • Reuse the updated value because every push and pop operation modifies the size.

  • Return Operation Results:

    • Return the appropriate value from pop, peek, empty, and size operations.

    • Provide a clear result for every stack query.

Dry Run

Stack using Linked List

Stack using Linked List

Solution

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
// Creates one linked list node.
Node(int value) {
data = value;
next = NULL;
}
};
class Solution {
private:
Node* topNode;
int count;
public:
// Initializes an empty linked list stack.
Solution() {
topNode = NULL;
count = 0;
}
// Inserts a value at stack top.
void push(int value) {
Node* newNode = new Node(value);
// New node points to the old top.
// Existing values stay below the new value.
newNode->next = topNode;
// Top moves to the newest node.
topNode = newNode;
// Count grows after one inserted value.
count++;
}
// Removes and returns the top value.
int pop() {
// Empty stack access causes underflow.
if (topNode == NULL) {
return -1;
}
Node* removedNode = topNode;
int removedValue = removedNode->data;
// Next node becomes top after removal.
topNode = topNode->next;
// Count shrinks after one removed value.
count--;
// Removed node memory is released.
delete removedNode;
return removedValue;
}
// Returns the top value without removal.
int peek() {
// Empty stack access has no top value.
if (topNode == NULL) {
return -1;
}
return topNode->data;
}
// Checks whether the stack has no nodes.
bool isEmpty() {
return topNode == NULL;
}
// Returns the number of stored values.
int size() {
return count;
}
};
// Driver code
int main() {
Solution obj;
obj.push(10);
obj.push(20);
obj.push(30);
cout << obj.peek() << endl;
cout << obj.pop() << endl;
cout << obj.peek() << endl;
cout << obj.size() << endl;
cout << (obj.isEmpty() ? "true" : "false") << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(1), because each push, pop, peek, isEmpty, and size operation only accesses the top pointer and the counter.

Space Complexity: O(N), because N stored stack values need N linked list nodes. Each individual operation uses O(1) extra space.

Interview follow-up Questions

Head insertion keeps push in O(1) time. The head node is already available through top, so no traversal is needed before adding a new value.

Stack

Read Similar Blogs

Stack

Sum of Subarray Ranges

Given an integer array nums , define the range of a non-empty contiguous subarray as the maximum element minus the minimum element. Return the sum of the ranges of all non-empty contiguous subarray...

86.8k
Stack

Introduction to Stack

Imagine a stack of plates in a kitchen. Whenever you add a new plate, you place it on the top. When you need a plate, you also take it from the top. You never remove a plate from the middle because...

69.3k
Two PointerStackString

Reverse Every Word in a String

Given a string s , reverse every word individually. The spaces should remain in the same positions, and the order of words should not change. A word is a continuous group of non-space...

83.2k
Comments0