Nikhil Learn Hub - Linked Lists in C Programming

Introduction to Linked Lists

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence.

Unlike arrays, linked lists don't require contiguous memory allocation, allowing dynamic memory usage.

Basic Node Structure in C:

struct Node {
    int data;           // Data stored in the node
    struct Node* next;  // Pointer to the next node
};

Key Characteristics:

Dynamic size (can grow/shrink during runtime)
Efficient insertions/deletions (O(1) at head)
No random access (sequential access only)
Extra memory needed for pointers

Types of Linked Lists

Singly Linked List

Each node points only to the next node in sequence.

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

Insert/Delete at head: O(1) Search: O(n)

Doubly Linked List

Nodes contain pointers to both next and previous nodes.

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

More memory Bidirectional traversal

Circular Linked List

Last node points back to the first node (can be singly or doubly linked).

// Circular singly linked list
struct Node* last->next = head;

Circular traversal Useful for round-robin

Basic Operations

Creating a Linked List

// 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;
}

Insertion Operations

1. Insert at Beginning

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

2. Insert at End

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

Deletion Operations

1. Delete by Value

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) return;
    
    prev->next = temp->next;
    free(temp);
}

Common Linked List Problems

Reverse a Linked List

// Iterative method
struct Node* reverseList(struct Node* head) {
    struct Node *prev = NULL, *current = head, *next = NULL;
    
    while (current != NULL) {
        next = current->next;  // Store next node
        current->next = prev;  // Reverse current node's pointer
        prev = current;         // Move pointers one position ahead
        current = next;
    }
    
    return prev;  // New head
}

Time Complexity: O(n) | Space Complexity: O(1)

Detect Cycle in Linked List

Floyd's Cycle-Finding Algorithm (Tortoise and Hare):

int hasCycle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;          // Moves one step
        fast = fast->next->next;    // Moves two steps
        
        if (slow == fast) {         // Cycle detected
            return 1;
        }
    }
    
    return 0;  // No cycle
}

Efficiency: O(n) time with O(1) space

Merge Two Sorted Lists

struct Node* mergeSortedLists(struct Node* l1, struct Node* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    
    if (l1->data < l2->data) {
        l1->next = mergeSortedLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeSortedLists(l1, l2->next);
        return l2;
    }
}

Note: This is the recursive approach (O(n+m) time, O(n+m) space due to recursion stack)

Best Practices & Common Pitfalls

Tips for Working with Linked Lists

Always check for NULL pointers: Before dereferencing any pointer, verify it's not NULL.
Memory management: Free allocated memory to prevent leaks when deleting nodes.
Edge cases: Handle empty lists, single-node lists, and operations at head/tail.
Pointer manipulation: Draw diagrams to visualize pointer changes during complex operations.
Dummy nodes: Use dummy nodes to simplify edge cases in some problems.
Debugging: Implement a print function to verify list contents during development.

LINKED LISTS IN C PROGRAMMING