A linked list is a dynamic data structure consisting of elements connected through pointers. Unlike arrays, elements are not stored contiguously in memory, allowing efficient insertions and deletions without reallocation. Each element contains data and a reference to the subsequent element.

Node Structure

Define the fundamental building block using typedef for cleaner syntax:

typedef struct ListNode {
    int payload;
    struct ListNode* successor;
} ListNode;

typedef struct {
    ListNode* head;
    size_t size;
} LinkedList;

The ListNode stores integer data and a pointer to the next node. The LinkedList wrapper tracks the entry point and miantains a count of elements.

Initialization

Create an empty list with proper null initialization:

LinkedList* create_list(void) {
    LinkedList* list = malloc(sizeof(LinkedList));
    if (!list) {
        perror("Failed to allocate list container");
        exit(EXIT_FAILURE);
    }
    list->head = NULL;
    list->size = 0;
    return list;
}

Insertion Operations

Append elements to the end by traversing to the tail:

void push_back(LinkedList* list, int value) {
    ListNode* node = malloc(sizeof(ListNode));
    if (!node) {
        fprintf(stderr, "Node allocation failed\n");
        exit(EXIT_FAILURE);
    }
    
    node->payload = value;
    node->successor = NULL;
    
    if (!list->head) {
        list->head = node;
    } else {
        ListNode* current = list->head;
        while (current->successor) {
            current = current->successor;
        }
        current->successor = node;
    }
    list->size++;
}

For O(1) insertion at the beginning:

void push_front(LinkedList* list, int value) {
    ListNode* node = malloc(sizeof(ListNode));
    if (!node) {
        fprintf(stderr, "Allocation error\n");
        return;
    }
    node->payload = value;
    node->successor = list->head;
    list->head = node;
    list->size++;
}

Deletion by Value

Remove the first occurrence matching the target value:

void remove_value(LinkedList* list, int target) {
    if (!list->head) {
        printf("Cannot delete from empty list\n");
        return;
    }
    
    if (list->head->payload == target) {
        ListNode* temp = list->head;
        list->head = list->head->successor;
        free(temp);
        list->size--;
        return;
    }
    
    ListNode* prev = list->head;
    while (prev->successor && prev->successor->payload != target) {
        prev = prev->successor;
    }
    
    if (prev->successor) {
        ListNode* target_node = prev->successor;
        prev->successor = target_node->successor;
        free(target_node);
        list->size--;
    } else {
        printf("Value %d not found in list\n", target);
    }
}

Traversal and Display

Iterate through elements without modifying structure:

void display(const LinkedList* list) {
    const ListNode* current = list->head;
    while (current) {
        printf("%d -> ", current->payload);
        current = current->successor;
    }
    printf("NULL\n");
}

Search Operations

Locate a node by its payload:

ListNode* find(const LinkedList* list, int key) {
    ListNode* cursor = list->head;
    while (cursor) {
        if (cursor->payload == key) {
            return cursor;
        }
        cursor = cursor->successor;
    }
    return NULL;
}

Utility Functions

Retrieve the number of elements:

size_t get_length(const LinkedList* list) {
    return list->size;
}

Deallocate all nodes to prevent memory leaks:

void destroy_list(LinkedList* list) {
    ListNode* current = list->head;
    while (current) {
        ListNode* next = current->successor;
        free(current);
        current = next;
    }
    list->head = NULL;
    list->size = 0;
    free(list);
}

Complete Working Example

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

typedef struct ListNode {
    int payload;
    struct ListNode* successor;
} ListNode;

typedef struct {
    ListNode* head;
    size_t size;
} LinkedList;

LinkedList* create_list(void) {
    LinkedList* list = malloc(sizeof(LinkedList));
    if (!list) {
        perror("Allocation failed");
        exit(EXIT_FAILURE);
    }
    list->head = NULL;
    list->size = 0;
    return list;
}

void push_back(LinkedList* list, int value) {
    ListNode* node = malloc(sizeof(ListNode));
    if (!node) {
        fprintf(stderr, "Memory error\n");
        exit(EXIT_FAILURE);
    }
    node->payload = value;
    node->successor = NULL;
    
    if (!list->head) {
        list->head = node;
    } else {
        ListNode* iter = list->head;
        while (iter->successor) {
            iter = iter->successor;
        }
        iter->successor = node;
    }
    list->size++;
}

void remove_value(LinkedList* list, int target) {
    if (!list->head) {
        printf("Empty list\n");
        return;
    }
    
    if (list->head->payload == target) {
        ListNode* obsolete = list->head;
        list->head = obsolete->successor;
        free(obsolete);
        list->size--;
        return;
    }
    
    ListNode* predecessor = list->head;
    while (predecessor->successor && predecessor->successor->payload != target) {
        predecessor = predecessor->successor;
    }
    
    if (predecessor->successor) {
        ListNode* obsolete = predecessor->successor;
        predecessor->successor = obsolete->successor;
        free(obsolete);
        list->size--;
    } else {
        printf("Element %d not found\n", target);
    }
}

void traverse(const LinkedList* list) {
    const ListNode* cursor = list->head;
    while (cursor) {
        printf("%d -> ", cursor->payload);
        cursor = cursor->successor;
    }
    printf("NULL\n");
}

ListNode* search(const LinkedList* list, int key) {
    ListNode* ptr = list->head;
    while (ptr) {
        if (ptr->payload == key) return ptr;
        ptr = ptr->successor;
    }
    return NULL;
}

void purge(LinkedList* list) {
    ListNode* ptr = list->head;
    while (ptr) {
        ListNode* next_ptr = ptr->successor;
        free(ptr);
        ptr = next_ptr;
    }
    list->head = NULL;
    list->size = 0;
}

int main(void) {
    LinkedList* inventory = create_list();
    
    push_back(inventory, 100);
    push_back(inventory, 200);
    push_back(inventory, 300);
    push_back(inventory, 400);
    
    printf("Initial state:\n");
    traverse(inventory);
    
    remove_value(inventory, 200);
    printf("After removing 200:\n");
    traverse(inventory);
    
    ListNode* result = search(inventory, 300);
    if (result) {
        printf("Found node with value: %d\n", result->payload);
    }
    
    printf("Current size: %zu\n", inventory->size);
    
    purge(inventory);
    free(inventory);
    
    return 0;
}