Question 5 of 8: Pointer-based Data Structures

Question 5: Pointer-based Data Structures

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) Stack via a linked list

Approach. The stack's "top" is simply the head of a singly-linked list; pushing prepends a node (O(1), no traversal), and popping removes and returns the head node's data (O(1)).

/* stack.h */
#ifndef STACK_H
#define STACK_H

typedef struct node {
    int data;
    struct node *next;
} node;

void make_empty(void);
int  is_empty(void);
void push(int i);
int  pop(void);

#endif

/* stack.c */
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

static node *top = NULL;

void make_empty(void) {
    while (!is_empty()) pop();     /* frees every remaining node */
}

int is_empty(void) {
    return top == NULL;
}

void push(int i) {
    node *n = (node *) malloc(sizeof(node));
    if (n == NULL) {
        fprintf(stderr, "push: out of memory\n");
        exit(1);
    }
    n->data = i;
    n->next = top;                 /* new node becomes the top */
    top = n;
}

int pop(void) {
    if (is_empty()) {
        fprintf(stderr, "pop: stack is empty\n");
        exit(1);
    }
    node *old_top = top;
    int value = old_top->data;
    top = old_top->next;
    free(old_top);
    return value;
}

(b) Print a singly-linked list in reverse

Approach. Recursion is the natural fit: to print the list in reverse, first recurse to the end of the list, then print each node's data on the way back up the call stack — the call stack itself provides the LIFO reversal, with no explicit stack data structure needed.

void print_reverse(node *head) {
    if (head == NULL) return;         /* base case: past the last node */
    print_reverse(head->next);        /* recurse to the tail first */
    printf("%d\n", head->data);       /* then print on the way back */
}

For a list head → 3 → 7 → 2 → NULL, the recursion descends to NULL (printing nothing), then unwinds printing 2, then 7, then 3 — the correct reverse order.