Doubly 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; struct Node *prev;
} Node;

Node is a short typedef name for the self-referential structure. data stores the integer. next identifies the following node. prev also identifies the preceding node, enabling backward traversal.

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. The loop releases each node exactly once.

    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; node->prev = 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. Both next and prev start as NULL.

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

The new node becomes both head and tail. There is no old endpoint to reconnect.

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

Link the new node to the old head before replacing head. The old head’s prev must also point back to the new node.

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

Link the old tail to the new node, then update the tail variable. Set the new node’s prev to the old tail so the backward link is preserved. The new tail’s next remains NULL.

    } 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; node->prev = previous; node->next->prev = node;
        previous->next = node;
    }

Set the new node’s next to the old successor before changing previous->next to node. Also set node->prev to previous and the old successor’s prev to node. Both traversal directions must agree.

    ++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;

Reject positions outside 1 through count. node will remember the removed node so its data can be returned and its storage freed after reconnection.

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

Save the old head. A one-node deletion clears both endpoints. Otherwise move head to the next node and set its prev to NULL, because a linear list’s first node has no predecessor.

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

When deleting the tail, tail->prev provides the predecessor directly. For other non-head positions, walk forward from head to position - 1. The brace ends this search branch.

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

Save previous->next in node, then link previous to node->next. If a successor exists, set its prev to previous. If node was tail, update tail to previous. These repairs keep forward and reverse traversal consistent.

    *removed = node->data;
    free(node);
    --list->count;
    return 1;
}

Assign node->data through removed before freeing node. Decrement count, return success and close deleteAt. The caller receives a copied integer, not an address into freed storage.

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:");
    for (const Node *p = list->head; p != NULL; p = p->next) printf(" %d", p->data);
    putchar('\n');
}

Follow next links from head until NULL, printing each integer. The const Node pointer prevents modification through that traversal access. Finish with a newline.

void traverseReverse(const List *list) {
    printf("Reverse:");
    for (const Node *p = list->tail; p != NULL; p = p->prev) printf(" %d", p->data);
    putchar('\n');
}

Start at tail and follow prev links until NULL. This produces the reverse order without changing the list or allocating a reverse copy.

/* 1 n values: create; 2 position value: insert; 3 position: delete;
   4: display; 5: reverse 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 if (command == 5) traverseReverse(&list);
        else goto invalid;
    }

Command 5 calls traverseReverse. Any remaining command jumps to invalid. The closing brace ends the command loop.

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

invalid is a label, not another function. All goto invalid branches arrive here. Print the message, release every remaining list node, then return failure from main.