Introduction to Singly Linked Lists

A singly linked list is a fundamental data structure consisting of nodes where each node contains data and a pointer to the next node in the sequence. Unlike arrays, linked lists don't require contiguous memory allocation, making them flexible for dynamic data storage.

The structure resembles a train where each carriage (node) is connected to the next one. Each carriage exists independently, and adding or removing carraiges doesn't affect the others' operation.

Node Structure

Each node in a linked list has two components:

1. Data field: Stores the actual value
2. Pointer field: Contains the address of the next node

The first node is called the head node, and the last node points to NULL, indicating the end of the list.

Linked List Implementation

Node Definition

We define a node structure using C:

struct Node {
    int value;        // Data field
    struct Node* next; // Pointer to next node
};

To make our implemantation flexible, we can use a typedef for the data type:

typedef int DataType;

Creating a New Node

Before implemetning operations, we need a function to create new nodes:

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

Insertion Operations

Insertion at the End (Tail Insertion)

void insertAtEnd(Node** head, DataType data) {
    Node* newNode = createNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

We use a double pointer (Node**) to handle the case when the list is empty.

Insertion at the Beginning (Head Insertion)

void insertAtBeginning(Node** head, DataType data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

Deletion Operations

Deletion at the End (Tail Deletion)

void deleteAtEnd(Node** head) {
    if (*head == NULL) return;
    
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    
    Node* current = *head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    free(current->next);
    current->next = NULL;
}

Deletion at the Beginning (Head Deletion)

void deleteAtBeginning(Node** head) {
    if (*head == NULL) return;
    
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

Searching in a Linked List

Node* searchNode(Node* head, DataType data) {
    Node* current = head;
    while (current != NULL) {
        if (current->value == data) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

Insertion at a Specific Position

Before a Given Node

void insertBeforeNode(Node** head, Node* targetNode, DataType data) {
    if (targetNode == NULL) return;
    
    if (*head == targetNode) {
        insertAtBeginning(head, data);
        return;
    }
    
    Node* current = *head;
    while (current != NULL && current->next != targetNode) {
        current = current->next;
    }
    
    if (current == NULL) {
        printf("Target node not found in the list\n");
        return;
    }
    
    Node* newNode = createNode(data);
    newNode->next = targetNode;
    current->next = newNode;
}

After a Given Node

void insertAfterNode(Node* prevNode, DataType data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL\n");
        return;
    }
    
    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

Deleting a Specific Node

void deleteNode(Node** head, Node* targetNode) {
    if (*head == NULL || targetNode == NULL) return;
    
    if (*head == targetNode) {
        deleteAtBeginning(head);
        return;
    }
    
    Node* current = *head;
    while (current != NULL && current->next != targetNode) {
        current = current->next;
    }
    
    if (current == NULL) {
        printf("Target node not found in the list\n");
        return;
    }
    
    current->next = targetNode->next;
    free(targetNode);
}

Printing the Linked List

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

Destroying the Linked List

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

Example Usage

int main() {
    Node* list = NULL;
    
    // Insert elements
    insertAtEnd(&list, 10);
    insertAtEnd(&list, 20);
    insertAtEnd(&list, 30);
    insertAtBeginning(&list, 5);
    
    // Print the list
    printf("Initial list: ");
    printList(list);
    
    // Search for an element
    Node* foundNode = searchNode(list, 20);
    if (foundNode != NULL) {
        printf("Found element 20 in the list\n");
    }
    
    // Insert after a found node
    insertAfterNode(foundNode, 25);
    
    // Insert before a node
    insertBeforeNode(&list, foundNode, 15);
    
    // Print the modified list
    printf("Modified list: ");
    printList(list);
    
    // Delete elements
    deleteAtBeginning(&list);
    deleteAtEnd(&list);
    deleteNode(&list, foundNode);
    
    // Print the final list
    printf("Final list: ");
    printList(list);
    
    // Clean up
    destroyList(&list);
    
    return 0;
}