Introduction to Singly Linked Lists

A singly linked list is a linear data strcuture where each element, called a node, contains data and a pointer to the next node in the sequence. Unlike arrays, nodes are not stored contiguous in memory, allowing dynamic memory allocation and efficietn insertions and deletions.

Node Structure

Each node consists of two parts: the data field and a pointer to the next node.

typedef int NodeData;
typedef struct ListNode {
    NodeData value;
    struct ListNode* next;
} ListNode;

To create a node:

ListNode* createNode(NodeData val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->value = val;
    newNode->next = NULL;
    return newNode;
}

Basic Operations

Traversing the List

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

Insertion Operations

Insert at the End

void insertEnd(ListNode** headRef, NodeData val) {
    ListNode* newNode = createNode(val);
    if (*headRef == NULL) {
        *headRef = newNode;
    } else {
        ListNode* temp = *headRef;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

Insert at the Beginning

void insertFront(ListNode** headRef, NodeData val) {
    ListNode* newNode = createNode(val);
    newNode->next = *headRef;
    *headRef = newNode;
}

Deletion Operations

Remove from the End

void removeEnd(ListNode** headRef) {
    if (*headRef == NULL) return;
    if ((*headRef)->next == NULL) {
        free(*headRef);
        *headRef = NULL;
    } else {
        ListNode* prev = NULL;
        ListNode* curr = *headRef;
        while (curr->next != NULL) {
            prev = curr;
            curr = curr->next;
        }
        prev->next = NULL;
        free(curr);
    }
}

Remove from the Begnining

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

Searching

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

Insertion at a Specific Position

Insert Before a Given Node

void insertBefore(ListNode** headRef, ListNode* targetNode, NodeData val) {
    if (targetNode == NULL) return;
    if (*headRef == targetNode) {
        insertFront(headRef, val);
    } else {
        ListNode* prev = *headRef;
        while (prev != NULL && prev->next != targetNode) {
            prev = prev->next;
        }
        if (prev != NULL) {
            ListNode* newNode = createNode(val);
            newNode->next = targetNode;
            prev->next = newNode;
        }
    }
}

Insert After a Given Node

void insertAfter(ListNode* targetNode, NodeData val) {
    if (targetNode == NULL) return;
    ListNode* newNode = createNode(val);
    newNode->next = targetNode->next;
    targetNode->next = newNode;
}

Deletion at a Specific Position

Remove a Given Node

void removeNode(ListNode** headRef, ListNode* targetNode) {
    if (*headRef == NULL || targetNode == NULL) return;
    if (*headRef == targetNode) {
        removeFront(headRef);
    } else {
        ListNode* prev = *headRef;
        while (prev != NULL && prev->next != targetNode) {
            prev = prev->next;
        }
        if (prev != NULL) {
            prev->next = targetNode->next;
            free(targetNode);
        }
    }
}

Remove the Node After a Given Node

void removeAfter(ListNode* targetNode) {
    if (targetNode == NULL || targetNode->next == NULL) return;
    ListNode* nodeToDelete = targetNode->next;
    targetNode->next = nodeToDelete->next;
    free(nodeToDelete);
}

Cleaning Up

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

Header File

#ifndef LIST_H
#define LIST_H

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

typedef int NodeData;
typedef struct ListNode {
    NodeData value;
    struct ListNode* next;
} ListNode;

ListNode* createNode(NodeData val);
void displayList(ListNode* head);
void insertEnd(ListNode** headRef, NodeData val);
void insertFront(ListNode** headRef, NodeData val);
void removeEnd(ListNode** headRef);
void removeFront(ListNode** headRef);
ListNode* findNode(ListNode* head, NodeData target);
void insertBefore(ListNode** headRef, ListNode* targetNode, NodeData val);
void insertAfter(ListNode* targetNode, NodeData val);
void removeNode(ListNode** headRef, ListNode* targetNode);
void removeAfter(ListNode* targetNode);
void destroyList(ListNode** headRef);

#endif