Representation of a Stack using a Linked List

Representation of Stack using a Linked List in C++

One of the basic linear user defined data structure that is also very useful to solve problems and implement tons of Graph theory algorithms is Stack. It follows the last in first out model and cann be implemented using LinkedList if you want to get its size changing dynamically. This is anarticle on the Representation of a Stack using a Linked List.

Representation of a stack as a linked list

What is Stack?

Stack is a data structure where you can add any kind of and store then in a LIFO (last in first out) manner.

  • If you want to know about The given stack Data structure in a C++ STL, here it goes: Stack in C++ STL
Representation of a stack as a linked list in C
Representation of a stack as a linked list in C

The Algorithm Goes here: 

So here goes the algorithm about How to use a linked list to implement a stack. It is one of the easiest algorithms, if you know what a linked list is. Here we used the inbuilt STL List (List in C++ STL) as a linked list inside a ‘Stack’ named class, otherwise you can make a class or structure with pointers to make a Linked List.

  • Firstly, This is a LinkedList, where only the last element is visible. So you have only one place open to change in the list, that is the topmost node of the list.
  • So if you want to push values, you have to push them at the back. Only if the list is empty, you can push the first value in the first node.
  • If you want to pop values, only the topmost or the last pushed place is accessible. If the list is empty, no values can be popped, otherwise, the momentary topmost value is to be popped.
  • That is how you can achieve the model of Last in First Out.
  • So Here a class is made with a list member. Then values are added only at the back, same goes for the popping.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

The code to implement this:

Run
#include<bits/stdc++.h>
using namespace std;
class Stack
{
public:

  list < int >L;
  void Push (int i)
  {
    cout << "Pushing the element : " << (i) << endl;
    L.push_back (i);
  }

  int pop ()
  {
    if (L.empty ())
    {
	   cout << "The Stack is empty" << endl;
    }
    int a = L.back ();
    L.pop_back ();
    cout << "Popping the element : " << a << endl;
    return a;
  }

  void Show ()
  {
    cout << "The present Stack is:" << endl;
    for (auto i:L)
       cout << i << " ";
    cout << endl;
  }
};

int main ()
{

  Stack s;
  s.Push (5);
  s.Push (2);
  s.Push (11);

  s.Show ();
  s.pop ();

  s.Push (12);

  s.Show ();
}

Output:

Pushing the element : 5
Pushing the element : 2
Pushing the element : 11
The present Stack is:
5 2 11 
Popping the element : 11
Pushing the element : 12
The present Stack is:
5 2 12

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java

FAQs - Stack using a Linked List

In a linked list-based stack, memory is allocated dynamically during runtime using pointers (e.g., new in C++ or malloc in C). This means the stack can grow as long as the system has free memory, reducing the chances of overflow. In contrast, an array-based stack has a fixed size, so it can overflow even if the system has free memory. However, dynamic allocation comes at the cost of increased overhead and slightly slower performance due to pointer management.

Both implementations provide O(1) time complexity for push() and pop() operations. However, array-based stacks may occasionally face O(n) complexity during dynamic resizing (in languages like Java with ArrayList). Linked list stacks always maintain O(1) time, but at the cost of extra memory for storing pointers and less cache locality, which can slow down operations in practice.

Linked list-based stacks allocate memory for each node individually, which can lead to memory fragmentation if there are frequent allocations and deallocations. Fragmentation can reduce performance over time due to inefficient memory access and increased overhead in memory management. In contrast, array-based stacks allocate memory in contiguous blocks, improving spatial locality and reducing fragmentation.

Linked list-based stacks involve frequent pointer updates (next and top), which are not atomic operations. In a multithreaded environment, this can lead to race conditions, data corruption, or segmentation faults. To mitigate this, developers must use mutex locks, atomic operations, or implement lock-free data structures using CAS (Compare-And-Swap) operations. Ensuring thread safety adds complexity and may reduce performance due to synchronization overhead.

In garbage-collected languages, unreferenced nodes in a linked list stack are cleaned up automatically. However, frequent node allocation and deallocation can trigger the garbage collector more often, potentially leading to GC pauses and degraded performance. Moreover, if references to nodes are not released properly (e.g., through circular references), memory leaks may still occur. Proper nullification of node references is critical for efficient memory usage.