Linked lists are fundamental data structures that provide dynamic memory allocation and efficient insertion/deletion operations. Unlike arrays, linked lists don't require contiguous memory and can grow or shrink during program execution. Understanding linked lists is essential for mastering C programming and forms the foundation for more complex data structures like trees, graphs, and hash tables.

What Is a Linked List?

A linked list is a linear data structure where each element (node) contains:

• Data: The actual value stored
• Pointer: Address of the next node in the sequence

Singly Linked List:
┌─────────┐    ┌─────────┐    ┌─────────┐
│ data: 10 │───▶│ data: 20 │───▶│ data: 30 │───▶ NULL
│ next:   ─┼─── │ next:   ─┼─── │ next:   ─┼───
└─────────┘    └─────────┘    └─────────┘
Head                          Tail

Types of Linked Lists

1. Singly Linked List: Each node points to the next node
2. Doubly Linked List: Nodes point to both next and previous nodes
3. Circular Linked List: Last node points back to first node

1. Singly Linked List Implementation

Basic Node Structure:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Node structure
typedef struct Node {
int data;
struct Node *next;
} Node;

Core Operations:

// Create a new node
Node* createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed!\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Insert at beginning
void insertAtBeginning(Node **head, int data) {
Node *newNode = createNode(data);
if (newNode) {
newNode->next = *head;
*head = newNode;
}
}
// Insert at end
void insertAtEnd(Node **head, int data) {
Node *newNode = createNode(data);
if (!newNode) return;
if (*head == NULL) {
*head = newNode;
return;
}
Node *current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
// Insert at position (0-based index)
void insertAtPosition(Node **head, int data, int position) {
if (position < 0) return;
if (position == 0) {
insertAtBeginning(head, data);
return;
}
Node *current = *head;
for (int i = 0; i < position - 1; i++) {
if (current == NULL) return;  // Position out of bounds
current = current->next;
}
if (current == NULL) return;
Node *newNode = createNode(data);
if (newNode) {
newNode->next = current->next;
current->next = newNode;
}
}
// Delete from beginning
int deleteFromBeginning(Node **head) {
if (*head == NULL) {
printf("List is empty!\n");
return -1;
}
Node *temp = *head;
int data = temp->data;
*head = (*head)->next;
free(temp);
return data;
}
// Delete from end
int deleteFromEnd(Node **head) {
if (*head == NULL) {
printf("List is empty!\n");
return -1;
}
if ((*head)->next == NULL) {
int data = (*head)->data;
free(*head);
*head = NULL;
return data;
}
Node *current = *head;
while (current->next->next != NULL) {
current = current->next;
}
int data = current->next->data;
free(current->next);
current->next = NULL;
return data;
}
// Delete by value
int deleteByValue(Node **head, int value) {
if (*head == NULL) return -1;
// If head node contains the value
if ((*head)->data == value) {
Node *temp = *head;
*head = (*head)->next;
int data = temp->data;
free(temp);
return data;
}
// Search for the node
Node *current = *head;
while (current->next != NULL && current->next->data != value) {
current = current->next;
}
if (current->next == NULL) {
printf("Value %d not found in list.\n", value);
return -1;
}
Node *temp = current->next;
current->next = temp->next;
int data = temp->data;
free(temp);
return data;
}
// Search for a value
Node* search(Node *head, int value) {
Node *current = head;
while (current != NULL) {
if (current->data == value) {
return current;
}
current = current->next;
}
return NULL;
}
// Get length of list
int getLength(Node *head) {
int count = 0;
Node *current = head;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
// Get node at index
Node* getNodeAt(Node *head, int index) {
Node *current = head;
int count = 0;
while (current != NULL && count < index) {
current = current->next;
count++;
}
return current;
}
// Reverse the list
void reverseList(Node **head) {
Node *prev = NULL;
Node *current = *head;
Node *next = NULL;
while (current != NULL) {
next = current->next;  // Store next node
current->next = prev;   // Reverse link
prev = current;         // Move prev forward
current = next;         // Move current forward
}
*head = prev;  // Update head
}
// Display the list
void displayList(Node *head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
printf("List: ");
Node *current = head;
while (current != NULL) {
printf("%d", current->data);
if (current->next != NULL) {
printf(" -> ");
}
current = current->next;
}
printf(" -> NULL\n");
printf("Length: %d\n", getLength(head));
}
// Free entire list
void freeList(Node **head) {
Node *current = *head;
while (current != NULL) {
Node *temp = current;
current = current->next;
free(temp);
}
*head = NULL;
}
// Main function to demonstrate singly linked list
int main() {
Node *head = NULL;
printf("=== Singly Linked List Demonstration ===\n\n");
// Insert at beginning
printf("Inserting at beginning: 30, 20, 10\n");
insertAtBeginning(&head, 30);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 10);
displayList(head);
// Insert at end
printf("\nInserting at end: 40, 50\n");
insertAtEnd(&head, 40);
insertAtEnd(&head, 50);
displayList(head);
// Insert at position
printf("\nInserting 25 at position 2:\n");
insertAtPosition(&head, 25, 2);
displayList(head);
// Delete operations
printf("\nDeleting from beginning: %d\n", deleteFromBeginning(&head));
displayList(head);
printf("\nDeleting from end: %d\n", deleteFromEnd(&head));
displayList(head);
printf("\nDeleting value 25: %d\n", deleteByValue(&head, 25));
displayList(head);
// Search
int searchValue = 40;
Node *found = search(head, searchValue);
printf("\nSearching for %d: %s\n", searchValue, 
found ? "Found" : "Not found");
// Reverse
printf("\nReversing list:\n");
reverseList(&head);
displayList(head);
// Free memory
freeList(&head);
printf("\nList freed. Head is: %s\n", head ? "not NULL" : "NULL");
return 0;
}

2. Doubly Linked List

Doubly linked lists have pointers to both next and previous nodes, enabling bidirectional traversal.

typedef struct DNode {
int data;
struct DNode *prev;
struct DNode *next;
} DNode;
// Create a new doubly linked list node
DNode* createDNode(int data) {
DNode *newNode = (DNode*)malloc(sizeof(DNode));
if (!newNode) return NULL;
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Insert at beginning (doubly linked list)
void insertAtBeginningD(DNode **head, int data) {
DNode *newNode = createDNode(data);
if (!newNode) return;
if (*head != NULL) {
(*head)->prev = newNode;
}
newNode->next = *head;
*head = newNode;
}
// Insert at end (doubly linked list)
void insertAtEndD(DNode **head, int data) {
DNode *newNode = createDNode(data);
if (!newNode) return;
if (*head == NULL) {
*head = newNode;
return;
}
DNode *current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
// Delete from end (doubly linked list)
int deleteFromEndD(DNode **head) {
if (*head == NULL) return -1;
if ((*head)->next == NULL) {
int data = (*head)->data;
free(*head);
*head = NULL;
return data;
}
DNode *current = *head;
while (current->next != NULL) {
current = current->next;
}
int data = current->data;
current->prev->next = NULL;
free(current);
return data;
}
// Display forward
void displayForward(DNode *head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
printf("Forward:  NULL");
DNode *current = head;
while (current != NULL) {
printf(" <- %d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// Display backward
void displayBackward(DNode *head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
// Go to last node
DNode *current = head;
while (current->next != NULL) {
current = current->next;
}
printf("Backward: NULL");
while (current != NULL) {
printf(" <- %d -> ", current->data);
current = current->prev;
}
printf("NULL\n");
}
// Free doubly linked list
void freeListD(DNode **head) {
DNode *current = *head;
while (current != NULL) {
DNode *temp = current;
current = current->next;
free(temp);
}
*head = NULL;
}
// Demonstrate doubly linked list
void demoDoublyLinkedList() {
printf("\n=== Doubly Linked List Demonstration ===\n\n");
DNode *head = NULL;
// Insert at beginning
printf("Inserting at beginning: 30, 20, 10\n");
insertAtBeginningD(&head, 30);
insertAtBeginningD(&head, 20);
insertAtBeginningD(&head, 10);
displayForward(head);
displayBackward(head);
// Insert at end
printf("\nInserting at end: 40, 50\n");
insertAtEndD(&head, 40);
insertAtEndD(&head, 50);
displayForward(head);
// Delete from end
printf("\nDeleting from end: %d\n", deleteFromEndD(&head));
displayForward(head);
freeListD(&head);
}

3. Circular Linked List

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

typedef struct CNode {
int data;
struct CNode *next;
} CNode;
// Create a new circular linked list node
CNode* createCNode(int data) {
CNode *newNode = (CNode*)malloc(sizeof(CNode));
if (!newNode) return NULL;
newNode->data = data;
newNode->next = newNode;  // Points to itself initially
return newNode;
}
// Insert at beginning (circular)
void insertAtBeginningC(CNode **head, int data) {
CNode *newNode = createCNode(data);
if (!newNode) return;
if (*head == NULL) {
*head = newNode;
return;
}
// Find last node
CNode *last = *head;
while (last->next != *head) {
last = last->next;
}
newNode->next = *head;
last->next = newNode;
*head = newNode;
}
// Insert at end (circular)
void insertAtEndC(CNode **head, int data) {
CNode *newNode = createCNode(data);
if (!newNode) return;
if (*head == NULL) {
*head = newNode;
return;
}
// Find last node
CNode *last = *head;
while (last->next != *head) {
last = last->next;
}
last->next = newNode;
newNode->next = *head;
}
// Display circular list
void displayCircular(CNode *head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
printf("Circular: ");
CNode *current = head;
do {
printf("%d", current->data);
current = current->next;
if (current != head) {
printf(" -> ");
}
} while (current != head);
printf(" -> (back to %d)\n", head->data);
}
// Get length of circular list
int getCircularLength(CNode *head) {
if (head == NULL) return 0;
int count = 0;
CNode *current = head;
do {
count++;
current = current->next;
} while (current != head);
return count;
}
// Free circular list
void freeCircularList(CNode **head) {
if (*head == NULL) return;
// Break the circle first
CNode *last = *head;
while (last->next != *head) {
last = last->next;
}
last->next = NULL;
// Free as normal list
CNode *current = *head;
while (current != NULL) {
CNode *temp = current;
current = current->next;
free(temp);
}
*head = NULL;
}
// Demonstrate circular linked list
void demoCircularLinkedList() {
printf("\n=== Circular Linked List Demonstration ===\n\n");
CNode *head = NULL;
// Insert at beginning
printf("Inserting at beginning: 30, 20, 10\n");
insertAtBeginningC(&head, 30);
insertAtBeginningC(&head, 20);
insertAtBeginningC(&head, 10);
displayCircular(head);
printf("Length: %d\n", getCircularLength(head));
// Insert at end
printf("\nInserting at end: 40, 50\n");
insertAtEndC(&head, 40);
insertAtEndC(&head, 50);
displayCircular(head);
printf("Length: %d\n", getCircularLength(head));
freeCircularList(&head);
}

4. Advanced Linked List Operations

Merge Two Sorted Lists:

Node* mergeSortedLists(Node *list1, Node *list2) {
if (list1 == NULL) return list2;
if (list2 == NULL) return list1;
Node *result = NULL;
if (list1->data <= list2->data) {
result = list1;
result->next = mergeSortedLists(list1->next, list2);
} else {
result = list2;
result->next = mergeSortedLists(list1, list2->next);
}
return result;
}

Detect Cycle (Floyd's Algorithm):

bool hasCycle(Node *head) {
if (head == NULL) return false;
Node *slow = head;
Node *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;  // Cycle detected
}
}
return false;
}

Find Middle Node:

Node* findMiddle(Node *head) {
if (head == NULL) return NULL;
Node *slow = head;
Node *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}

Remove Duplicates (Sorted List):

void removeDuplicatesSorted(Node *head) {
if (head == NULL) return;
Node *current = head;
while (current->next != NULL) {
if (current->data == current->next->data) {
Node *temp = current->next;
current->next = temp->next;
free(temp);
} else {
current = current->next;
}
}
}

Remove Duplicates (Unsorted List):

void removeDuplicatesUnsorted(Node *head) {
if (head == NULL) return;
Node *current = head;
while (current != NULL) {
Node *runner = current;
while (runner->next != NULL) {
if (runner->next->data == current->data) {
Node *temp = runner->next;
runner->next = temp->next;
free(temp);
} else {
runner = runner->next;
}
}
current = current->next;
}
}

Rotate List:

Node* rotateRight(Node *head, int k) {
if (head == NULL || head->next == NULL || k == 0) {
return head;
}
// Find length and last node
int len = 1;
Node *last = head;
while (last->next != NULL) {
last = last->next;
len++;
}
// Make it circular
last->next = head;
// Find new head and break
k = k % len;
int steps = len - k;
Node *newLast = head;
for (int i = 1; i < steps; i++) {
newLast = newLast->next;
}
Node *newHead = newLast->next;
newLast->next = NULL;
return newHead;
}

Split List into Two Halves:

void splitList(Node *head, Node **firstHalf, Node **secondHalf) {
if (head == NULL || head->next == NULL) {
*firstHalf = head;
*secondHalf = NULL;
return;
}
Node *slow = head;
Node *fast = head->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*firstHalf = head;
*secondHalf = slow->next;
slow->next = NULL;
}

5. Generic Linked List (Using void*)

typedef struct GenericNode {
void *data;
size_t dataSize;
struct GenericNode *next;
} GenericNode;
typedef struct {
GenericNode *head;
int size;
} GenericList;
GenericList* createGenericList() {
GenericList *list = (GenericList*)malloc(sizeof(GenericList));
list->head = NULL;
list->size = 0;
return list;
}
void insertGeneric(GenericList *list, void *data, size_t dataSize) {
GenericNode *newNode = (GenericNode*)malloc(sizeof(GenericNode));
newNode->data = malloc(dataSize);
newNode->dataSize = dataSize;
memcpy(newNode->data, data, dataSize);
newNode->next = list->head;
list->head = newNode;
list->size++;
}
void* getGeneric(GenericList *list, int index) {
if (index < 0 || index >= list->size) return NULL;
GenericNode *current = list->head;
for (int i = 0; i < index; i++) {
current = current->next;
}
return current->data;
}
void freeGenericList(GenericList *list) {
GenericNode *current = list->head;
while (current != NULL) {
GenericNode *temp = current;
current = current->next;
free(temp->data);
free(temp);
}
free(list);
}
// Example usage
void demoGenericList() {
GenericList *list = createGenericList();
// Store integers
int intVal = 42;
insertGeneric(list, &intVal, sizeof(int));
// Store doubles
double dblVal = 3.14159;
insertGeneric(list, &dblVal, sizeof(double));
// Store strings
char *strVal = "Hello";
insertGeneric(list, strVal, strlen(strVal) + 1);
// Retrieve and print
printf("Generic list contents:\n");
int *retrievedInt = (int*)getGeneric(list, 2);
printf("  Integer: %d\n", *retrievedInt);
double *retrievedDbl = (double*)getGeneric(list, 1);
printf("  Double: %f\n", *retrievedDbl);
char *retrievedStr = (char*)getGeneric(list, 0);
printf("  String: %s\n", retrievedStr);
freeGenericList(list);
}

6. Practical Applications

Polynomial Representation:

typedef struct Term {
int coefficient;
int exponent;
struct Term *next;
} Term;
Term* createTerm(int coeff, int exp) {
Term *t = (Term*)malloc(sizeof(Term));
t->coefficient = coeff;
t->exponent = exp;
t->next = NULL;
return t;
}
void addTerm(Term **poly, int coeff, int exp) {
if (coeff == 0) return;
Term *newTerm = createTerm(coeff, exp);
if (*poly == NULL || (*poly)->exponent < exp) {
newTerm->next = *poly;
*poly = newTerm;
return;
}
Term *current = *poly;
while (current->next != NULL && current->next->exponent > exp) {
current = current->next;
}
if (current->exponent == exp) {
current->coefficient += coeff;
free(newTerm);
if (current->coefficient == 0) {
// Remove term if coefficient becomes zero
// (implementation omitted for brevity)
}
} else {
newTerm->next = current->next;
current->next = newTerm;
}
}
void displayPolynomial(Term *poly) {
if (poly == NULL) {
printf("0\n");
return;
}
Term *current = poly;
while (current != NULL) {
if (current != poly && current->coefficient > 0) {
printf("+");
}
if (current->exponent == 0) {
printf("%d", current->coefficient);
} else if (current->exponent == 1) {
printf("%dx", current->coefficient);
} else {
printf("%dx^%d", current->coefficient, current->exponent);
}
current = current->next;
}
printf("\n");
}
Term* addPolynomials(Term *p1, Term *p2) {
Term *result = NULL;
while (p1 != NULL || p2 != NULL) {
if (p1 == NULL) {
addTerm(&result, p2->coefficient, p2->exponent);
p2 = p2->next;
} else if (p2 == NULL) {
addTerm(&result, p1->coefficient, p1->exponent);
p1 = p1->next;
} else if (p1->exponent > p2->exponent) {
addTerm(&result, p1->coefficient, p1->exponent);
p1 = p1->next;
} else if (p2->exponent > p1->exponent) {
addTerm(&result, p2->coefficient, p2->exponent);
p2 = p2->next;
} else {
addTerm(&result, p1->coefficient + p2->coefficient, p1->exponent);
p1 = p1->next;
p2 = p2->next;
}
}
return result;
}
void demoPolynomial() {
Term *poly1 = NULL;
Term *poly2 = NULL;
addTerm(&poly1, 5, 3);   // 5x^3
addTerm(&poly1, 4, 2);   // +4x^2
addTerm(&poly1, 3, 0);   // +3
addTerm(&poly2, 2, 4);   // 2x^4
addTerm(&poly2, 1, 2);   // +1x^2
addTerm(&poly2, 7, 1);   // +7x
printf("Polynomial 1: ");
displayPolynomial(poly1);
printf("Polynomial 2: ");
displayPolynomial(poly2);
Term *sum = addPolynomials(poly1, poly2);
printf("Sum:          ");
displayPolynomial(sum);
}

7. Performance Comparison

*If array has space; O(n) if resize needed

8. Common Pitfalls and Solutions

// Pitfall 1: Not checking malloc return
Node *node = malloc(sizeof(Node));  // Might return NULL
node->data = 10;  // Crash if malloc failed!
// Solution:
Node *node = malloc(sizeof(Node));
if (node == NULL) {
printf("Memory allocation failed!\n");
return;
}
// Pitfall 2: Losing reference to list
Node *head = NULL;
insertAtBeginning(&head, 10);
head = NULL;  // Lost the list - memory leak!
// Solution: Always use freeList() before reassigning
// Pitfall 3: Dangling pointers after free
Node *node = head;
free(node);
node->data = 20;  // Using freed memory!
// Solution: Set pointer to NULL after free
free(node);
node = NULL;
// Pitfall 4: Not updating head in functions
void badInsert(Node *head, int data) {  // Pass by value!
Node *newNode = createNode(data);
newNode->next = head;
head = newNode;  // Only modifies local copy!
}
// Solution: Pass pointer to head
void goodInsert(Node **head, int data) {
Node *newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}

9. Linked List Algorithms Summary

10. Best Practices

1. Always check malloc return - Handle allocation failures
2. Maintain head pointer - Never lose reference to list start
3. Use temporary pointers - When modifying links
4. Free memory properly - No memory leaks
5. Validate parameters - Check for NULL inputs
6. Document ownership - Who frees the memory
7. Consider edge cases - Empty list, single element
8. Use const when appropriate - For read-only parameters
9. Implement debug functions - Print list for testing
10. Write unit tests - Verify all operations

Conclusion

Linked lists are fundamental data structures that every C programmer must master. They demonstrate key concepts:

• Dynamic memory allocation - Creating nodes at runtime
• Pointer manipulation - The essence of C programming
• Algorithm implementation - Various operations and their complexity
• Memory management - Proper allocation and deallocation
• Data structure design - Trade-offs between different implementations

Key takeaways:

• Singly linked lists are simple but limited to forward traversal
• Doubly linked lists enable bidirectional traversal
• Circular lists are useful for round-robin applications
• Generic lists can store any data type
• Always handle edge cases and memory properly

Mastering linked lists provides the foundation for understanding more complex data structures and is essential for system programming, embedded systems, and algorithm design.