Linked Lists in C

Table of Contents

1. •Introduction to Linked Lists
2. •Why Use Linked Lists
3. •Singly Linked Lists
4. •Doubly Linked Lists
5. •Circular Linked Lists
6. •Basic Operations
7. •Advanced Operations
8. •Memory Management
9. •Common Algorithms
10. •Applications
11. •Best Practices
12. •Common Pitfalls

---

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 list elements are not stored in contiguous memory locations.

Basic Concept

Array:
+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |  Contiguous memory
+---+---+---+---+---+

Linked List:
+------+    +------+    +------+    +------+
| 1 | -+->  | 2 | -+->  | 3 | -+->  | 4 | NULL
+------+    +------+    +------+    +------+
  Node       Node        Node        Node

Node Structure

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

/* Using typedef for convenience */
typedef struct Node {
    int data;
    struct Node *next;
} Node;

Creating a Node

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

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

Node *create_node(int data) {
    Node *new_node = (Node *)malloc(sizeof(Node));
    if (new_node == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

---

Why Use Linked Lists

Advantages Over Arrays

When to Use Linked Lists

1. •Dynamic size needed: Unknown number of elements
2. •Frequent insertions/deletions: Especially at beginning
3. •No random access required: Sequential access is fine
4. •Memory fragmentation: Can utilize non-contiguous memory
5. •Implementing other data structures: Stacks, queues, graphs

When NOT to Use Linked Lists

1. •Random access needed: Arrays are O(1)
2. •Memory is limited: Extra overhead per node
3. •Cache performance matters: Arrays have better locality
4. •Size is known and fixed: Arrays are simpler

---

Singly Linked Lists

A singly linked list has nodes with data and one pointer to the next node.

Structure Definition

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

typedef struct {
    SLLNode *head;
    SLLNode *tail;  /* Optional: for O(1) append */
    size_t size;    /* Optional: for O(1) size query */
} SinglyLinkedList;

Creating a Singly Linked List

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

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

typedef struct {
    SLLNode *head;
    SLLNode *tail;
    size_t size;
} SinglyLinkedList;

/* Create empty list */
SinglyLinkedList *sll_create(void) {
    SinglyLinkedList *list = malloc(sizeof(SinglyLinkedList));
    if (list == NULL) return NULL;

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    return list;
}

/* Create a new node */
SLLNode *sll_create_node(int data) {
    SLLNode *node = malloc(sizeof(SLLNode));
    if (node == NULL) return NULL;

    node->data = data;
    node->next = NULL;
    return node;
}

/* Free entire list */
void sll_free(SinglyLinkedList *list) {
    if (list == NULL) return;

    SLLNode *current = list->head;
    while (current != NULL) {
        SLLNode *next = current->next;
        free(current);
        current = next;
    }
    free(list);
}

Basic Operations

/* Insert at beginning - O(1) */
int sll_prepend(SinglyLinkedList *list, int data) {
    SLLNode *node = sll_create_node(data);
    if (node == NULL) return -1;

    node->next = list->head;
    list->head = node;

    if (list->tail == NULL) {
        list->tail = node;
    }

    list->size++;
    return 0;
}

/* Insert at end - O(1) with tail pointer */
int sll_append(SinglyLinkedList *list, int data) {
    SLLNode *node = sll_create_node(data);
    if (node == NULL) return -1;

    if (list->tail == NULL) {
        list->head = node;
        list->tail = node;
    } else {
        list->tail->next = node;
        list->tail = node;
    }

    list->size++;
    return 0;
}

/* Insert after specific node - O(1) */
int sll_insert_after(SinglyLinkedList *list, SLLNode *prev, int data) {
    if (prev == NULL) return -1;

    SLLNode *node = sll_create_node(data);
    if (node == NULL) return -1;

    node->next = prev->next;
    prev->next = node;

    if (prev == list->tail) {
        list->tail = node;
    }

    list->size++;
    return 0;
}

/* Delete first node - O(1) */
int sll_delete_first(SinglyLinkedList *list) {
    if (list->head == NULL) return -1;

    SLLNode *temp = list->head;
    list->head = list->head->next;

    if (list->head == NULL) {
        list->tail = NULL;
    }

    free(temp);
    list->size--;
    return 0;
}

/* Delete specific value - O(n) */
int sll_delete_value(SinglyLinkedList *list, int value) {
    if (list->head == NULL) return -1;

    /* Check if head needs to be deleted */
    if (list->head->data == value) {
        return sll_delete_first(list);
    }

    /* Find node before the one to delete */
    SLLNode *prev = list->head;
    while (prev->next != NULL && prev->next->data != value) {
        prev = prev->next;
    }

    if (prev->next == NULL) return -1;  /* Value not found */

    SLLNode *temp = prev->next;
    prev->next = temp->next;

    if (temp == list->tail) {
        list->tail = prev;
    }

    free(temp);
    list->size--;
    return 0;
}

/* Search for value - O(n) */
SLLNode *sll_search(SinglyLinkedList *list, int value) {
    SLLNode *current = list->head;
    while (current != NULL) {
        if (current->data == value) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

/* Get node at index - O(n) */
SLLNode *sll_get(SinglyLinkedList *list, size_t index) {
    if (index >= list->size) return NULL;

    SLLNode *current = list->head;
    for (size_t i = 0; i < index; i++) {
        current = current->next;
    }
    return current;
}

/* Print list */
void sll_print(SinglyLinkedList *list) {
    printf("[");
    SLLNode *current = list->head;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) {
            printf(" -> ");
        }
        current = current->next;
    }
    printf("]\n");
}

---

Doubly Linked Lists

A doubly linked list has nodes with pointers to both the next and previous nodes.

Structure Definition

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

typedef struct {
    DLLNode *head;
    DLLNode *tail;
    size_t size;
} DoublyLinkedList;

Visual Representation

      NULL
        ^
        |
    +------+     +------+     +------+
    | prev |<--->| prev |<--->| prev |
    |  10  |     |  20  |     |  30  |
    | next |<--->| next |<--->| next |
    +------+     +------+     +------+
        ^                         |
        |                         v
      HEAD                      TAIL->NULL

Complete Implementation

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

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

typedef struct {
    DLLNode *head;
    DLLNode *tail;
    size_t size;
} DoublyLinkedList;

/* Create empty list */
DoublyLinkedList *dll_create(void) {
    DoublyLinkedList *list = malloc(sizeof(DoublyLinkedList));
    if (list == NULL) return NULL;

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    return list;
}

/* Create a new node */
DLLNode *dll_create_node(int data) {
    DLLNode *node = malloc(sizeof(DLLNode));
    if (node == NULL) return NULL;

    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

/* Insert at beginning - O(1) */
int dll_prepend(DoublyLinkedList *list, int data) {
    DLLNode *node = dll_create_node(data);
    if (node == NULL) return -1;

    if (list->head == NULL) {
        list->head = node;
        list->tail = node;
    } else {
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }

    list->size++;
    return 0;
}

/* Insert at end - O(1) */
int dll_append(DoublyLinkedList *list, int data) {
    DLLNode *node = dll_create_node(data);
    if (node == NULL) return -1;

    if (list->tail == NULL) {
        list->head = node;
        list->tail = node;
    } else {
        node->prev = list->tail;
        list->tail->next = node;
        list->tail = node;
    }

    list->size++;
    return 0;
}

/* Insert before specific node - O(1) */
int dll_insert_before(DoublyLinkedList *list, DLLNode *ref, int data) {
    if (ref == NULL) return -1;

    DLLNode *node = dll_create_node(data);
    if (node == NULL) return -1;

    node->next = ref;
    node->prev = ref->prev;

    if (ref->prev != NULL) {
        ref->prev->next = node;
    } else {
        list->head = node;
    }
    ref->prev = node;

    list->size++;
    return 0;
}

/* Insert after specific node - O(1) */
int dll_insert_after(DoublyLinkedList *list, DLLNode *ref, int data) {
    if (ref == NULL) return -1;

    DLLNode *node = dll_create_node(data);
    if (node == NULL) return -1;

    node->prev = ref;
    node->next = ref->next;

    if (ref->next != NULL) {
        ref->next->prev = node;
    } else {
        list->tail = node;
    }
    ref->next = node;

    list->size++;
    return 0;
}

/* Delete node - O(1) */
int dll_delete_node(DoublyLinkedList *list, DLLNode *node) {
    if (node == NULL || list->head == NULL) return -1;

    if (node->prev != NULL) {
        node->prev->next = node->next;
    } else {
        list->head = node->next;
    }

    if (node->next != NULL) {
        node->next->prev = node->prev;
    } else {
        list->tail = node->prev;
    }

    free(node);
    list->size--;
    return 0;
}

/* Delete first node - O(1) */
int dll_delete_first(DoublyLinkedList *list) {
    return dll_delete_node(list, list->head);
}

/* Delete last node - O(1) */
int dll_delete_last(DoublyLinkedList *list) {
    return dll_delete_node(list, list->tail);
}

/* Print forward */
void dll_print_forward(DoublyLinkedList *list) {
    printf("Forward: [");
    DLLNode *current = list->head;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) {
            printf(" <-> ");
        }
        current = current->next;
    }
    printf("]\n");
}

/* Print backward */
void dll_print_backward(DoublyLinkedList *list) {
    printf("Backward: [");
    DLLNode *current = list->tail;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->prev != NULL) {
            printf(" <-> ");
        }
        current = current->prev;
    }
    printf("]\n");
}

/* Free entire list */
void dll_free(DoublyLinkedList *list) {
    if (list == NULL) return;

    DLLNode *current = list->head;
    while (current != NULL) {
        DLLNode *next = current->next;
        free(current);
        current = next;
    }
    free(list);
}

---

Circular Linked Lists

In a circular linked list, the last node points back to the first node, forming a circle.

Singly Circular Linked List

    +------+     +------+     +------+
    | 10   |---->| 20   |---->| 30   |
    +------+     +------+     +------+
       ^                          |
       |                          |
       +--------------------------+

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

typedef struct {
    CSLLNode *tail;  /* Point to last node for efficient operations */
    size_t size;
} CircularSLL;

/* Create empty circular list */
CircularSLL *csll_create(void) {
    CircularSLL *list = malloc(sizeof(CircularSLL));
    if (list == NULL) return NULL;

    list->tail = NULL;
    list->size = 0;
    return list;
}

/* Insert at beginning - O(1) */
int csll_prepend(CircularSLL *list, int data) {
    CSLLNode *node = malloc(sizeof(CSLLNode));
    if (node == NULL) return -1;
    node->data = data;

    if (list->tail == NULL) {
        node->next = node;  /* Point to itself */
        list->tail = node;
    } else {
        node->next = list->tail->next;  /* Point to head */
        list->tail->next = node;
    }

    list->size++;
    return 0;
}

/* Insert at end - O(1) */
int csll_append(CircularSLL *list, int data) {
    int result = csll_prepend(list, data);
    if (result == 0) {
        list->tail = list->tail->next;  /* Move tail to new node */
    }
    return result;
}

/* Delete first node - O(1) */
int csll_delete_first(CircularSLL *list) {
    if (list->tail == NULL) return -1;

    CSLLNode *head = list->tail->next;

    if (head == list->tail) {
        /* Only one node */
        list->tail = NULL;
    } else {
        list->tail->next = head->next;
    }

    free(head);
    list->size--;
    return 0;
}

/* Print circular list */
void csll_print(CircularSLL *list) {
    if (list->tail == NULL) {
        printf("(empty)\n");
        return;
    }

    printf("Circular: ");
    CSLLNode *head = list->tail->next;
    CSLLNode *current = head;
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);
    printf("(back to start)\n");
}

/* Free circular list */
void csll_free(CircularSLL *list) {
    if (list == NULL) return;

    if (list->tail != NULL) {
        CSLLNode *head = list->tail->next;
        CSLLNode *current = head;
        do {
            CSLLNode *next = current->next;
            free(current);
            current = next;
        } while (current != head);
    }
    free(list);
}

Doubly Circular Linked List

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

typedef struct {
    CDLLNode *head;
    size_t size;
} CircularDLL;

/* Create with sentinel node for easier operations */
CircularDLL *cdll_create(void) {
    CircularDLL *list = malloc(sizeof(CircularDLL));
    if (list == NULL) return NULL;

    list->head = NULL;
    list->size = 0;
    return list;
}

/* Insert at beginning */
int cdll_prepend(CircularDLL *list, int data) {
    CDLLNode *node = malloc(sizeof(CDLLNode));
    if (node == NULL) return -1;
    node->data = data;

    if (list->head == NULL) {
        node->next = node;
        node->prev = node;
        list->head = node;
    } else {
        node->next = list->head;
        node->prev = list->head->prev;
        list->head->prev->next = node;
        list->head->prev = node;
        list->head = node;
    }

    list->size++;
    return 0;
}

---

Basic Operations

Time Complexity Summary

* With tail pointer ** Amortized (dynamic array) *** If node reference is known

Insert at Position

/* Insert at specific position in singly linked list */
int sll_insert_at(SinglyLinkedList *list, size_t position, int data) {
    if (position > list->size) return -1;

    if (position == 0) {
        return sll_prepend(list, data);
    }

    if (position == list->size) {
        return sll_append(list, data);
    }

    /* Find node at position - 1 */
    SLLNode *prev = sll_get(list, position - 1);
    return sll_insert_after(list, prev, data);
}

Delete at Position

/* Delete at specific position */
int sll_delete_at(SinglyLinkedList *list, size_t position) {
    if (position >= list->size) return -1;

    if (position == 0) {
        return sll_delete_first(list);
    }

    SLLNode *prev = sll_get(list, position - 1);
    SLLNode *to_delete = prev->next;

    prev->next = to_delete->next;

    if (to_delete == list->tail) {
        list->tail = prev;
    }

    free(to_delete);
    list->size--;
    return 0;
}

---

Advanced Operations

Reverse a Linked List

/* Iterative reverse - O(n) time, O(1) space */
void sll_reverse(SinglyLinkedList *list) {
    if (list->head == NULL || list->head->next == NULL) {
        return;
    }

    SLLNode *prev = NULL;
    SLLNode *current = list->head;
    list->tail = list->head;

    while (current != NULL) {
        SLLNode *next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    list->head = prev;
}

/* Recursive reverse */
SLLNode *reverse_recursive(SLLNode *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    SLLNode *rest = reverse_recursive(head->next);
    head->next->next = head;
    head->next = NULL;

    return rest;
}

Find Middle Element

/* Floyd's algorithm - O(n) time, O(1) space */
SLLNode *sll_find_middle(SinglyLinkedList *list) {
    if (list->head == NULL) return NULL;

    SLLNode *slow = list->head;
    SLLNode *fast = list->head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

Detect Cycle

/* Floyd's Cycle Detection - O(n) time, O(1) space */
int sll_has_cycle(SLLNode *head) {
    if (head == NULL) return 0;

    SLLNode *slow = head;
    SLLNode *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 */
}

/* Find start of cycle */
SLLNode *sll_find_cycle_start(SLLNode *head) {
    if (head == NULL) return NULL;

    SLLNode *slow = head;
    SLLNode *fast = head;

    /* Detect cycle */
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            /* Cycle detected, find start */
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }

    return NULL;  /* No cycle */
}

Merge Two Sorted Lists

/* Merge two sorted lists - O(n+m) */
SLLNode *merge_sorted(SLLNode *l1, SLLNode *l2) {
    SLLNode dummy;
    SLLNode *tail = &dummy;
    dummy.next = NULL;

    while (l1 != NULL && l2 != NULL) {
        if (l1->data <= l2->data) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    /* Append remaining nodes */
    tail->next = (l1 != NULL) ? l1 : l2;

    return dummy.next;
}

Find Nth Node from End

/* Two-pointer technique - O(n) */
SLLNode *sll_nth_from_end(SinglyLinkedList *list, size_t n) {
    if (list->head == NULL || n == 0) return NULL;

    SLLNode *fast = list->head;
    SLLNode *slow = list->head;

    /* Move fast n nodes ahead */
    for (size_t i = 0; i < n; i++) {
        if (fast == NULL) return NULL;  /* n > list size */
        fast = fast->next;
    }

    /* Move both until fast reaches end */
    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

Remove Duplicates

/* Remove duplicates from sorted list - O(n) */
void sll_remove_duplicates_sorted(SinglyLinkedList *list) {
    SLLNode *current = list->head;

    while (current != NULL && current->next != NULL) {
        if (current->data == current->next->data) {
            SLLNode *duplicate = current->next;
            current->next = current->next->next;
            if (duplicate == list->tail) {
                list->tail = current;
            }
            free(duplicate);
            list->size--;
        } else {
            current = current->next;
        }
    }
}

/* Remove duplicates from unsorted list - O(n^2) or O(n) with hash */
void sll_remove_duplicates_unsorted(SinglyLinkedList *list) {
    SLLNode *current = list->head;

    while (current != NULL) {
        SLLNode *runner = current;
        while (runner->next != NULL) {
            if (runner->next->data == current->data) {
                SLLNode *duplicate = runner->next;
                runner->next = runner->next->next;
                if (duplicate == list->tail) {
                    list->tail = runner;
                }
                free(duplicate);
                list->size--;
            } else {
                runner = runner->next;
            }
        }
        current = current->next;
    }
}

Palindrome Check

/* Check if list is palindrome */
int sll_is_palindrome(SinglyLinkedList *list) {
    if (list->head == NULL || list->head->next == NULL) {
        return 1;  /* Empty or single node is palindrome */
    }

    /* Find middle */
    SLLNode *slow = list->head;
    SLLNode *fast = list->head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    /* Reverse second half */
    SLLNode *prev = NULL;
    SLLNode *current = slow;
    while (current != NULL) {
        SLLNode *next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    /* Compare halves */
    SLLNode *p1 = list->head;
    SLLNode *p2 = prev;
    int is_palindrome = 1;

    while (p2 != NULL) {
        if (p1->data != p2->data) {
            is_palindrome = 0;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    /* Restore list (reverse second half back) */
    current = prev;
    prev = NULL;
    while (current != NULL) {
        SLLNode *next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    return is_palindrome;
}

---

Memory Management

Proper Cleanup

/* Always free all nodes before freeing list */
void sll_free(SinglyLinkedList *list) {
    if (list == NULL) return;

    SLLNode *current = list->head;
    while (current != NULL) {
        SLLNode *next = current->next;
        free(current);
        current = next;
    }

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    free(list);
}

Deep Copy

/* Create deep copy of list */
SinglyLinkedList *sll_copy(SinglyLinkedList *source) {
    if (source == NULL) return NULL;

    SinglyLinkedList *copy = sll_create();
    if (copy == NULL) return NULL;

    SLLNode *current = source->head;
    while (current != NULL) {
        if (sll_append(copy, current->data) != 0) {
            sll_free(copy);
            return NULL;
        }
        current = current->next;
    }

    return copy;
}

Generic Linked List

/* Generic linked list for any data type */
typedef struct GenericNode {
    void *data;
    size_t data_size;
    struct GenericNode *next;
} GenericNode;

typedef struct {
    GenericNode *head;
    GenericNode *tail;
    size_t size;
    void (*free_func)(void *);  /* Custom free function */
} GenericList;

/* Create node with data copy */
GenericNode *generic_create_node(void *data, size_t data_size) {
    GenericNode *node = malloc(sizeof(GenericNode));
    if (node == NULL) return NULL;

    node->data = malloc(data_size);
    if (node->data == NULL) {
        free(node);
        return NULL;
    }

    memcpy(node->data, data, data_size);
    node->data_size = data_size;
    node->next = NULL;

    return node;
}

/* Free generic list */
void generic_free(GenericList *list) {
    if (list == NULL) return;

    GenericNode *current = list->head;
    while (current != NULL) {
        GenericNode *next = current->next;
        if (list->free_func) {
            list->free_func(current->data);
        } else {
            free(current->data);
        }
        free(current);
        current = next;
    }
    free(list);
}

---

Common Algorithms

Merge Sort for Linked Lists

/* Split list into two halves */
void split_list(SLLNode *source, SLLNode **front, SLLNode **back) {
    SLLNode *fast = source->next;
    SLLNode *slow = source;

    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    *front = source;
    *back = slow->next;
    slow->next = NULL;
}

/* Merge sort for linked list */
SLLNode *merge_sort(SLLNode *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    SLLNode *a;
    SLLNode *b;

    split_list(head, &a, &b);

    a = merge_sort(a);
    b = merge_sort(b);

    return merge_sorted(a, b);
}

Intersection of Two Lists

/* Find intersection point of two lists */
SLLNode *find_intersection(SLLNode *head1, SLLNode *head2) {
    if (head1 == NULL || head2 == NULL) return NULL;

    /* Get lengths */
    int len1 = 0, len2 = 0;
    SLLNode *p1 = head1;
    SLLNode *p2 = head2;

    while (p1 != NULL) {
        len1++;
        p1 = p1->next;
    }
    while (p2 != NULL) {
        len2++;
        p2 = p2->next;
    }

    /* Align starting points */
    p1 = head1;
    p2 = head2;

    int diff = len1 - len2;
    if (diff > 0) {
        while (diff--) p1 = p1->next;
    } else {
        while (diff++) p2 = p2->next;
    }

    /* Find intersection */
    while (p1 != NULL && p2 != NULL) {
        if (p1 == p2) return p1;
        p1 = p1->next;
        p2 = p2->next;
    }

    return NULL;
}

Add Two Numbers (Represented as Lists)

/* Add two numbers where each node is a digit (reverse order) */
SLLNode *add_numbers(SLLNode *l1, SLLNode *l2) {
    SLLNode dummy;
    SLLNode *current = &dummy;
    dummy.next = NULL;
    int carry = 0;

    while (l1 != NULL || l2 != NULL || carry) {
        int sum = carry;

        if (l1 != NULL) {
            sum += l1->data;
            l1 = l1->next;
        }
        if (l2 != NULL) {
            sum += l2->data;
            l2 = l2->next;
        }

        carry = sum / 10;

        SLLNode *node = malloc(sizeof(SLLNode));
        node->data = sum % 10;
        node->next = NULL;

        current->next = node;
        current = node;
    }

    return dummy.next;
}

---

Applications

Stack Implementation

typedef struct {
    SinglyLinkedList *list;
} Stack;

Stack *stack_create(void) {
    Stack *stack = malloc(sizeof(Stack));
    if (stack == NULL) return NULL;

    stack->list = sll_create();
    if (stack->list == NULL) {
        free(stack);
        return NULL;
    }
    return stack;
}

int stack_push(Stack *stack, int data) {
    return sll_prepend(stack->list, data);
}

int stack_pop(Stack *stack, int *data) {
    if (stack->list->head == NULL) return -1;

    *data = stack->list->head->data;
    return sll_delete_first(stack->list);
}

int stack_peek(Stack *stack, int *data) {
    if (stack->list->head == NULL) return -1;

    *data = stack->list->head->data;
    return 0;
}

int stack_is_empty(Stack *stack) {
    return stack->list->head == NULL;
}

Queue Implementation

typedef struct {
    SinglyLinkedList *list;
} Queue;

Queue *queue_create(void) {
    Queue *queue = malloc(sizeof(Queue));
    if (queue == NULL) return NULL;

    queue->list = sll_create();
    if (queue->list == NULL) {
        free(queue);
        return NULL;
    }
    return queue;
}

int queue_enqueue(Queue *queue, int data) {
    return sll_append(queue->list, data);
}

int queue_dequeue(Queue *queue, int *data) {
    if (queue->list->head == NULL) return -1;

    *data = queue->list->head->data;
    return sll_delete_first(queue->list);
}

int queue_is_empty(Queue *queue) {
    return queue->list->head == NULL;
}

LRU Cache

/* Least Recently Used Cache using Doubly Linked List + Hash */
typedef struct LRUNode {
    int key;
    int value;
    struct LRUNode *prev;
    struct LRUNode *next;
} LRUNode;

typedef struct {
    int capacity;
    int size;
    LRUNode *head;  /* Most recent */
    LRUNode *tail;  /* Least recent */
    LRUNode **hash; /* Hash table for O(1) lookup */
    int hash_size;
} LRUCache;

/* Move node to front (most recently used) */
void lru_move_to_front(LRUCache *cache, LRUNode *node) {
    if (node == cache->head) return;

    /* Remove from current position */
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    if (node == cache->tail) cache->tail = node->prev;

    /* Insert at front */
    node->next = cache->head;
    node->prev = NULL;
    if (cache->head) cache->head->prev = node;
    cache->head = node;
    if (cache->tail == NULL) cache->tail = node;
}

---

Best Practices

1. Always Initialize Pointers

SLLNode *node = malloc(sizeof(SLLNode));
if (node != NULL) {
    node->data = 0;
    node->next = NULL;  /* Always initialize */
}

2. Check for Empty List

void safe_operation(SinglyLinkedList *list) {
    if (list == NULL || list->head == NULL) {
        return;  /* Handle empty list */
    }
    /* ... */
}

3. Use Sentinel Nodes

/* Sentinel simplifies edge cases */
typedef struct {
    SLLNode sentinel;  /* Dummy head node */
    size_t size;
} SentinelList;

void sentinel_init(SentinelList *list) {
    list->sentinel.data = 0;
    list->sentinel.next = NULL;
    list->size = 0;
}

/* No special case for empty list */
void sentinel_insert_after(SLLNode *prev, int data) {
    SLLNode *node = malloc(sizeof(SLLNode));
    node->data = data;
    node->next = prev->next;
    prev->next = node;
}

4. Return Status Codes

typedef enum {
    LL_SUCCESS = 0,
    LL_ERROR_NULL = -1,
    LL_ERROR_MEMORY = -2,
    LL_ERROR_NOT_FOUND = -3,
    LL_ERROR_EMPTY = -4
} LLStatus;

LLStatus safe_prepend(SinglyLinkedList *list, int data) {
    if (list == NULL) return LL_ERROR_NULL;

    SLLNode *node = malloc(sizeof(SLLNode));
    if (node == NULL) return LL_ERROR_MEMORY;

    node->data = data;
    node->next = list->head;
    list->head = node;
    list->size++;

    return LL_SUCCESS;
}

5. Use Wrapper Functions

/* Hide implementation details */
typedef struct LinkedList LinkedList;  /* Opaque type */

LinkedList *ll_create(void);
void ll_destroy(LinkedList *list);
int ll_add(LinkedList *list, int data);
int ll_remove(LinkedList *list, int data);
int ll_get(LinkedList *list, size_t index, int *data);
size_t ll_size(LinkedList *list);

---

Common Pitfalls

1. Forgetting to Update Tail

/* WRONG */
void bad_delete_last(SinglyLinkedList *list) {
    SLLNode *prev = list->head;
    while (prev->next->next != NULL) {
        prev = prev->next;
    }
    free(prev->next);
    prev->next = NULL;
    /* Forgot to update list->tail! */
}

/* CORRECT */
void good_delete_last(SinglyLinkedList *list) {
    SLLNode *prev = list->head;
    while (prev->next->next != NULL) {
        prev = prev->next;
    }
    free(prev->next);
    prev->next = NULL;
    list->tail = prev;  /* Update tail */
    list->size--;
}

2. Memory Leaks

/* WRONG - memory leak */
void bad_delete(SinglyLinkedList *list, int value) {
    SLLNode *prev = list->head;
    while (prev->next != NULL && prev->next->data != value) {
        prev = prev->next;
    }
    prev->next = prev->next->next;  /* Lost reference! */
}

/* CORRECT */
void good_delete(SinglyLinkedList *list, int value) {
    SLLNode *prev = list->head;
    while (prev->next != NULL && prev->next->data != value) {
        prev = prev->next;
    }
    SLLNode *to_delete = prev->next;
    prev->next = prev->next->next;
    free(to_delete);  /* Free the memory */
}

3. Dangling Pointers

/* WRONG */
SLLNode *get_first(SinglyLinkedList *list) {
    SLLNode *first = list->head;
    sll_delete_first(list);  /* Frees first! */
    return first;  /* Dangling pointer! */
}

/* CORRECT */
int get_first_value(SinglyLinkedList *list, int *value) {
    if (list->head == NULL) return -1;
    *value = list->head->data;
    sll_delete_first(list);
    return 0;
}

4. Not Handling Edge Cases

/* WRONG - crashes on empty list */
void bad_print(SinglyLinkedList *list) {
    SLLNode *current = list->head;
    while (current->next != NULL) {  /* Dereference NULL! */
        printf("%d ", current->data);
        current = current->next;
    }
}

/* CORRECT */
void good_print(SinglyLinkedList *list) {
    if (list == NULL || list->head == NULL) {
        printf("(empty)\n");
        return;
    }
    SLLNode *current = list->head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

5. Infinite Loops with Circular Lists

/* WRONG - infinite loop */
void bad_print_circular(CircularSLL *list) {
    CSLLNode *current = list->tail->next;
    while (current != NULL) {  /* Never becomes NULL! */
        printf("%d ", current->data);
        current = current->next;
    }
}

/* CORRECT */
void good_print_circular(CircularSLL *list) {
    if (list->tail == NULL) return;

    CSLLNode *head = list->tail->next;
    CSLLNode *current = head;
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head);  /* Stop at head */
}

---

Summary

Linked lists are fundamental data structures that form the basis for many other structures and algorithms. Understanding their implementation and trade-offs is essential for every C programmer.