Question 4 of 8: Pointer-based Data Structures — Sorted Doubly Linked List

Question 4: Pointer-based Data Structures — Sorted Doubly Linked List (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 doubly linked list node with an int payload and prev/next pointers, always maintained in ascending sorted order by data.

Find. Insertion and deletion functions that preserve sort order and handle an empty list correctly, plus a function that removes adjacent duplicate values in place.

Approach. Both functions operate on a plain singly-directed scan (using next) to find the insertion or deletion point, then splice by updating up to four pointers (the new/old node's own prev/next and its neighbours' matching fields); the only case needing special handling is when the affected node is the current head.

(a) dlinked_add and dlinked_del (10 marks)

1. Insertion: find the first node not smaller than the new value. Scanning forward from head for the first node whose data is >= new->data gives the node the new element must be inserted before; if no such node exists, it goes at the tail. Three cases fall out of this rule: the list is empty, the insertion point is the head, or the insertion point is any other node (including "after the last node," treated by the scan naturally finding no successor).

   #include <stddef.h>   /* NULL */
   #include <stdlib.h>   /* free(), used by dlinked_del() and del_dupl() */
   
   typedef struct element {
       int data;
       struct element *prev;
       struct element *next;
   } ELEMENT;
   
   /* Returns the (possibly updated) head of the list. */
   ELEMENT *dlinked_add(ELEMENT *head, ELEMENT *new)
   {
       ELEMENT *node;
   
       new->prev = new->next = NULL;
   
       if (head == NULL)                       /* empty list */
           return new;
   
       if (new->data <= head->data) {          /* insert before the current head */
           new->next = head;
           head->prev = new;
           return new;                          /* new is the new head */
       }
   
       node = head;
       while (node->next != NULL && node->next->data < new->data)
           node = node->next;
   
       new->next = node->next;                 /* may be NULL: inserting at the tail */
       new->prev = node;
       if (node->next != NULL)
           node->next->prev = new;
       node->next = new;
   
       return head;                             /* head is unchanged */
   }

2. Deletion: linear search, then splice around the found node. Because duplicates may exist, the first matching node encountered by the forward scan is the one removed, satisfying "delete only one."

   /* Returns the (possibly updated) head, or NULL if no node has this data. */
   ELEMENT *dlinked_del(ELEMENT *head, int data)
   {
       ELEMENT *node = head;
   
       while (node != NULL && node->data != data)
           node = node->next;
   
       if (node == NULL)
           return NULL;                         /* not found, per the spec */
   
       if (node->prev != NULL)
           node->prev->next = node->next;
       else
           head = node->next;                   /* deleting the head */
   
       if (node->next != NULL)
           node->next->prev = node->prev;
   
       free(node);
       return head;
   }

3. Confirm on a worked sequence. Inserting 5, 1, 3, 3, 1, 4 one at a time (each insertion re-running the scan above) builds 1, 1, 3, 3, 4, 5. Deleting data = 3 removes the first node holding 3 (leaving one 3 behind), giving 1, 1, 3, 4, 5; every prev/next pair. $$\boxed{\text{after 6 inserts and one delete(3): } 1,1,3,4,5}$$

(b) del_dupl (10 marks)

1. Exploit the fact that the list stays sorted. Because duplicates are equal values, and the list is always kept in sorted order by both functions above, any two nodes with equal data must be adjacent — so a single forward pass comparing each node to its immediate successor finds every duplicate, with no need to search the whole list per node.
2. Write the function. When node and node->next match, the successor is unlinked and freed while node itself stays put (so a run of three or more equal values collapses correctly, one deletion at a time, without ever advancing past the surviving copy).

   void del_dupl(ELEMENT *head)
   {
       ELEMENT *node = head;
       ELEMENT *dup;
   
       if (head == NULL) return;               /* empty list: nothing to do */
   
       while (node != NULL && node->next != NULL) {
           if (node->data == node->next->data) {
               dup = node->next;
               node->next = dup->next;
               if (dup->next != NULL)
                   dup->next->prev = node;
               free(dup);
               /* do NOT advance node: it may equal the next successor too */
           } else {
               node = node->next;
           }
       }
   }

3. Confirm on the same list. Running del_dupl on 1, 1, 3, 4, 5 removes the second 1, leaving 1, 3, 4, 5, with no adjacent equal pair remaining and every link re-checked for consistency. $$\boxed{\text{del\_dupl}(1,1,3,4,5) = 1,3,4,5}$$