Node Structure Definition

A singly linked list is constructed as a sequence of nodes, where each node contains a data field and a pointer to the subsequent node. The following structure defines a node with an integer identifier and a text label.

typedef struct ListNode {
    int id;
    char description[32];
    struct ListNode* next;
} ListNode;

Node Insertion

Insertion at the Head

Adding a node at the beginning requires the new node to point to the current head, subsequently updating the head pointer to reference the new node. This operation is efficient, running in O(1) time.

ListNode* insertAtHead(ListNode* head, int id, const char* desc) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (!newNode) {
        perror("Memory allocation failed");
        return head;
    }
    newNode->id = id;
    strncpy(newNode->description, desc, sizeof(newNode->description) - 1);
    newNode->description[sizeof(newNode->description) - 1] = '\0';
    newNode->next = head;
    return newNode;
}

Insertion at the Tail

To append a node, traverse the list to locate the last element. If the list is empty, the new node becomes the head.

ListNode* insertAtTail(ListNode* head, int id, const char* desc) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (!newNode) return head;
    
    newNode->id = id;
    strncpy(newNode->description, desc, sizeof(newNode->description) - 1);
    newNode->description[sizeof(newNode->description) - 1] = '\0';
    newNode->next = NULL;

    if (head == NULL) {
        return newNode;
    }

    ListNode* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

Insertion After a Specific Node

Inserting after a node identified by a specific ID involves traversing to that node and adjusting pointers.

ListNode* insertAfterTarget(ListNode* head, int targetId, int newId, const char* desc) {
    ListNode* current = head;
    while (current != NULL && current->id != targetId) {
        current = current->next;
    }

    if (current == NULL) {
        printf("Target node %d not found.\n", targetId);
        return head;
    }

    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (!newNode) return head;

    newNode->id = newId;
    strncpy(newNode->description, desc, sizeof(newNode->description) - 1);
    newNode->next = current->next;
    current->next = newNode;
    return head;
}

Node Deletion

Standard Deletion by ID

Removing a node requires maintaining a reference to the previous node to bypass the node being deleted. Special handling is necessary when the target node is the head.

ListNode* deleteNodeById(ListNode* head, int targetId) {
    if (head == NULL) {
        printf("List is empty.\n");
        return NULL;
    }

    // Case 1: Deleting the head node
    if (head->id == targetId) {
        ListNode* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    // Case 2: Deleting a node in the middle or end
    ListNode* current = head;
    while (current->next != NULL && current->next->id != targetId) {
        current = current->next;
    }

    if (current->next == NULL) {
        printf("Node with ID %d not found.\n", targetId);
    } else {
        ListNode* temp = current->next;
        current->next = temp->next;
        free(temp);
    }
    return head;
}

Deletion Without Head Pointer (Interview Scenario)

A common technical interview challenge involves deleting a node when only a pointer to that specific node is provided, and the head pointer is unavailable. Since traversal backward is impossible in a singly linked list, the solution involves copying the data from the next node into the current node and then deleting the next node.

void deleteNodeWithoutHead(ListNode* node) {
    if (node == NULL || node->next == NULL) {
        // Cannot delete the last node or a null node using this method
        printf("Deletion failed: Node is the tail or invalid.\n");
        return;
    }

    ListNode* nextNode = node->next;
    node->id = nextNode->id;
    strcpy(node->description, nextNode->description);
    node->next = nextNode->next;
    free(nextNode);
}

Search and Update

Searching for a Node

Finding a node involves traversing the list until the identifier matches.

ListNode* findNode(ListNode* head, int targetId) {
    ListNode* current = head;
    while (current != NULL) {
        if (current->id == targetId) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

Updating Node Data

Modification typically combines a search operation followed by data alteration.

void updateNodeData(ListNode* head, int targetId, const char* newDesc) {
    ListNode* target = findNode(head, targetId);
    if (target != NULL) {
        strncpy(target->description, newDesc, sizeof(target->description) - 1);
        target->description[sizeof(target->description) - 1] = '\0';
        printf("Updated node %d successfully.\n", targetId);
    } else {
        printf("Node %d not found for update.\n", targetId);
    }
}