Linked Lists

A linked list is a linear data structure in which elements (called nodes) are connected using pointers instead of being stored in contiguous memory (as in arrays). Each node is dynamically allocated using malloc() and must be freed using free() once no longer needed, to prevent memory leaks. Each node contains:

• Data: the value stored
• Pointer (link): address of the next node

Structure of a Node in C

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

A linked list is a chain of such nodes, connected by their next pointers.

Advantages of using a Linked List

• Dynamic size: memory allocated as needed (no fixed size like arrays)
• Efficient insertion and deletion: no shifting of elements required
• Memory utilization: suitable when memory is fragmented

Disadvantages of using a Linked List

• No random access: must traverse sequentially to reach an element
• Extra memory overhead: each node stores a pointer
• Poor cache locality: nodes scattered in memory
• Reverse traversal is difficult in singly linked lists

When to Use

• Frequent insertions and deletions are required
• Memory size is unpredictable
• Data size grows or shrinks dynamically
• Use linked lists for dynamic memory and efficient insertions or deletions

When to Avoid

• Random access is needed
• Memory is very limited (pointer overhead matters)
• Avoid them when random access or cache performance is important

Applications of Linked Lists

• Implementation of stacks, queues, graphs, and hash tables
• Undo and redo operations in editors
• Memory management (free list, OS memory allocation)
• Polynomial arithmetic and big integer arithmetic
• Circular scheduling (for example, round-robin CPU scheduling)

Comparison: Array vs Linked List

Types of Linked Lists

Common Operations and Time Complexities

Example 1: Create and Traverse a Singly Linked List

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

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

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

int main() {
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = NULL;

    printList(head);

    return 0;
}

Output

10 -> 20 -> 30 -> NULL

Example 2: Insert at Beginning

void push(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}

Usage:

push(&head, 5);

Example 3: Delete a Node

void deleteNode(struct Node** head_ref, int key) {
    struct Node *temp = *head_ref, *prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

Example 4: Reverse a Linked List

struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* curr = head;
    struct Node* next = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Practice further by solving problems involving Linked Lists.