Question 7 of 9: Pointer-Based Data Structures — Doubly Linked List and a Stack Module

Question 7: Pointer-Based Data Structures — Doubly Linked List and a Stack Module (20 marks: (a) 10, (b) 10)

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.

Given. (a) The ELEMENT doubly-linked-node type (data/prev/next) and the function signature void del_dupl(ELEMENT *head). (b) A stack module interface (make_empty, is_empty, push, pop) over a linked list of nodes with a single top pointer.

Find. (a) A function removing every later occurrence of a value already seen earlier in the list, safe on an empty list. (b) A complete linked-list-backed implementation of the four stack operations.

Approach. (a) For each node in turn, scan the remainder of the list and unlink (relink prev/next, free) every later node whose data matches it, so only the first occurrence of each value survives. (b) Push/pop only ever touch the single top pointer, so a classic singly-linked "insert/remove at head" pattern gives $O(1)$ push and pop.

(a) del_dupl on a doubly linked list (10 marks)

1. Design the outer/inner scan. For each node p from head onward, walk every node q after p; whenever q->data == p->data, unlink q by pointing q->prev->next at q->next and (if it exists) q->next->prev at q->prev, then free q and continue from the node that used to follow it.
2. Write the function.

   #include <stdlib.h>
   
   typedef struct element {
       int data;
       struct element *prev;
       struct element *next;
   } ELEMENT;
   
   /* delete duplicate valued elements in the list pointed to by head */
   void del_dupl(ELEMENT *head)
   {
       ELEMENT *p, *q, *next_q;
   
       if (head == NULL) return;          /* empty list: nothing to do */
   
       for (p = head; p != NULL; p = p->next) {
           q = p->next;
           while (q != NULL) {
               next_q = q->next;
               if (q->data == p->data) {
                   q->prev->next = q->next;
                   if (q->next != NULL)
                       q->next->prev = q->prev;
                   free(q);
               }
               q = next_q;
           }
       }
   }
   

3. Confirm on a worked example and the empty-list case. List $3,1,2,3,1$: with $p$ at the first node (value 3), the scan removes the later node valued 3; with $p$ at the second node (value 1), it removes the later node valued 1; $p$ then reaches the remaining nodes (2) with nothing left to remove. Result: $3,1,2$, each value kept once, in original order. Calling del_dupl(NULL) returns immediately via the guard clause, satisfying the "must work correctly for empty lists" requirement. $$\boxed{3,1,2,3,1 \ \longrightarrow\ 3,1,2}$$

(b) Stack module on a linked list (10 marks)

1. Fix the two defects in the printed declaration before implementing. The printed typedef struct { int data; node *next; } node; does not compile — node is used as a member type before the typedef that introduces the name has completed, so the type must be given a tag (struct node) and referenced by that tag inside itself. The header guard's closing #end if is also a slip for #endif (a two-word "#end if" is not valid C preprocessor syntax). Both are flagged and corrected below.
2. Write the module (stack.h / stack.c).

   /* stack.h */
   #ifndef STACK_H
   #define STACK_H
   
   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"
   
   struct node {
       int data;
       struct node *next;
   };
   
   static struct node *top = NULL;
   
   void make_empty(void)
   {
       while (!is_empty()) pop();     /* free any existing nodes */
   }
   
   int is_empty(void)
   {
       return top == NULL;
   }
   
   void push(int i)
   {
       struct node *n = malloc(sizeof(struct node));
       n->data = i;
       n->next = top;
       top = n;
   }
   
   int pop(void)
   {
       struct node *old_top = top;
       int val = old_top->data;       /* caller must ensure !is_empty() first */
       top = old_top->next;
       free(old_top);
       return val;
   }
   

3. Confirm with a worked sequence. Starting empty: push(5) → top=5; push(3) → top=3, then 5; pop() returns 3 (top=5); push(7) → top=7, then 5; pop() returns 7; pop() returns 5; is_empty() now returns true — matching LIFO order throughout. $$\boxed{\text{push }5,3\ \Rightarrow\ \text{pop}=3;\ \text{push }7\ \Rightarrow\ \text{pop}=7;\ \text{pop}=5}$$