QUESTION 09

What changes when inserting at the head of a singly linked list?

2 marks

Answer

Set new_node->next to the old head, then make head identify the new node. Check allocation before changing the list.

Explain singly linked-list insertion and deletion with algorithms.

5 marks

Answer in brief

Insertion creates a node and reconnects links. Deletion disconnects a selected node and releases its storage when the list owns it.

Insert at beginning

Allocate and initialise new_node.
Set new_node->next = head.
Set head = new_node.

Insert at end

Set the new node’s next to NULL. If the list is empty, set head to it. Otherwise follow links to the final node and set its next to the new node. A maintained tail avoids that search. Do not lose the old head while traversing.

Delete the first matching value

Track current and previous while searching.
If no node matches, report failure without changing the list.
For a head match, set head to current->next.
Otherwise set previous->next to current->next.
Free current and stop using it.

Example

Deleting 20 from 10 → 20 → 30 links the 10 node directly to the 30 node before freeing the 20 node. Deleting 10 instead changes head. Deleting the sole node leaves head equal to NULL.

Complexity

Head insertion is O(1) link work. End insertion without a tail and value-based deletion can each need O(n) search. Once the relevant predecessor is already known, unlinking is O(1). Node storage grows with the list; the fixed search pointers add O(1) auxiliary space. The demonstration program includes creation, append, delete, traversal and cleanup.

Complete C example

main.c

Download 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_first(struct Node **head, struct Node **tail, int value)
{
    struct Node *current = *head, *previous = NULL;
    while (current != NULL && current->data != value) { previous = current; current = current->next; }
    if (current == NULL) { return 0; }
    if (previous != NULL) { previous->next = current->next; } else { *head = current->next; }
    if (*tail == current) { *tail = previous; }
    free(current);
    return 1;
}

int main(void)
{
    struct Node *head = NULL, *tail = NULL;
    for (int value = 10; value <= 30; value += 10) {
        if (!append(&head, &tail, value)) { destroy(head); puts("Allocation failed"); return 1; }
    }
    display(head);
    delete_first(&head, &tail, 20);
    display(head);
    destroy(head);
    head = tail = NULL;
    return 0;
}

Sample input and output

The example uses values in the code.

Output

10 20 30
10 30

Worked trace: keep both head and tail correct

The complete program keeps a head pointer and a tail pointer. Consider three separately allocated nodes holding 10, 20, 30. Head identifies 10 and tail identifies 30. Delete the first node whose value is 30.

↔ Scroll horizontally on a small screen

Deleting the tail node
Stage	previous	current	Action
Start	NULL	10	The first value does not match
Move once	10	20	The second value does not match
Move again	20	30	The value matches
Reconnect	20	30	Set previous->next to NULL and tail to previous
Release	20	No longer usable	Free the removed node; the list contains 10, 20

Changing only previous->next would leave tail pointing to freed storage. A later append could then write through that invalid pointer. The tail update is part of the deletion, even though traversal from head might initially look correct.

Other cases to check

Delete the first node: move head to its successor before freeing the old head.
Delete the only node: both head and tail must become NULL.
Delete an absent value: return failure and keep every link unchanged.
Duplicate values: the supplied function removes only the first match. In 10, 20, 20, deleting 20 leaves 10, 20.

Why the search still costs O(n)

A tail pointer makes appending convenient, but it does not tell us which node comes before a requested value. Value-based deletion may inspect every node. Reconnecting the links is fixed work after the match and its predecessor have been found.