LINKED LISTS IN C PROGRAMMING

Linked List Fundamentals

What is a Linked List?

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.

  • Dynamic Size - Can grow or shrink during program execution
  • Efficient Insertions/Deletions - No need to shift elements
  • Memory Efficiency - Allocates memory as needed
// Basic Node Structure in C
struct Node {
    int data;
    struct Node* next;
};

Types of Linked Lists

Singly Linked List

Each node points only to the next node in sequence.

struct Node {
    int data;
    struct Node* next;
};
Doubly Linked List

Each node has pointers to both next and previous nodes.

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
Circular Linked List

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

// Circular variation of
// either singly or doubly
// linked list

Linked List Operations

# Operation Description Complexity Code Snippet
1 Insert at Head Add new node at the beginning of the list O(1) 
void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}
2 Insert at Tail Add new node at the end of the list O(n) 
void insertAtTail(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    
    if(*head == NULL) {
        *head = newNode;
        return;
    }
    
    struct Node* temp = *head;
    while(temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}
3 Delete by Value Remove first occurrence of a specific value O(n) 
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);
}
4 Search Element Check if a value exists in the list O(n) 
bool search(struct Node* head, int key) {
    struct Node* current = head;
    while(current != NULL) {
        if(current->data == key)
            return true;
        current = current->next;
    }
    return false;
}
5 Traversal Visit each node of the list O(n) 
void printList(struct Node* node) {
    while(node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
6 Reverse List Reverse the order of nodes in the list O(n) 
void reverse(struct Node** head) {
    struct Node *prev = NULL, *current = *head, *next = NULL;
    
    while(current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head = prev;
}

Advanced Linked List Techniques

Cycle Detection (Floyd's Algorithm)

Detect cycles in a linked list using fast and slow pointers.

bool hasCycle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    
    while(fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) return true;
    }
    return false;
}
Time Complexity: O(n), Space: O(1)
Find Middle Element

Find the middle node using fast and slow pointers.

struct Node* findMiddle(struct Node* head) {
    struct Node *slow = head, *fast = head;
    
    while(fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
Time Complexity: O(n), Space: O(1)
Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list.

struct Node* mergeLists(struct Node* l1, struct Node* l2) {
    if(l1 == NULL) return l2;
    if(l2 == NULL) return l1;
    
    if(l1->data < l2->data) {
        l1->next = mergeLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeLists(l1, l2->next);
        return l2;
    }
}
Time Complexity: O(n+m)
Remove Nth Node from End

Remove the nth node from the end of the list.

struct Node* removeNthFromEnd(struct Node* head, int n) {
    struct Node *fast = head, *slow = head;
    
    for(int i = 0; i < n; i++) fast = fast->next;
    
    if(fast == NULL) return head->next;
    
    while(fast->next != NULL) {
        slow = slow->next;
        fast = fast->next;
    }
    slow->next = slow->next->next;
    return head;
}
Time Complexity: O(n)
Palindrome Check

Check if a linked list is a palindrome.

bool isPalindrome(struct Node* head) {
    struct Node *slow = head, *fast = head, *prev = NULL, *temp;
    
    // Find middle and reverse first half
    while(fast && fast->next) {
        fast = fast->next->next;
        temp = slow->next;
        slow->next = prev;
        prev = slow;
        slow = temp;
    }
    
    // Handle odd length
    if(fast) slow = slow->next;
    
    // Compare two halves
    while(slow) {
        if(prev->data != slow->data) return false;
        prev = prev->next;
        slow = slow->next;
    }
    return true;
}
Time Complexity: O(n), Space: O(1)
Intersection Point

Find the intersection node of two linked lists.

struct Node *getIntersectionNode(struct Node *headA, struct Node *headB) {
    struct Node *a = headA, *b = headB;
    
    while(a != b) {
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;
}
Time Complexity: O(m+n)

Linked List Problem-Solving Patterns

# Pattern Description Example Problems
1 Two Pointer Technique Use fast and slow pointers to solve problems with optimal time and space complexity
  • Middle of linked list
  • Cycle detection
  • Palindrome check
2 Dummy Node Technique Create a dummy node to simplify edge cases in list manipulation
  • Merge two sorted lists
  • Remove elements
  • Partition list
3 Recursion Solve problems by breaking them down into smaller subproblems
  • Reverse linked list
  • Merge sorted lists
  • Tree-like problems
4 Pointer Manipulation Carefully manipulate node pointers to achieve desired structure
  • Reverse nodes in k-groups
  • Swap nodes in pairs
  • Rotate list
5 Hybrid Data Structures Combine linked lists with other data structures for efficient solutions
  • LRU Cache (list + hashmap)
  • LFU Cache
  • Browser history
Related Data Structure Resources
Arrays
Stacks
Trees
Graphs