Implement Stack using Linked List - Programming and Data Structures - Computer

Table of Contents
1. Introduction
2. Stack operations
3. Node structure and top pointer
4. Implementation (C++)
5. Sample run (expected output)
6. Time and space complexity
7. Notes, best practices and variations
View more

Introduction

To implement a stack using a singly linked list, we represent the stack as a linked list whose head node is treated as the top of the stack. All stack operations-LIFO (last in, first out) behaviour-are implemented by manipulating the list at its head. In this approach, push and pop operate at the beginning of the linked list so each operation runs in constant time.

In this representation, a top pointer refers to the first node of the linked list. Each node contains a data field and a link (pointer) to the next node. The last node in the list has its link set to NULL. The principal advantage of using a linked list over a fixed-size array is dynamic size: nodes are allocated on the heap as needed, so the stack grows and shrinks at runtime without a static maximum capacity. Array-based stacks impose an upper bound and risk overflow; a linked-list stack can only overflow when the system runs out of memory.

Stack operations

• push(): insert a new element onto the stack; implemented by inserting a new node at the beginning of the linked list.
• pop(): remove and return the top element of the stack; implemented by deleting the first node of the linked list.
• peek() (or top()): return the value of the top element without removing it.
• display(): print all elements of the stack from top to bottom.

Node structure and top pointer

A typical node for a singly linked list based stack contains two fields:

• data: stores the element value (for example, an integer).
• link (or next): pointer to the next node in the list.

The stack maintains a single pointer top that refers to the first node. If top is NULL, the stack is empty.

Push operation

• Create a new node (allocate it on the heap).
• Set the node's data field to the value to be pushed.
• Set the new node's link to the current top node.
• Update top to point to the new node.

Pop operation

• Check if the stack is empty (if top is NULL); if empty, handle underflow (report error or return sentinel).
• Otherwise, save a pointer to the top node in a temporary variable.
• Update top to top->link (the next node).
• Retrieve the data from the removed node if needed and release its memory (delete the node).

Peek operation

• Check if the stack is empty; if empty, handle accordingly.
• Otherwise, return top->data without modifying the list.

Display operation

• Start from a temporary pointer initialized to top.
• Traverse the list following the link field until the pointer becomes NULL.
• Print the data of each node as you traverse; this will show elements from top to bottom.

Implementation (C++)

The following C++ program demonstrates a simple, clear implementation of a stack using a singly linked list. The implementation uses new and delete for dynamic allocation and deallocation.

#include <iostream> #include <cstdlib> using namespace std; class Node { public: int data; Node* link; Node(int n) : data(n), link(nullptr) { } }; class Stack { Node* top; public: Stack() : top(nullptr) { } void push(int data) { Node* temp = new (nothrow) Node(data); if (temp == nullptr) { cout << "
Heap allocation failed: Stack Overflow" << endl; exit(EXIT_FAILURE); } temp->link = top; top = temp; } bool isEmpty() const { return top == nullptr; } int peek() const { if (!isEmpty()) return top->data; cout << "
Stack is empty: cannot perform peek" << endl; exit(EXIT_FAILURE); } void pop() { if (top == nullptr) { cout << "
Stack Underflow" << endl; exit(EXIT_FAILURE); } Node* temp = top; top = top->link; delete temp; } void display() const { if (top == nullptr) { cout << "
Stack is empty" << endl; return; } Node* temp = top; while (temp != nullptr) { cout << temp->data; temp = temp->link; if (temp != nullptr) cout << " -> "; } cout << endl; } }; int main() { Stack s; s.push(11); s.push(22); s.push(33); s.push(44); s.display(); cout << "Top element is " << s.peek() << endl; s.pop(); s.pop(); s.display(); cout << "Top element is " << s.peek() << endl; return 0; }

Sample run (expected output)

44 -> 33 -> 22 -> 11 Top element is 44 22 -> 11 Top element is 22

Time and space complexity

• Time Complexity: O(1) for push(), pop() and peek(), since each operates only at the head of the list and does not traverse it.
• Display() requires O(n) time to traverse and print all n elements.
• Auxiliary Space: O(n) where n is the number of elements currently in the stack; each element requires one node object on the heap.

Notes, best practices and variations

• Use delete to free memory allocated with new; do not mix free() with new.
• For production code, prefer throwing exceptions on errors (for example, in peek() or pop()) or return an optional/flag instead of calling exit().
• Using nothrow with new allows checking for allocation failure without catching exceptions.
• Alternative designs: maintain a size counter for O(1) size() queries; implement stack using templates to support any data type; implement using std::unique_ptr or smart pointers to automate memory management.