Linked Implementation of Stacks — Data Structures

Alright! 😊 Let’s talk about a very practical and easy-to-grasp concept — Linked Implementation of Stacks — one of the simplest yet smartest ways to manage data in memory.

We’ll go step-by-step so it feels like you’re learning this from a friendly teacher who wants you to actually understand what’s happening, not just memorize it.

---

🧠 First, a Quick Recall: What is a Stack?

Before we jump into the “linked implementation,” let’s remind ourselves what a stack is.

A stack is a data structure that works on the principle of LIFO – Last In, First Out.
Think of it like a stack of plates in a cafeteria —
you add (push) new plates on top, and when you need one, you take (pop) from the top.

So the topmost plate is always the one that gets used first!

---

💾 Two Ways to Implement a Stack

A stack can be built in two main ways:

1. Using an array (called Array Implementation)
2. Using a linked list (called Linked Implementation)

Array implementation is simple but has a problem — you must decide the size beforehand.
Once it’s full, you can’t push more elements unless you create a bigger array.

That’s where linked implementation comes to the rescue!

---

⚙️ What is Linked Implementation?

In linked implementation, we use a linked list to store stack elements instead of an array.
Each element is stored in a node, and every node has two parts:

• Data field – to store the actual value.
• Pointer (or link) – to store the address of the next node.

We also keep a special pointer called TOP, which always points to the top node of the stack.

---

🧩 Structure of a Node

Each node looks like this:

+--------+-----------+
|  Data  |   Next    |
+--------+-----------+

And the TOP pointer points to the most recently added node.

---

🧱 Diagram of a Linked Stack

Here’s a simple diagram to visualize how it looks:

        TOP
         ↓
+--------+-----------+     +--------+-----------+     +--------+-----------+
|   30   |    •----> | --> |   20   |    •----> | --> |   10   |   NULL    |
+--------+-----------+     +--------+-----------+     +--------+-----------+

• The TOP points to 30, which is the most recent item pushed.
• Each node links to the one below it.
• The last node (bottom of the stack) points to NULL, showing the end of the list.

---

🧮 Operations on a Linked Stack

Let’s walk through the two main stack operations — Push and Pop — using this linked structure.

---

🔹 1. PUSH Operation (Insert an element)

To push an element means to add it on top of the stack.

Steps:

1. Create a new node.
2. Store the new element in its data part.
3. Link the new node to the current TOP node.
4. Update TOP to point to the new node.

Example:
If TOP points to 30 and we push 40, the new node (40) becomes the top.

Before Push: TOP → 30  
After Push:
        TOP
         ↓
+--------+-----------+     +--------+-----------+     +--------+-----------+
|   40   |    •----> | --> |   30   |    •----> | --> |   20   |   NULL    |
+--------+-----------+     +--------+-----------+     +--------+-----------+

---

🔹 2. POP Operation (Remove an element)

To pop an element means to remove it from the top of the stack.

Steps:

1. Check if the stack is empty (TOP = NULL). If yes, display “Underflow”.
2. Store the address of TOP in a temporary pointer.
3. Move TOP to the next node.
4. Free the memory of the old top node.

Example:
If we pop from the stack above, the node with 40 will be deleted, and TOP will now point to 30.

Before Pop:
TOP → 40 → 30 → 20 → NULL

After Pop:
TOP → 30 → 20 → NULL

---

🧠 Other Operations

Besides push and pop, we can also:

• Peek/Top: Show the element at the top without removing it.
• isEmpty: Check if the stack is empty (TOP == NULL).
• Display: Print all stack elements from top to bottom.

---

💡 Why Use Linked Implementation?

Let’s see why this approach is so powerful compared to using arrays:

Feature	Array Stack	Linked Stack
Size	Fixed	Dynamic (grows and shrinks as needed)
Memory use	May waste space	Efficient (allocates as needed)
Overflow	Possible when full	Almost impossible unless memory is exhausted
Implementation	Simpler	Slightly complex but flexible

So, a linked stack gives you freedom and flexibility — it can grow as your program demands, without worrying about size limits.

---

🧾 Example in C-like Pseudocode

Let’s look at how we might write this in simple pseudocode:

struct Node {
    int data;
    struct Node* next;
};

struct Node* TOP = NULL;

void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = TOP;
    TOP = newNode;
}

void pop() {
    if (TOP == NULL)
        printf("Stack Underflow");
    else {
        struct Node* temp = TOP;
        TOP = TOP->next;
        free(temp);
    }
}

This shows how each new element is linked dynamically, without any fixed array size.

---

🌍 Real-Life Analogy

Think of a linked stack like a stack of boxes where each box has a string attached to the one below it.
Whenever you add a new box (push), you tie its string to the previous top box.
When you remove a box (pop), you just untie the top one and move the string to the next.

You can keep adding boxes forever — as long as you have space!

---

🧩 Summary Table

Operation	Description	Time Complexity
Push	Add an element to the top	O(1)
Pop	Remove an element from the top	O(1)
Peek	Return the top element	O(1)
isEmpty	Check if stack is empty	O(1)

---