Algorithm

1. Set current = head and previous = NULL. Keep last_match and last_previous as NULL.
2. Visit each node. When its key matches, save current and previous as the latest match.
3. Advance previous and current until the scan ends.
4. If no match was saved, report Not found.
5. Bypass the saved node using its saved predecessor, or update head when it was the head. Free the saved node.

Example

For IDs 7, 2, 7, 3 and key 7, the first saved match is the head. At the third node, the saved pair is replaced. After scanning the whole list, bypass the third node. The result is 7, 2, 3, preserving the earlier occurrence.

Boundary cases

An empty list and an absent key produce no deletion. A single matching node is removed and head becomes NULL. If the last occurrence is also the last node, its predecessor’s next becomes NULL. A representation with a tail pointer must update that tail too.

Interpretation

The paper uses a student scenario without a full record schema. The algorithm treats the student identifier as the key; it does not decide attendance policy or infer a person’s identity from a name.

Complexity

Every node must be examined to establish that a match is the last, giving O(n) time. A fixed number of remembered pointers gives O(1) auxiliary space.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
void destroy(struct Node *head)
{
    while (head != NULL) { struct Node *next = head->next; free(head); head = next; }
}
int append(struct Node **head, struct Node **tail, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value; node->next = NULL;
    if (*tail != NULL) { (*tail)->next = node; } else { *head = node; }
    *tail = node;
    return 1;
}
void display(const struct Node *head)
{
    const struct Node *p = head;
    while (p != NULL) { printf("%d%s", p->data, p->next == NULL ? "\n" : " "); p = p->next; }
    if (head == NULL) { puts("Empty"); }
}
int delete_last(struct Node **head, struct Node **tail, int key)
{
    struct Node *current = *head, *previous = NULL, *last = NULL, *last_previous = NULL;
    while (current != NULL) {
        if (current->data == key) { last = current; last_previous = previous; }
        previous = current; current = current->next;
    }
    if (last == NULL) { return 0; }
    if (last_previous != NULL) { last_previous->next = last->next; } else { *head = last->next; }
    if (*tail == last) { *tail = last_previous; }
    free(last); return 1;
}

int main(void)
{
    struct Node *head = NULL, *tail = NULL;
    int data[4] = {7, 2, 7, 3};
    for (int i = 0; i < 4; ++i) {
        if (!append(&head, &tail, data[i])) { destroy(head); puts("Allocation failed"); return 1; }
    }
    delete_last(&head, &tail, 7); display(head); destroy(head);
    return 0;
}

7 2 3

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• August/September 2022 · Q2(a) · 8 marks

  Write a function to delete the last occurrence of a student from a list.

  Paper DS02 · page 1

View all matching source questions →