A linked list organizes elements using non-contiguous memory blocks. Each node holds a data field and a pointer to the next node, forming a chain. The basic structure is defined as follows:

typedef struct SNode {
    int value;
    struct SNode *next;
} SNode, *SList;

Headless List Operations

Operations on lists without a dummy head node require special handling for the first position.

bool initHeadless(SList *list) {
    *list = NULL;
    return true;
}

bool insertHeadless(SList *list, int position, int item) {
    if (position < 1) return false;
    if (position == 1) {
        SNode *node = (SNode *)malloc(sizeof(SNode));
        if (!node) return false;
        node->value = item;
        node->next = *list;
        *list = node;
        return true;
    }
    return insertAt(list, position - 1, item);
}

Initialization with a Sentinel Node

A sentinel node simplifeis edge cases by acting as a placeholder before the first real element.

bool initList(SList *list) {
    *list = (SNode *)malloc(sizeof(SNode));
    if (*list == NULL) return false;
    (*list)->next = NULL;
    return true;
}

Insertion at a Given Index

bool insertAt(SList *list, int index, int item) {
    if (index < 1) return false;
    SNode *curr = *list;
    int count = 0;
    while (curr != NULL && count < index - 1) {
        curr = curr->next;
        ++count;
    }
    if (curr == NULL) return false;
    SNode *fresh = (SNode *)malloc(sizeof(SNode));
    if (!fresh) return false;
    fresh->value = item;
    fresh->next = curr->next;
    curr->next = fresh;
    return true;
}

Inserting After a Given Node

bool addAfterNode(SNode *target, int item) {
    if (target == NULL) return false;
    SNode *newNode = (SNode *)malloc(sizeof(SNode));
    if (!newNode) return false;
    newNode->value = item;
    newNode->next = target->next;
    target->next = newNode;
    return true;
}

Inserting Before a Given Node

Becuase there is no backward link, we can swap values to simulate a prepend.

bool addBeforeNode(SNode *target, int item) {
    if (target == NULL) return false;
    SNode *newNode = (SNode *)malloc(sizeof(SNode));
    if (!newNode) return false;
    newNode->next = target->next;
    target->next = newNode;
    newNode->value = target->value;
    target->value = item;
    return true;
}

Deletion at a Given Index

bool deleteAt(SList *list, int index, int *removed) {
    if (index < 1) return false;
    SNode *prev = *list;
    int count = 0;
    while (prev != NULL && count < index - 1) {
        prev = prev->next;
        ++count;
    }
    if (prev == NULL || prev->next == NULL) return false;
    SNode *target = prev->next;
    *removed = target->value;
    prev->next = target->next;
    free(target);
    return true;
}

Deleting a Specific Node

Special care is needed when the node to delete is the tail.

bool removeNode(SNode *target) {
    if (target == NULL) return false;
    if (target->next != NULL) {
        SNode *succeeding = target->next;
        target->value = succeeding->value;
        target->next = succeeding->next;
        free(succeeding);
    } else {
        free(target);
        // External record-keeping (e.g., length) must be adjusted by the caller
    }
    return true;
}

Element Retrieval

Locate by position:

SNode *fetchAt(SList list, int index) {
    if (index < 0) return NULL;
    SNode *curr = list;
    int pos = 0;
    while (curr != NULL && pos < index) {
        curr = curr->next;
        ++pos;
    }
    return curr;
}

Locate by value:

SNode *findValue(SList list, int key) {
    SNode *curr = list->next;
    while (curr != NULL && curr->value != key) {
        curr = curr->next;
    }
    return curr;
}

Length Calculation

int nodeCount(SList list) {
    int total = 0;
    for (SNode *n = list->next; n != NULL; n = n->next)
        total++;
    return total;
}

Building the List

Tail insertion maintains input order:

SList buildFromTail() {
    int input;
    SList head = (SNode *)malloc(sizeof(SNode));
    SNode *tail = head;
    while (scanf("%d", &input) != EOF) {
        SNode *cell = (SNode *)malloc(sizeof(SNode));
        cell->value = input;
        tail->next = cell;
        tail = cell;
    }
    tail->next = NULL;
    return head;
}

Head insertion reverses input order:

SList buildFromHead() {
    int input;
    SList head = (SNode *)malloc(sizeof(SNode));
    head->next = NULL;
    while (scanf("%d", &input) != EOF) {
        SNode *cell = (SNode *)malloc(sizeof(SNode));
        cell->value = input;
        cell->next = head->next;
        head->next = cell;
    }
    return head;
}

These operations cover the fundaemntal singly linked list manipulations commonly examined in foundational algorithm assessments.