Question 1 of 8: Linked Lists

Question 1: Linked Lists (10 marks: 4, 3, 3)

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.

Approach. All three variants share one node type; only the placement rule inside Insert and the pointer bookkeeping inside Delete change. Both functions return 1 on success and 0 when nothing could be done (delete target not found).

1. Singly-linked list (unordered) — 4 marks

Insertion is cheapest at the front (O(1), no traversal needed); deletion removes the first node whose val matches, relinking the previous node's next around it.

int Insert(item** head, int insertMe) {
    item* n = (item*) malloc(sizeof(item));
    if (n == NULL) return 0;           /* allocation failed */
    n->val  = insertMe;
    n->next = *head;                   /* new node becomes the first node */
    *head = n;
    return 1;
}

int Delete(item** head, int deleteMe) {
    item *cur = *head, *prev = NULL;
    while (cur != NULL && cur->val != deleteMe) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return 0;         /* deleteMe not present */
    if (prev == NULL) *head = cur->next;   /* removing the head node */
    else prev->next = cur->next;
    free(cur);
    return 1;
}

2. Sorted (ascending) linked list — 3 marks

Insert must walk forward only until the next node's value would exceed insertMe, so the new node is spliced in at the correct position (still O(1) once the position is found for the head case, O(n) worst case overall). Delete is unchanged in structure from the singly-linked case — the list stays sorted automatically because removal never reorders elements.

int Insert(item** head, int insertMe) {
    item* n = (item*) malloc(sizeof(item));
    if (n == NULL) return 0;
    n->val = insertMe;
    if (*head == NULL || (*head)->val >= insertMe) {
        n->next = *head;               /* smaller than (or equal to) current first */
        *head = n;
        return 1;
    }
    item* cur = *head;
    while (cur->next != NULL && cur->next->val < insertMe)
        cur = cur->next;
    n->next = cur->next;
    cur->next = n;
    return 1;
}

int Delete(item** head, int deleteMe) {
    item *cur = *head, *prev = NULL;
    while (cur != NULL && cur->val != deleteMe) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return 0;
    if (prev == NULL) *head = cur->next;
    else prev->next = cur->next;
    free(cur);
    return 1;
}

3. Circular linked list — 3 marks

The last node's next points back to the first node instead of NULL, so both functions must special-case the empty list (a single node pointing to itself) and stop the search after one full lap rather than at a NULL sentinel.

int Insert(item** head, int insertMe) {
    item* n = (item*) malloc(sizeof(item));
    if (n == NULL) return 0;
    n->val = insertMe;
    if (*head == NULL) {               /* first node: points to itself */
        n->next = n;
        *head = n;
        return 1;
    }
    n->next = *head;                   /* insert as new head */
    item* last = *head;
    while (last->next != *head) last = last->next;  /* find current tail */
    last->next = n;
    *head = n;
    return 1;
}

int Delete(item** head, int deleteMe) {
    if (*head == NULL) return 0;
    item *cur = *head, *prev = NULL;
    do {
        if (cur->val == deleteMe) {
            if (cur->next == cur) {    /* only node in the list */
                *head = NULL;
            } else {
                if (prev == NULL) {    /* deleting the head: find the tail first */
                    item* last = *head;
                    while (last->next != *head) last = last->next;
                    last->next = cur->next;
                    *head = cur->next;
                } else {
                    prev->next = cur->next;
                }
            }
            free(cur);
            return 1;
        }
        prev = cur;
        cur = cur->next;
    } while (cur != *head);
    return 0;                          /* walked the full ring, not found */
}