Linked Lists in C

Singly linked lists are the simplest form of linked lists. Each node contains data and a single pointer to the next node. They are memory-efficient and perfect for applications that only need forward traversal.

Complete Implementation

// singly_linked_list.h
#ifndef SINGLY_LINKED_LIST_H
#define SINGLY_LINKED_LIST_H

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

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

// Function prototypes
Node *createNode(int data);
void insertAtBeginning(Node **head, int data);
void insertAtEnd(Node **head, int data);
void insertAfter(Node *prevNode, int data);
void deleteNode(Node **head, int key);
Node *search(Node *head, int key);
void printList(Node *head);
void freeList(Node **head);
int getLength(Node *head);

#endif

// singly_linked_list.c
#include "singly_linked_list.h"

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

// Insert at the beginning - O(1)
void insertAtBeginning(Node **head, int data) {
    Node *newNode = createNode(data);
    newNode->next = *head;  // Point new node to current head
    *head = newNode;        // Update head to new node
}

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

// Insert after a given node - O(1)
void insertAfter(Node *prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL\n");
        return;
    }
    Node *newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// Delete a node by value - O(n)
void deleteNode(Node **head, int key) {
    Node *current = *head;
    Node *prev = NULL;
    
    // If head node holds the key
    if (current != NULL && current->data == key) {
        *head = current->next;
        free(current);
        return;
    }
    
    // Search for the key
    while (current != NULL && current->data != key) {
        prev = current;
        current = current->next;
    }
    
    // Key not found
    if (current == NULL) {
        printf("Key %d not found in list\n", key);
        return;
    }
    
    // Unlink and free the node
    prev->next = current->next;
    free(current);
}

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

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

// Free all nodes
void freeList(Node **head) {
    Node *current = *head;
    Node *next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;
}

// Get length of list - O(n)
int getLength(Node *head) {
    int count = 0;
    Node *current = head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

Using the Singly Linked List

// main.c - Demonstration
#include "singly_linked_list.h"

int main() {
    Node *head = NULL;  // Start with empty list
    
    // Insert elements
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    printList(head);  // List: 10 -> 20 -> 30 -> NULL
    
    // Insert at beginning
    insertAtBeginning(&head, 5);
    printList(head);  // List: 5 -> 10 -> 20 -> 30 -> NULL
    
    // Insert after node with value 10
    Node *node10 = search(head, 10);
    if (node10 != NULL) {
        insertAfter(node10, 15);
    }
    printList(head);  // List: 5 -> 10 -> 15 -> 20 -> 30 -> NULL
    
    // Delete node
    deleteNode(&head, 15);
    printList(head);  // List: 5 -> 10 -> 20 -> 30 -> NULL
    
    printf("Length: %d\n", getLength(head));  // Length: 4
    
    // Clean up
    freeList(&head);
    return 0;
}

int countOccurrences(Node *head, int key) {
    int count = 0;
    Node *current = head;
    
    while (current != NULL) {
        if (current->data == key) {
            count++;
        }
        current = current->next;
    }
    
    return count;
}

// Usage:
// List: 1 -> 2 -> 1 -> 3 -> 1 -> NULL
// countOccurrences(head, 1) returns 3

void reverseList(Node **head) {
    Node *prev = NULL;
    Node *current = *head;
    Node *next = NULL;
    
    while (current != NULL) {
        next = current->next;    // Store next
        current->next = prev;    // Reverse the link
        prev = current;          // Move prev forward
        current = next;          // Move current forward
    }
    
    *head = prev;  // Update head to last node
}

// Visual:
// Before: 1 -> 2 -> 3 -> NULL
// After:  3 -> 2 -> 1 -> NULL

// Step by step:
// prev=NULL, curr=1, next=2: 1->NULL, prev=1, curr=2
// prev=1, curr=2, next=3: 2->1, prev=2, curr=3
// prev=2, curr=3, next=NULL: 3->2, prev=3, curr=NULL
// head = 3

Node *findMiddle(Node *head) {
    if (head == NULL) return NULL;
    
    Node *slow = head;  // Moves 1 step at a time
    Node *fast = head;  // Moves 2 steps at a time
    
    // When fast reaches end, slow is at middle
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

// Example:
// List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
// 
// Initial: slow=1, fast=1
// Step 1:  slow=2, fast=3
// Step 2:  slow=3, fast=5
// Step 3:  fast->next is NULL, stop
// Middle is 3

// For even length: 1 -> 2 -> 3 -> 4 -> NULL
// Returns 3 (second middle element)

Doubly linked lists extend singly linked lists by adding a pointer to the previous node. This allows bidirectional traversal and makes some operations more efficient, at the cost of extra memory per node.

Doubly Linked List Structure

// Doubly linked list node
typedef struct DNode {
    int data;
    struct DNode *prev;  // Pointer to previous node
    struct DNode *next;  // Pointer to next node
} DNode;

// Visual representation:
// NULL <- [prev|10|next] <-> [prev|20|next] <-> [prev|30|next] -> NULL
//              ↑                   ↑                   ↑
//            head                                    tail

Complete Implementation

// doubly_linked_list.c
#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

// Create a new node
DNode *createDNode(int data) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Insert at the beginning - O(1)
void insertAtBeginningD(DNode **head, int data) {
    DNode *newNode = createDNode(data);
    
    newNode->next = *head;
    
    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    
    *head = newNode;
}

// Insert at the end - O(n) without tail pointer
void insertAtEndD(DNode **head, int data) {
    DNode *newNode = createDNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    DNode *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    current->next = newNode;
    newNode->prev = current;
}

// Insert after a given node - O(1)
void insertAfterD(DNode *prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL\n");
        return;
    }
    
    DNode *newNode = createDNode(data);
    
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    
    if (prevNode->next != NULL) {
        prevNode->next->prev = newNode;
    }
    
    prevNode->next = newNode;
}

// Delete a node - O(1) if node pointer is given
void deleteDNode(DNode **head, DNode *nodeToDelete) {
    if (*head == NULL || nodeToDelete == NULL) {
        return;
    }
    
    // If deleting head
    if (*head == nodeToDelete) {
        *head = nodeToDelete->next;
    }
    
    // Update next node's prev pointer
    if (nodeToDelete->next != NULL) {
        nodeToDelete->next->prev = nodeToDelete->prev;
    }
    
    // Update prev node's next pointer
    if (nodeToDelete->prev != NULL) {
        nodeToDelete->prev->next = nodeToDelete->next;
    }
    
    free(nodeToDelete);
}

// Print forward
void printForward(DNode *head) {
    DNode *current = head;
    printf("Forward:  ");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// Print backward (from tail)
void printBackward(DNode *head) {
    if (head == NULL) {
        printf("Backward: NULL\n");
        return;
    }
    
    // Go to tail
    DNode *current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    // Print backward
    printf("Backward: ");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->prev;
    }
    printf("NULL\n");
}

Using Doubly Linked List

int main() {
    DNode *head = NULL;
    
    insertAtEndD(&head, 10);
    insertAtEndD(&head, 20);
    insertAtEndD(&head, 30);
    
    printForward(head);   // Forward:  10 <-> 20 <-> 30 <-> NULL
    printBackward(head);  // Backward: 30 <-> 20 <-> 10 <-> NULL
    
    insertAtBeginningD(&head, 5);
    printForward(head);   // Forward:  5 <-> 10 <-> 20 <-> 30 <-> NULL
    
    // Delete node with value 20
    DNode *node20 = head->next->next;  // Navigate to 20
    deleteDNode(&head, node20);
    printForward(head);   // Forward:  5 <-> 10 <-> 30 <-> NULL
    
    return 0;
}

int countFromTail(DNode *head) {
    if (head == NULL) return 0;
    
    // Find tail
    DNode *tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    
    // Count backward
    int count = 0;
    while (tail != NULL) {
        count++;
        tail = tail->prev;
    }
    
    return count;
}

void insertBefore(DNode **head, DNode *nextNode, int data) {
    if (nextNode == NULL) {
        printf("Next node cannot be NULL\n");
        return;
    }
    
    DNode *newNode = createDNode(data);
    
    newNode->prev = nextNode->prev;
    newNode->next = nextNode;
    
    // If inserting before head
    if (nextNode->prev == NULL) {
        *head = newNode;
    } else {
        nextNode->prev->next = newNode;
    }
    
    nextNode->prev = newNode;
}

// Usage:
// Before: 10 <-> 20 <-> 30
// insertBefore(&head, node20, 15)
// After:  10 <-> 15 <-> 20 <-> 30

Circular linked lists have no NULL at the end - the last node points back to the first node. This creates a continuous loop, useful for applications like round-robin scheduling, circular buffers, and multiplayer game turns.

Circular Singly Linked List

// Circular singly linked list
// Visual: head -> [10] -> [20] -> [30] -+
//          ^                            |
//          +----------------------------+

typedef struct CNode {
    int data;
    struct CNode *next;
} CNode;

// Create a new node
CNode *createCNode(int data) {
    CNode *newNode = (CNode *)malloc(sizeof(CNode));
    if (newNode == NULL) exit(1);
    newNode->data = data;
    newNode->next = newNode;  // Points to itself initially
    return newNode;
}

// Insert at the end of circular list
void insertAtEndC(CNode **head, int data) {
    CNode *newNode = createCNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    // Find the last node (the one pointing to head)
    CNode *current = *head;
    while (current->next != *head) {
        current = current->next;
    }
    
    // Insert new node
    current->next = newNode;
    newNode->next = *head;
}

// Insert at the beginning
void insertAtBeginningC(CNode **head, int data) {
    CNode *newNode = createCNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    // Find the last node
    CNode *current = *head;
    while (current->next != *head) {
        current = current->next;
    }
    
    newNode->next = *head;
    current->next = newNode;
    *head = newNode;
}

// Print circular list (be careful of infinite loop!)
void printCircular(CNode *head) {
    if (head == NULL) {
        printf("Empty list\n");
        return;
    }
    
    CNode *current = head;
    printf("Circular List: ");
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);
    printf("(back to %d)\n", head->data);
}

// Delete a node from circular list
void deleteCNode(CNode **head, int key) {
    if (*head == NULL) return;
    
    CNode *current = *head;
    CNode *prev = NULL;
    
    // Find the node to delete
    while (current->data != key) {
        if (current->next == *head) {
            printf("Key %d not found\n", key);
            return;
        }
        prev = current;
        current = current->next;
    }
    
    // Only one node in list
    if (current->next == current) {
        *head = NULL;
        free(current);
        return;
    }
    
    // Deleting head
    if (current == *head) {
        // Find last node
        prev = *head;
        while (prev->next != *head) {
            prev = prev->next;
        }
        *head = current->next;
        prev->next = *head;
    } else {
        prev->next = current->next;
    }
    
    free(current);
}

Circular Doubly Linked List

// Circular doubly linked list
typedef struct CDNode {
    int data;
    struct CDNode *prev;
    struct CDNode *next;
} CDNode;

// Visual:
//    +------------------------------------------+
//    |                                          |
//    v                                          |
//   [prev|10|next] <-> [prev|20|next] <-> [prev|30|next]
//    ^                                          |
//    |                                          |
//    +------------------------------------------+

// Insert at end
void insertAtEndCD(CDNode **head, int data) {
    CDNode *newNode = (CDNode *)malloc(sizeof(CDNode));
    newNode->data = data;
    
    if (*head == NULL) {
        newNode->next = newNode;
        newNode->prev = newNode;
        *head = newNode;
        return;
    }
    
    CDNode *tail = (*head)->prev;  // Last node
    
    newNode->next = *head;
    newNode->prev = tail;
    tail->next = newNode;
    (*head)->prev = newNode;
}

Real-World Application: Round Robin

// Round-robin process scheduler simulation
typedef struct Process {
    int pid;
    int burstTime;
    struct Process *next;
} Process;

void roundRobinDemo() {
    Process *queue = NULL;
    
    // Add processes
    insertProcess(&queue, 1, 10);
    insertProcess(&queue, 2, 5);
    insertProcess(&queue, 3, 8);
    
    int timeQuantum = 3;
    Process *current = queue;
    
    printf("Round Robin Scheduling (quantum=%d):\n", timeQuantum);
    
    while (queue != NULL) {
        printf("Running Process %d (remaining: %d)\n", 
               current->pid, current->burstTime);
        
        if (current->burstTime <= timeQuantum) {
            // Process completes
            printf("Process %d completed!\n", current->pid);
            Process *toDelete = current;
            current = current->next;
            deleteProcess(&queue, toDelete->pid);
            if (queue == NULL) break;
        } else {
            // Process needs more time
            current->burstTime -= timeQuantum;
            current = current->next;
        }
    }
}

// Using Floyd's cycle detection (tortoise and hare)
int isCircular(Node *head) {
    if (head == NULL) return 0;
    
    Node *slow = head;
    Node *fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return 1;  // Cycle detected
        }
    }
    
    return 0;  // No cycle
}

// Simple check for circular list that loops back to head
int isCircularToHead(CNode *head) {
    if (head == NULL) return 0;
    
    CNode *current = head->next;
    while (current != NULL && current != head) {
        current = current->next;
    }
    
    return current == head;
}

void splitCircularList(CNode *head, CNode **head1, CNode **head2) {
    if (head == NULL) {
        *head1 = NULL;
        *head2 = NULL;
        return;
    }
    
    CNode *slow = head;
    CNode *fast = head;
    
    // Find middle using slow/fast pointers
    while (fast->next != head && fast->next->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // If even number of nodes, move fast one more
    if (fast->next->next == head) {
        fast = fast->next;
    }
    
    // Set up first half
    *head1 = head;
    
    // Set up second half
    *head2 = slow->next;
    
    // Make first half circular
    slow->next = *head1;
    
    // Make second half circular
    // Find end of second half (currently points to original head)
    CNode *temp = *head2;
    while (temp->next != head) {
        temp = temp->next;
    }
    temp->next = *head2;
}

// Example:
// Original: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> (back to 1)
// After split:
// head1: 1 -> 2 -> 3 -> (back to 1)
// head2: 4 -> 5 -> 6 -> (back to 4)

Beyond basic CRUD operations, linked lists support many powerful algorithms. These operations are common interview questions and demonstrate deep understanding of pointer manipulation.

Merge Two Sorted Lists

// Merge two sorted linked lists into one sorted list
Node *mergeSortedLists(Node *list1, Node *list2) {
    // Create dummy head to simplify code
    Node dummy;
    dummy.next = NULL;
    Node *tail = &dummy;
    
    while (list1 != NULL && list2 != NULL) {
        if (list1->data <= list2->data) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    
    // Attach remaining nodes
    if (list1 != NULL) {
        tail->next = list1;
    } else {
        tail->next = list2;
    }
    
    return dummy.next;
}

// Usage:
// list1: 1 -> 3 -> 5 -> NULL
// list2: 2 -> 4 -> 6 -> NULL
// merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Detect and Remove Loop

// Detect if list has a loop (cycle)
Node *detectLoop(Node *head) {
    Node *slow = head;
    Node *fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return slow;  // Meeting point inside loop
        }
    }
    
    return NULL;  // No loop
}

// Remove loop from list
void removeLoop(Node *head) {
    Node *meetPoint = detectLoop(head);
    if (meetPoint == NULL) return;  // No loop
    
    // Find loop start
    Node *ptr1 = head;
    Node *ptr2 = meetPoint;
    
    while (ptr1->next != ptr2->next) {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    
    // ptr2 is now at the node before loop start
    ptr2->next = NULL;  // Break the loop
}

Find Nth Node from End

// Find nth node from end in one pass
Node *findNthFromEnd(Node *head, int n) {
    Node *first = head;
    Node *second = head;
    
    // Move first pointer n nodes ahead
    for (int i = 0; i < n; i++) {
        if (first == NULL) {
            return NULL;  // List has fewer than n nodes
        }
        first = first->next;
    }
    
    // Move both pointers until first reaches end
    while (first != NULL) {
        first = first->next;
        second = second->next;
    }
    
    return second;  // second is now nth from end
}

// Example:
// List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
// findNthFromEnd(head, 2) returns node with value 4

Check if Palindrome

// Check if linked list is palindrome
int isPalindrome(Node *head) {
    if (head == NULL || head->next == NULL) {
        return 1;  // Empty or single node is palindrome
    }
    
    // Find middle
    Node *slow = head;
    Node *fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // Reverse second half
    Node *secondHalf = reverseListReturn(slow->next);
    
    // Compare first and second half
    Node *p1 = head;
    Node *p2 = secondHalf;
    int result = 1;
    
    while (p2 != NULL) {
        if (p1->data != p2->data) {
            result = 0;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    
    // Restore original list (optional)
    slow->next = reverseListReturn(secondHalf);
    
    return result;
}

// Helper: Reverse and return new head
Node *reverseListReturn(Node *head) {
    Node *prev = NULL;
    Node *current = head;
    while (current != NULL) {
        Node *next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

// Example:
// 1 -> 2 -> 3 -> 2 -> 1 is palindrome
// 1 -> 2 -> 3 -> 4 -> 5 is not palindrome

Time Complexity Summary

void removeDuplicates(Node *head) {
    if (head == NULL) return;
    
    Node *current = head;
    
    while (current->next != NULL) {
        if (current->data == current->next->data) {
            // Remove duplicate
            Node *duplicate = current->next;
            current->next = current->next->next;
            free(duplicate);
        } else {
            current = current->next;
        }
    }
}

// Example:
// Before: 1 -> 1 -> 2 -> 3 -> 3 -> 3 -> NULL
// After:  1 -> 2 -> 3 -> NULL

// Numbers are stored in reverse order
// 342 is stored as 2 -> 4 -> 3
// 465 is stored as 5 -> 6 -> 4
// Sum: 807 stored as 7 -> 0 -> 8

Node *addTwoNumbers(Node *l1, Node *l2) {
    Node dummy;
    dummy.next = NULL;
    Node *tail = &dummy;
    int carry = 0;
    
    while (l1 != NULL || l2 != NULL || carry != 0) {
        int sum = carry;
        
        if (l1 != NULL) {
            sum += l1->data;
            l1 = l1->next;
        }
        
        if (l2 != NULL) {
            sum += l2->data;
            l2 = l2->next;
        }
        
        carry = sum / 10;
        
        Node *newNode = createNode(sum % 10);
        tail->next = newNode;
        tail = newNode;
    }
    
    return dummy.next;
}

// Example:
// l1: 2 -> 4 -> 3 (represents 342)
// l2: 5 -> 6 -> 4 (represents 465)
// Result: 7 -> 0 -> 8 (represents 807)