Stack Implementation Using Linked List

Implementing stack operations using a linked list

Implementation

1

Push Operation

  • Create a new node with the given data.
  • Set the next pointer of the new node to the current top.
  • Update top to point to the new node.
    • Increment len by 1.
2

Pop Operation

  • Check if top is NULL (stack is empty).
  • If true, print "Stack is empty" and exit.

Otherwise:

  • Store the current top node in a temporary variable (del).

  • Update top to point to top->next (the next node).

  • Free the memory of the node stored in del.

  • Decrement len by 1.

3

Peek Operation

  • Check if the stack is empty (top == NULL).

  • If true, print "Stack is empty" and return -1.

  • Otherwise, return the data value of the top node.

4

IsEmpty Operation

  • Check if top == NULL.

  • Return true if the stack is empty, otherwise false.

5

Size Operation

  • Return the value of len.

Coding Implementation

//stackusinglinkedlist.cpp
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data)
{
    this->data = data;
    this->next = NULL;
}
};
class Stack
{
Node *top;
int len;

public:
Stack()
{
    len = 0;
    top = NULL;
}
void push(int data)
{
    Node *temp = new Node(data);
    temp->next = top;
    top = temp;
    len++;
}
void pop()
{
    if(isEmpty()){
        cout<<"Stack Underflow"<<endl;
        return;
    }
    Node *del = top;
    top = top->next;
    delete del;
    len--;
}
bool isEmpty()
{
    return (top == NULL);
}
int peek()
{
    if (isEmpty())
    {
        cout << "Stack is Empty" << endl;
        return -1;
    }
    return top->data;
}
int size(){
    return this->len;
}
};
int main()
{
Stack st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
cout<<st.peek()<<endl;
cout<<st.size()<<endl;
st.pop();
cout<<st.peek()<<endl;
cout<<st.size()<<endl;
st.pop();
st.pop();
st.pop();
st.pop();
}

Comparison of Stack Implementation Using Array and Linked List

FeatureArrayLinked List
Memory AllocationRequires a contiguous block of memory.Uses non-contiguous memory; nodes allocated dynamically.
SizeFixed size (needs resizing for dynamic growth).Dynamic size; no resizing needed.
Memory EfficiencyCan waste space if resized or over-allocated.Allocates memory exactly as needed.
Push Operation (Insert) O(1), unless resizing is needed. O(1), always efficient.
Pop Operation (Delete) O(1), straightforward. O(1), straightforward.