/*
 * Single linked list: independent tail/head builds and two searches.
 * The sentinel head stores no event ID and is not counted in positions.
 * Compile: cc -std=c11 -Wall -Wextra -pedantic linked-list-example.c -o list-demo
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

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

static Node *new_node(int value)
{
    Node *node = malloc(sizeof *node);
    if (node == NULL) {
        return NULL;
    }
    node->data = value;
    node->next = NULL;
    return node;
}

static Node *create_head(void)
{
    return new_node(0); /* Sentinel data is unused. */
}

static void destroy_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

static Node *build_tail(const int values[], size_t count)
{
    Node *L = create_head();
    if (L == NULL) {
        return NULL;
    }
    Node *r = L;
    for (size_t i = 0; i < count; ++i) {
        Node *s = new_node(values[i]);
        if (s == NULL) {
            destroy_list(L);
            return NULL;
        }
        r->next = s; /* Connect first. */
        r = s;       /* Then update the tail pointer. */
    }
    return L;
}

static Node *build_head(const int values[], size_t count)
{
    Node *L = create_head();
    if (L == NULL) {
        return NULL;
    }
    for (size_t i = 0; i < count; ++i) {
        Node *s = new_node(values[i]);
        if (s == NULL) {
            destroy_list(L);
            return NULL;
        }
        s->next = L->next; /* Preserve the old chain first. */
        L->next = s;       /* Then replace the sentinel's link. */
    }
    return L;
}

static Node *find_value(Node *L, int target)
{
    if (L == NULL) { /* Initialization failure is distinct from an empty list. */
        return NULL;
    }
    Node *p = L->next;
    while (p != NULL) {
        if (p->data == target) {
            return p; /* The first matching node. */
        }
        p = p->next;
    }
    return NULL;
}

static Node *find_index(Node *L, int i)
{
    if (L == NULL || i < 1) {
        return NULL;
    }
    Node *p = L->next;
    int j = 1;
    while (p != NULL && j < i) {
        p = p->next;
        ++j;
    }
    if (p == NULL) {
        return NULL;
    }
    return p;
}

static void print_list(const char *label, const Node *L)
{
    printf("%s:", label);
    if (L != NULL) {
        for (const Node *p = L->next; p != NULL; p = p->next) {
            printf(" %d", p->data);
        }
    }
    putchar('\n');
}

static int has_order(const Node *L, const int expected[], size_t count)
{
    if (L == NULL) {
        return 0;
    }
    const Node *p = L->next;
    for (size_t i = 0; i < count; ++i) {
        if (p == NULL || p->data != expected[i]) {
            return 0;
        }
        p = p->next;
    }
    return p == NULL;
}

int main(void)
{
    const int values[] = {103, 101, 105, 102, 104};
    const int reversed[] = {104, 102, 105, 101, 103};
    const size_t count = sizeof values / sizeof values[0];
    Node *tail = build_tail(values, count);
    Node *head = build_head(values, count); /* A separate empty list. */
    Node *empty = build_tail(NULL, 0);
    const int duplicate_values[] = {7, -2, -2};
    Node *duplicates = build_tail(duplicate_values, 3);
    const int singleton_value[] = {42};
    Node *singleton = build_tail(singleton_value, 1);
    if (tail == NULL || head == NULL || empty == NULL ||
        duplicates == NULL || singleton == NULL) {
        fputs("Memory allocation failed.\n", stderr);
        destroy_list(tail);
        destroy_list(head);
        destroy_list(empty);
        destroy_list(duplicates);
        destroy_list(singleton);
        return EXIT_FAILURE;
    }

    print_list("Tail insertion", tail);
    print_list("Head insertion", head);
    assert(has_order(tail, values, count));
    assert(has_order(head, reversed, count));

    /* Search only the tail-built table for the classroom baseline. */
    Node *matched = find_value(tail, 105);
    assert(matched != NULL && matched->data == 105);
    if (matched != NULL) {
        printf("Value 105 found: %d\n", matched->data);
    }
    assert(find_value(tail, 999) == NULL);
    const int indexes[] = {1, 3, 5};
    const int expected[] = {103, 105, 104};
    for (size_t k = 0; k < 3; ++k) {
        Node *result = find_index(tail, indexes[k]);
        assert(result != NULL && result->data == expected[k]);
        if (result != NULL) {
            printf("Index %d: %d\n", indexes[k], result->data);
        }
    }
    assert(find_index(tail, 0) == NULL);
    assert(find_index(tail, -1) == NULL);
    assert(find_index(tail, 6) == NULL);
    assert(find_value(empty, 105) == NULL);
    assert(find_index(empty, 1) == NULL);
    assert(find_value(duplicates, -2) == duplicates->next->next);
    assert(find_index(singleton, 1) == singleton->next);
    assert(find_index(singleton, 2) == NULL);
    assert(has_order(tail, values, count)); /* Searching does not modify links. */
    puts("All baseline and boundary checks passed.");

    destroy_list(tail);
    destroy_list(head);
    destroy_list(empty);
    destroy_list(duplicates);
    destroy_list(singleton);
    return EXIT_SUCCESS;
}