QUESTION 03

Where should a singly linked stack keep its top?

2 marks

Answer

At the head, so push and pop can change the first link without searching for the last node.

Explain a stack implemented using a singly linked list.

5 marks

Answer in brief

A linked stack uses its head pointer as top and allocates one node per pushed item.

Push

Allocate a node and check success before modifying the stack.
Store the value and set new->next to top.
Set top to the new node.

Pop

If top is NULL, report underflow.
Save the current top node and its value.
Move top to old->next.
Free the old owned node and return success with the saved value.

Example

Pushing 10 then 20 creates 20 → 10 → NULL. Pop removes 20 first and leaves 10 as top. Removing the only remaining node makes top NULL. This matches the same LIFO contract as the array implementation.

Capacity and ownership

There is no preset array capacity in this version, but memory is finite and malloc can fail. Calling it unlimited would be incorrect. Every successful push creates owned storage that must later be released by pop or destruction. Read the link before freeing its node.

Complexity

Each operation uses O(1) link work, excluding the allocator’s implementation-dependent cost. A linked stack with n items needs O(n) node storage, including next links. It avoids shifting elements but adds allocation overhead and less predictable physical locality than an array.

Complete C example

main.c

Download main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int push(struct Node **top, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value; node->next = *top; *top = node; return 1;
}
int pop(struct Node **top, int *out)
{
    if (*top == NULL) { return 0; }
    struct Node *old = *top; *out = old->data; *top = old->next; free(old); return 1;
}

int main(void)
{
    struct Node *top = NULL;
    int value;
    if (!push(&top, 10) || !push(&top, 20)) {
        while (pop(&top, &value)) { }
        puts("Allocation failed"); return 1;
    }
    while (pop(&top, &value)) { printf("%d\n", value); }
    return 0;
}

Sample input and output

The example uses values in the code.

Output

20
10