C Linked Lists

A linked list is one of the most fundamental and versatile data structures in C programming. Unlike arrays, linked lists are dynamic data structures that can grow or shrink during program execution.

What is a Linked List?

A linked list is a collection of nodes, where each node contains:

1. Data (or value)
2. A pointer (or reference) to the next node in the sequence

struct Node {
    int data;          // The value stored
    struct Node* next; // Pointer to the next node
};

Types of Linked Lists

1. Singly Linked List

• Each node points to the next node
• The last node points to NULL

/*
  Representation: A -> B -> C -> NULL
*/

2. Doubly Linked List

• Each node has two pointers: one to the next node and one to the previous node

struct DoubleNode {
    int data;
    struct DoubleNode* next;
    struct DoubleNode* prev;
};

/*
  Representation: NULL <- A <-> B <-> C -> NULL
*/

3. Circular Linked List

• The last node points back to the first node, forming a circle

/*
  Representation: A -> B -> C -> A (loops back)
*/

Basic Operations on Linked Lists

Creating a Node

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

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

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

Inserting a Node

1. At the Beginning

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

2. At the End

void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    
    // If the list is empty, make the new node the head
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    // Traverse to the last node
    struct Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    // Link the new node at the end
    current->next = newNode;
}

3. After a Given Node

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

Deleting a Node

1. Delete First Node

void deleteFirstNode(struct Node** head) {
    if (*head == NULL) {
        printf("List is already empty\n");
        return;
    }
    
    struct Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

2. Delete a Node with a Specific Value

void deleteNode(struct Node** head, int key) {
    struct Node *temp = *head, *prev = NULL;
    
    // If head node itself holds the key
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    
    // Search for the key to be deleted
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    // If key was not present in linked list
    if (temp == NULL) {
        printf("Key not found in the list\n");
        return;
    }
    
    // Unlink the node from linked list
    prev->next = temp->next;
    free(temp);
}

Traversing a Linked List

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

Complete Example: Singly Linked List Implementation

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

// Node structure
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Insert at the beginning
void insertAtBeginning(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// Insert at the end
void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    struct Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    current->next = newNode;
}

// Delete a node with given key
void deleteNode(struct Node** head, int key) {
    struct Node *temp = *head, *prev = NULL;
    
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    if (temp == NULL) {
        printf("Key not found in the list\n");
        return;
    }
    
    prev->next = temp->next;
    free(temp);
}

// Search for a node with given key
struct Node* search(struct Node* head, int key) {
    struct Node* current = head;
    
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    
    return NULL; // Not found
}

// Print the linked list
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// Free the entire linked list
void freeList(struct Node** head) {
    struct Node* current = *head;
    struct Node* next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    
    *head = NULL;
}

int main() {
    struct Node* head = NULL;
    
    // Insert some values
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtBeginning(&head, 5);
    insertAtEnd(&head, 30);
    
    printf("Linked List: ");
    printList(head);
    
    // Delete a node
    deleteNode(&head, 20);
    printf("After deleting 20: ");
    printList(head);
    
    // Search for a node
    int searchKey = 10;
    struct Node* foundNode = search(head, searchKey);
    if (foundNode != NULL) {
        printf("Node with value %d found\n", searchKey);
    } else {
        printf("Node with value %d not found\n", searchKey);
    }
    
    // Free the list
    freeList(&head);
    
    return 0;
}

Advantages of Linked Lists

1. Dynamic Size: Linked lists can grow or shrink at runtime
2. Efficient Insertion/Deletion: Inserting or deleting elements doesn't require shifting other elements
3. Memory Efficiency: They allocate memory as needed (no need to pre-allocate memory)

Disadvantages of Linked Lists

1. Random Access: No direct access to elements by index (must traverse from beginning)
2. Extra Memory: Requires extra memory for storing pointer information
3. Cache Performance: Poor cache locality compared to arrays

Applications of Linked Lists

1. Implementation of stacks and queues
2. Symbol tables in compilers
3. Dynamic memory allocation
4. Representation of sparse matrices
5. Undo functionality in applications

Common Linked List Problems

1. Finding the middle element
2. Detecting a loop in a linked list
3. Reversing a linked list
4. Finding the nth node from the end
5. Merging two sorted linked lists

---

Understanding linked lists is crucial for mastering more complex data structures and algorithms. This data structure serves as a building block for many advanced concepts in computer science.