Stack and queue built on linked lists

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• How many pointers are written when inserting into the middle of a doubly linked list? from Lesson 3.4.3
• Which list operations are O(1) with only a head pointer? from Lesson 3.4.1
• In the array stack, what are the empty and full tests? from Lesson 3.2.1

1 · The Hook

🎣

The array stack and the array queue had a fixed capacity: one more item than planned and they overflowed. Built from linked nodes, they grow as long as memory lasts. The design question is only: which end of the list does each operation use, so that every operation stays O(1)?

2 · Predict First

🤔

A stack is built on a singly linked list with only a head pointer. Should push add at the head or at the tail? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

At the head: inserting and deleting at the head are both O(1). Popping from the tail would need the second-to-last node, O(n).

Linked stack

The head is the top. push = insert at head; pop = delete at head; empty when top == NULL. No overflow (until malloc fails).

struct node *top = NULL;

void push(int x)
{
    struct node *n = newNode(x);
    n->next = top;
    top = n;
}

int pop(void)
{
    struct node *t = top;
    int x;
    if (top == NULL) { printf("underflow "); return -1; }
    x = t->data;
    top = t->next;
    free(t);
    return x;
}

int main(void)
{
    push(1); push(2); push(3);
    printf("%d ", pop());
    push(4);
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop());
    pop();
    printf("\n");
    return 0;
}

Output

3 4 2 1 underflow

Linked queue

Keep front (head, where we delete) and rear (last node, where we insert). Enqueue: link the new node after rear; dequeue: remove the front node. Special cases: enqueue into an empty queue sets both pointers; dequeuing the last item must reset rear to NULL.

struct node *front = NULL, *rear = NULL;

void enqueue(int x)
{
    struct node *n = newNode(x);
    if (rear == NULL) front = rear = n;   /* first item */
    else { rear->next = n; rear = n; }
}

int dequeue(void)
{
    struct node *t = front;
    int x;
    if (front == NULL) { printf("empty "); return -1; }
    x = t->data;
    front = front->next;
    if (front == NULL) rear = NULL;       /* queue became empty */
    free(t);
    return x;
}

int main(void)
{
    enqueue(10); enqueue(20); enqueue(30);
    printf("%d ", dequeue());
    enqueue(40);
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    dequeue();
    printf("\n");
    return 0;
}

Output

10 20 30 40 empty

Why not insert at the front and delete at the rear? Deleting the last node of a singly linked list is O(n).

Array vs linked implementations

4 · Visual

Linked stack after push 1, 2, 3, pop, push 4: the top is the head.

Linked queue after enqueue 10, 20, 30, dequeue, enqueue 40: delete at front, insert after rear.

Linked queue, special cases:

enqueue into empty:   front = rear = n
dequeue last item:    front = front->next (= NULL)  ->  also set rear = NULL
                      otherwise rear would dangle on the freed node

The two special cases of the linked queue.

5 · Worked Examples

Example 1 Easy

What does this print?

struct node *top = NULL;

void push(int x)
{
    struct node *n = newNode(x);
    n->next = top;
    top = n;
}

int pop(void)
{
    struct node *t = top;
    int x;
    if (top == NULL) { printf("underflow "); return -1; }
    x = t->data;
    top = t->next;
    free(t);
    return x;
}

int main(void)
{
    push(1); push(2); push(3);
    printf("%d ", pop());
    push(4);
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop());
    pop();
    printf("\n");
    return 0;
}

Solution

push 1, 2, 3; pop → 3; push 4; pops → 4, 2, 1; the next pop underflows.

Output

3 4 2 1 underflow

Example 2 Medium

What does this print?

struct node *front = NULL, *rear = NULL;

void enqueue(int x)
{
    struct node *n = newNode(x);
    if (rear == NULL) front = rear = n;   /* first item */
    else { rear->next = n; rear = n; }
}

int dequeue(void)
{
    struct node *t = front;
    int x;
    if (front == NULL) { printf("empty "); return -1; }
    x = t->data;
    front = front->next;
    if (front == NULL) rear = NULL;       /* queue became empty */
    free(t);
    return x;
}

int main(void)
{
    enqueue(10); enqueue(20); enqueue(30);
    printf("%d ", dequeue());
    enqueue(40);
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    dequeue();
    printf("\n");
    return 0;
}

Solution

FIFO: 10, then 20, 30, 40; the fifth dequeue finds an empty queue.

Output

10 20 30 40 empty

Example 3 GATE

A queue is implemented with a singly linked list, insertion at the head and deletion at the tail, keeping both a head and a tail pointer. What are the costs of enqueue and dequeue?

Solution

Enqueue at the head: O(1). Dequeue at the tail: the new tail is the node before the old tail, found only by walking from the head: O(n). Swapping the ends (insert at tail, delete at head) makes both O(1).

6 · GATE Traps

⚠️

• Linked stack: push and pop at the head, never at the tail.
• Linked queue: insert at the rear, delete at the front.
• Dequeuing the last item must also set rear = NULL.
• Enqueue into an empty queue must set front as well as rear.
• A linked structure can still fail when malloc returns NULL; it just has no fixed capacity.

8 · Memory Hook

🧠

“Stacks live at the head; queues enter at the tail and leave at the head.”

9 · Connect the Dots

Phase 3 has now built every linear structure from both arrays and linked nodes. GATE tests linked lists mostly by giving a short function full of p->next->next and asking what list or value results. Next lesson answers: how do we trace such pointer code quickly and without mistakes?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markDesign

For a linked stack with only a head pointer, push should:

• (A) insert at the head
• (B) replace the head’s data
• (C) insert in the middle
• (D) insert at the tail

Q2MCQ2 marksOutput

What does this print?

struct node *front = NULL, *rear = NULL;

void enqueue(int x)
{
    struct node *n = newNode(x);
    if (rear == NULL) front = rear = n;   /* first item */
    else { rear->next = n; rear = n; }
}

int dequeue(void)
{
    struct node *t = front;
    int x;
    if (front == NULL) { printf("empty "); return -1; }
    x = t->data;
    front = front->next;
    if (front == NULL) rear = NULL;       /* queue became empty */
    free(t);
    return x;
}

int main(void)
{
    enqueue(10); enqueue(20); enqueue(30);
    printf("%d ", dequeue());
    enqueue(40);
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    dequeue();
    printf("\n");
    return 0;
}

• (A) 10 20 30 40 empty
• (B) 40 30 20 10 empty
• (C) 30 40 20 10 empty
• (D) 10 20 30 40

Q3MCQ1 markSpecial case

In a linked queue, after dequeuing the only remaining item, which pointer must also be reset?

• (A) none
• (B) rear
• (C) both front->next and rear
• (D) front

Q4MCQ2 marksOutput

What does this print?

struct node *top = NULL;

void push(int x)
{
    struct node *n = newNode(x);
    n->next = top;
    top = n;
}

int pop(void)
{
    struct node *t = top;
    int x;
    if (top == NULL) { printf("underflow "); return -1; }
    x = t->data;
    top = t->next;
    free(t);
    return x;
}

int main(void)
{
    push(1); push(2); push(3);
    printf("%d ", pop());
    push(4);
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop());
    pop();
    printf("\n");
    return 0;
}

• (A) 3 4 2 1
• (B) 3 4 2 1 underflow
• (C) 3 2 1 4 underflow
• (D) 1 2 3 4 underflow

Q5MSQ1 markComparison

Compared with array versions, linked stacks and queues:

• (A) make each operation O(n)
• (B) allocate memory per item
• (C) use extra memory for pointers
• (D) have no fixed capacity

11 · Rule Card

• Linked stack: top = head; push/pop at head; empty top == NULL.
• Linked queue: front = head (delete), rear = last (insert); both O(1).
• Empty enqueue sets front = rear = n; last dequeue sets rear = NULL.
• No fixed capacity; extra pointer per item; malloc/free per operation.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

linked stacklinked queuefront and rear pointers (linked)

13 · Answer Vault