Circular singly linked list

#include <stdio.h>

stdio.h declares printf, puts, getchar and putchar. The input helper reads characters with getchar; the main program prints operation results using the output functions.

#include <stdlib.h>

stdlib.h declares strtol for converting an integer token. It also declares malloc and free, which the linked structures and tree programs use to obtain and release node storage.

#include <string.h>

string.h declares utilities such as memset. It is part of the shared header list; merely including a header does not call any function or change stored values.

#include <ctype.h>
#include <errno.h>

ctype.h supplies isspace for recognising whitespace. errno.h supplies errno so the program can detect a range error reported by strtol.

/* Read a complete integer token; reject bad or oversized input safely. */
int readInt(int *value) {

The comment states the purpose of readInt. Its int *value parameter receives the address of a caller variable. The helper returns 1 after storing a valid value there, or 0 on failure; these flags are separate from main’s process exit status.

    char token[64];
    int ch;
    size_t used = 0;

token holds up to 63 input characters and a null terminator. ch is int so it can distinguish character input from EOF. used starts at zero and counts the stored token characters.

    while ((ch = getchar()) != EOF && isspace((unsigned char)ch)) { }
    if (ch == EOF) return 0;

getchar reads one character at a time. The loop discards whitespace before the token. The unsigned-char cast supplies an allowed argument to isspace. If EOF is reached before a token starts, return 0 without changing the caller variable.

    do {
        if (used < sizeof token - 1) token[used++] = (char)ch;

The do-while body handles the first non-whitespace character already read. The size check leaves one buffer slot for a null terminator. used++ uses the old index for storage, then advances the count.

        else {
            while ((ch = getchar()) != EOF && !isspace((unsigned char)ch)) { }
            return 0;
        }

When the buffer has no character space left, consume the rest of that token through whitespace or EOF, then return failure. The program does not silently treat a truncated prefix as the full input number.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));

Keep collecting until whitespace or EOF. The terminating whitespace has been consumed by getchar; it is not stored as part of the token.

    token[used] = '\0';
    char *end;
    errno = 0;

Write the null terminator after the stored token. end will identify where conversion stopped. Reset errno before strtol so a previous library error cannot be mistaken for this conversion’s result.

    long result = strtol(token, &end, 10);

strtol reads token in base 10 and returns a long. Passing &end lets it write the address of the first unconverted character. A sign such as - is allowed as part of a valid integer token.

    if (errno || *end != '\0' || result < -1000000 || result > 1000000) return 0;

A nonzero errno rejects a reported conversion error. *end must be the null terminator, so input such as 12x is rejected rather than accepted as 12. The allowed value range is -1,000,000 to 1,000,000.

    *value = (int)result;
    return 1;
}

After validation, cast result to int and assign it through *value. Return 1 for success. The brace ends readInt. The caller variable remains unchanged on the earlier failure returns.

typedef struct Node {
    int data;
    struct Node *next; 
} Node;

Node is a short typedef name for the self-referential structure. data stores the integer. next identifies the following node. In this circular representation, the final node links back to head.

typedef struct {
    Node *head, *tail;
    int count;
} List;

The List structure stores head, tail and count. Passing List * to an operation lets that operation change the caller’s endpoint pointers and count, rather than only local copies.

void clearList(List *list) {
    Node *current = list->head;

clearList receives the actual list state. current initially identifies the head node; an empty list has count zero and no nodes to visit.

    for (int i = 0; i < list->count; ++i) {
        Node *next = current->next;
        free(current);
        current = next;
    }

Repeat once for each counted node. Read current->next while current is still alive, free current, then continue using the saved address. Do not read current->next after free. Counting nodes stops after one circuit; a circular list does not end at a null next link.

    list->head = list->tail = NULL;
    list->count = 0;
}

Set both endpoints to NULL and count to zero. The empty state prevents later operations from following a link to released storage.

/* Positions are 1-based. Return 1 on success, 0 on failure. */
int insertAt(List *list, int position, int value) {
    if (position < 1 || position > list->count + 1) return 0;

The comment records the return convention. An insertion position must lie from 1 through count + 1. Position 1 means the front and count + 1 means append. Invalid positions return 0 without allocating or changing links.

    Node *node = malloc(sizeof *node);
    if (node == NULL) return 0;
    node->data = value;
    node->next = NULL; 

malloc(sizeof *node) reserves space for one complete Node. If allocation fails, return 0 before changing the old list. Set data to value and initialise the link fields. next starts as NULL until the chosen branch connects it.

    if (list->count == 0) {
        list->head = list->tail = node; node->next = node;

The new node becomes both head and tail. Set node->next to node itself so the one-node list already forms a circle.

    } else if (position == 1) {
        node->next = list->head; 
        list->head = node; list->tail->next = list->head;

Link the new node to the old head before replacing head. The old chain stays reachable through node->next. Finally make tail->next identify the new head, preserving the circular link.

    } else if (position == list->count + 1) {
        
        list->tail->next = node;
        list->tail = node; node->next = list->head;

Link the old tail to the new node, then update the tail variable. Set the new tail’s next to head to close the circle again.

    } else {
        Node *previous = list->head;
        for (int i = 1; i < position - 1; ++i) previous = previous->next;

For positions strictly between the endpoints, start previous at head and move until it identifies position - 1. This is the node whose next link must change.

        node->next = previous->next; 
        previous->next = node;
    }

Set the new node’s next to the old successor before changing previous->next to node. This order preserves the address of the remainder of the list.

    ++list->count;
    return 1;
}

Increment count only after the new node has been fully connected. Return 1 to tell the caller that insertion succeeded.

int deleteAt(List *list, int position, int *removed) {
    if (position < 1 || position > list->count) return 0;
    Node *node;

A deletion position must be from 1 through count; an empty list has no valid deletion. node will remember the exact node that must be disconnected and freed. removed is an output pointer for returning its stored integer.

    if (position == 1) {
        node = list->head;
        if (list->count == 1) list->head = list->tail = NULL;

Save the old head in node before changing any endpoint. If it is the only node, both head and tail become NULL.

        else {
            list->head = node->next; list->tail->next = list->head;
        }
    } else {

Move head to node->next when other nodes remain. Also update tail->next to the new head so the circle no longer points at the removed node. The final brace/else leads to the separate non-head case.

        Node *previous = list->head;
        for (int i = 1; i < position - 1; ++i) previous = previous->next;
        node = previous->next;

Walk previous to the node before the requested position, then save previous->next in node. The original list stays connected until both pointers have been obtained.

        previous->next = node->next; 
        if (node == list->tail) list->tail = previous;
    }

Set previous->next to node->next. If the target was the tail, previous becomes the new tail. Its next already points to head after the bypass, so the circle is preserved.

    *removed = node->data;
    free(node);

Copy node->data through the output pointer. Then free node. The integer result is independent of the released node and can safely be printed by the caller.

    --list->count;
    return 1;
}

Decrease count once for the successful removal, then return 1. Rejected requests returned earlier without changing the list.

int createList(List *list, const int values[], int n) {
    List fresh = {NULL, NULL, 0};

createList receives the current list, an input array and n. fresh starts empty. Building in a separate List allows allocation failure to leave the current list unchanged.

    for (int i = 0; i < n; ++i)
        if (!insertAt(&fresh, fresh.count + 1, values[i])) {
            clearList(&fresh);
            return 0;
        }

Use fresh.count + 1 as the append position. If any insertion fails, clear the partial fresh list and return 0. The old list has not been cleared yet, so it remains available.

    clearList(list);
    *list = fresh;
    return 1;
}

After all n nodes have been created, clear the old list. Assign the whole fresh state into *list, including both endpoints and count, then return 1. This copies the small wrapper; the allocated nodes remain alive after the local fresh wrapper ends. For n = 0, the replacement is an empty list.

void traverse(const List *list) {
    printf("List:");
    if (list->head != NULL) {

Print the label. The head check prevents trying to print a node in an empty list; the circular loop has no null endpoint to detect emptiness on its own.

        const Node *p = list->head;
        do { printf(" %d", p->data); p = p->next; } while (p != list->head);
    }

Start p at head and use do-while to print each node before advancing. Stop when p returns to head. Testing p != NULL here would never end for a valid nonempty circular list.

    putchar('\n');
}

putchar prints a newline after traversal or after the label of an empty list. The brace ends traverse.

/* 1 n values: create; 2 position value: insert; 3 position: delete;
   4: display; 0: exit. */
int main(void) {

The comment lists the command number and any following arguments. main is the program entry function and returns an integer exit status.

    List list = {NULL, NULL, 0};
    int command;

Both endpoint pointers begin as NULL and count begins at zero. command stores the next requested operation.

    while (readInt(&command)) {
        if (command == 0) { clearList(&list); return 0; }

The loop continues while readInt succeeds. Command 0 clears all nodes and returns success immediately. Running out of input without the explicit exit command is handled by the error path below.

        if (command == 1) {
            int n, values[100];
            if (!readInt(&n) || n < 0 || n > 100) goto invalid;
            for (int i = 0; i < n; ++i) if (!readInt(&values[i])) goto invalid;

For command 1, n must be from 0 through 100. Read exactly n integers into the temporary values array. A missing or rejected integer jumps to the shared invalid label.

            puts(createList(&list, values, n) ? "Created." : "Allocation failed; list unchanged.");

The conditional expression selects the success or allocation-failure message using createList’s result. The helper’s temporary-list design preserves the current list if allocation fails.

        } else if (command == 2) {
            int position, value;
            if (!readInt(&position) || !readInt(&value)) goto invalid;
            puts(insertAt(&list, position, value) ? "Inserted." : "Insertion failed: invalid position or allocation failure.");

For command 2, read position and value. A token-reading failure uses the shared error path. insertAt reports whether the position and allocation were acceptable; puts then prints the corresponding message.

        } else if (command == 3) {
            int position, value;
            if (!readInt(&position)) goto invalid;
            if (deleteAt(&list, position, &value)) printf("Deleted: %d\n", value);
            else puts("Invalid deletion position.");

For command 3, read a position. Pass &value as output storage to deleteAt. Print that integer only when deletion succeeds; otherwise report an invalid position without using an unassigned value.

        } else if (command == 4) traverse(&list);

traverse prints the nodes in their forward logical order without removing any node.

        else goto invalid;
    }

A command not handled by the previous branches jumps to invalid. The brace ends the reading loop.

invalid:
    puts("Invalid or incomplete input. End with command 0.");
    clearList(&list);
    return 1;
}

The invalid label is the destination of the earlier goto statements. It is also reached if the command loop ends without command 0. Print the message, clear the list and return failure.