Core Concept and Memory Layout

Unlike arrays that require contiguous memory allocation, a singly linked list distributes elements across arbitrary memory addresses. The logical sequence is maintained through explicit directional references: each element contains a reference to its immediate successor. This architecture relies on two distinct components within each unit: a data field for storing the actual value, and a reference field for navigation. The resulting structure operates similarly to a chain, where each segment explicitly links forward.

Node Structure Definition

The foundation of the list is a self-referential type. The definition below uses a typed integer placeholder that can be adapted for other data types.

typedef int Payload;

typedef struct Node {
    Payload value;
    struct Node* next_ptr;
} Node;

List Initialization with a Sentinel Head

Introducing a dummy head node (sentinel) eliminates special-case logic for operations at the beginning of the chain. The routine below allocates this marker and establishes an empty sequence.

#include <stdlib.h>
#include <stdbool.h>

bool initialize_list(Node** head_ref) {
    *head_ref = (Node*)malloc(sizeof(Node));
    if (*head_ref == NULL) {
        return false; // Allocation failure
    }
    (*head_ref)->next_ptr = NULL; // Marks empty state
    return true;
}

Construction Strategies

Prepending (Head Insertion)

Inserting each incoming element immediately after the sentinel reverses the input sequence. Each insertion executes in constant time.

void construct_by_prepend(Node* head) {
    int input_val;
    printf("Enter values (9999 to terminate): ");
    while (scanf("%d", &input_val) == 1 && input_val != 9999) {
        Node* fresh = (Node*)malloc(sizeof(Node));
        fresh->value = input_val;
        fresh->next_ptr = head->next_ptr;
        head->next_ptr = fresh;
    }
}

Appending (Tail Insertion)

Tracking the end of the chain ensures new elements are added sequentially, preserving the original input order.

Node* construct_by_append() {
    Node* head = (Node*)malloc(sizeof(Node));
    Node* tail = head;
    tail->next_ptr = NULL;

    int input_val;
    while (scanf("%d", &input_val) == 1 && input_val != 9999) {
        Node* fresh = (Node*)malloc(sizeof(Node));
        fresh->value = input_val;
        tail->next_ptr = fresh;
        tail = fresh;
    }
    tail->next_ptr = NULL; // Properly terminate the chain
    return head;
}

Insertion Routines

Positional Insertion

To insert a value at a specific 1-based index, the algorithm traverses to the node immediately preceding the target slot.

bool insert_at_index(Node* head, int target_idx, Payload val) {
    if (target_idx < 1) return false;

    Node* cursor = head;
    int step = 0;

    while (cursor != NULL && step < target_idx - 1) {
        cursor = cursor->next_ptr;
        step++;
    }

    if (cursor == NULL) return false; // Index exceeds bounds

    Node* fresh = (Node*)malloc(sizeof(Node));
    fresh->value = val;
    fresh->next_ptr = cursor->next_ptr;
    cursor->next_ptr = fresh;
    return true;
}

Insertion After a Known Reference

When the target node is already identified, simply reroute the pointer chain to interleave the new unit.

bool insert_after(Node* reference, Payload val) {
    if (reference == NULL) return false;

    Node* fresh = (Node*)malloc(sizeof(Node));
    if (fresh == NULL) return false;

    fresh->value = val;
    fresh->next_ptr = reference->next_ptr;
    reference->next_ptr = fresh;
    return true;
}

Insertion Before a Known Reference

Without backward navigation, placing a node logically before a reference requries an O(1) technique: physically attach the new node after the reference, then exchange their payload values.

bool insert_before(Node* reference, Payload val) {
    if (reference == NULL) return false;

    Node* fresh = (Node*)malloc(sizeof(Node));
    if (fresh == NULL) return false;

    // Physical placement after reference
    fresh->next_ptr = reference->next_ptr;
    reference->next_ptr = fresh;

    // Logical placement via payload swap
    Payload temp = reference->value;
    reference->value = val;
    fresh->value = temp;

    return true;
}

Deletion and Search Operations

Removing a Specified Node

Similar to the pre-insertion technique, deleting a node without predecessor access involves copying the successor's payload, bypassing the successor in the chain, and deallocating the successor.

bool remove_node(Node* target) {
    if (target == NULL || target->next_ptr == NULL) {
        return false; // Swap technique fails on tail nodes
    }

    Node* successor = target->next_ptr;
    target->value = successor->value;
    target->next_ptr = successor->next_ptr;
    free(successor);
    return true;
}

Index-Based Retrieval

Sequentially advance through the chain until the counter aligns with the requested position.

Node* fetch_by_index(Node* head, int idx) {
    if (idx < 0) return NULL;

    Node* cursor = head;
    int step = 0;

    while (cursor != NULL && step < idx) {
        cursor = cursor->next_ptr;
        step++;
    }

    return cursor; // Returns NULL if index is out of range
}

Value-Based Retrieval

Scan from the first data-bearing node until a matching payload is located or the chain terminates.

Node* search_by_value(Node* head, Payload query) {
    Node* cursor = head->next_ptr;
    while (cursor != NULL && cursor->value != query) {
        cursor = cursor->next_ptr;
    }
    return cursor;
}