Structure Definition

A singly linked list is a linear data structure where elements are stored in nodes that are logically connected but physically dispersed in memory. Each node contains data and a pointer to the next node in the sequence.

typedef int DataType;
typedef struct Node {
    DataType value;
    struct Node* next;
} ListNode;

In this implementation:

• Nodes are unidirectionally connected
• No sentinel head node is used
• The last node points to NULL, making it non-circular

Core Operations

Node Creation

Creating a new node involves allocating memory and initializing its fields:

ListNode* createNode(DataType data) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (!newNode) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    newNode->value = data;
    newNode->next = NULL;
    return newNode;
}

Traversal and Display

Iterating through the list to display all elements:

void displayList(ListNode* head) {
    ListNode* current = head;
    while (current) {
        printf("%d -> ", current->value);
        current = current->next;
    }
    printf("NULL\n");
}

Tail Insertion

Adding an element at the end of the list:

void appendNode(ListNode** headRef, DataType data) {
    ListNode* newNode = createNode(data);
    
    if (!*headRef) {
        *headRef = newNode;
        return;
    }
    
    ListNode* current = *headRef;
    while (current->next) {
        current = current->next;
    }
    current->next = newNode;
}

Head Insertion

Inserting an element at the beginning:

void prependNode(ListNode** headRef, DataType data) {
    ListNode* newNode = createNode(data);
    newNode->next = *headRef;
    *headRef = newNode;
}

Tail Deletion

Removing the last element requires special handling for single-node lists:

void removeTail(ListNode** headRef) {
    if (!*headRef) return;
    
    if (!(*headRef)->next) {
        free(*headRef);
        *headRef = NULL;
        return;
    }
    
    ListNode* previous = *headRef;
    ListNode* current = (*headRef)->next;
    
    while (current->next) {
        previous = current;
        current = current->next;
    }
    
    free(current);
    previous->next = NULL;
}

Head Deletion

Removing the first element:

void removeHead(ListNode** headRef) {
    if (!*headRef) return;
    
    ListNode* temp = *headRef;
    *headRef = (*headRef)->next;
    free(temp);
}

Element Search

Finding a specific value in the list:

ListNode* findElement(ListNode* head, DataType target) {
    ListNode* current = head;
    while (current) {
        if (current->value == target) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

Arbitrary Position Insertion

Inserting before a specific node:

void insertBefore(ListNode** headRef, ListNode* target, DataType data) {
    if (!target || !*headRef) return;
    
    if (target == *headRef) {
        prependNode(headRef, data);
        return;
    }
    
    ListNode* current = *headRef;
    while (current->next && current->next != target) {
        current = current->next;
    }
    
    if (current->next == target) {
        ListNode* newNode = createNode(data);
        newNode->next = target;
        current->next = newNode;
    }
}

Memory Deallocation

Properly freeing all allocated memory:

void destroyList(ListNode** headRef) {
    ListNode* current = *headRef;
    ListNode* nextNode;
    
    while (current) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    *headRef = NULL;
}

Characteristics

Linked lists provide O(1) insertion and deletion at both ends when proper references are maintained. However, they do not support random access and require sequential traversal for element retrieval. Memory overhead per element is higher compared to arays due to pointer storage, but dynamic sizing eliminates pre-allocation concerns.