Linked lists are fundamental data structures in computer science, serving as building blocks for more complex data structures like stacks, queues, and graphs. In C, linked lists demonstrate the power of pointers and dynamic memory allocation, making them essential knowledge for any serious C programmer.

What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are not stored contiguously in memory. Each node contains two components:

1. Data: The actual value being stored
2. Pointer: A reference to the next node in the sequence

This structure offers dynamic memory allocation, efficient insertions and deletions, and the ability to grow and shrink during runtime.

Types of Linked Lists

1. Singly Linked List: Each node points to the next node only
2. Doubly Linked List: Each node points to both the next and previous nodes
3. Circular Linked List: The last node points back to the first node

Node Structure Definition

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Singly linked list node
typedef struct Node {
int data;
struct Node* next;
} Node;
// Doubly linked list node
typedef struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
} DNode;
// List structure with metadata
typedef struct LinkedList {
Node* head;
Node* tail;
int size;
} LinkedList;

Core Linked List Operations

1. Creating a New Node

/**
* Creates a new node with given data
* @param data Value to store in the node
* @return Pointer to the newly created node, or NULL if allocation fails
*/
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
fprintf(stderr, "Memory allocation failed!\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
/**
* Creates a new doubly linked list node
*/
DNode* createDNode(int data) {
DNode* newNode = (DNode*)malloc(sizeof(DNode));
if (newNode == NULL) {
fprintf(stderr, "Memory allocation failed!\n");
return NULL;
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}

2. Initializing a Linked List

/**
* Initializes an empty linked list
*/
void initLinkedList(LinkedList* list) {
list->head = NULL;
list->tail = NULL;
list->size = 0;
}
/**
* Creates and initializes a new linked list
*/
LinkedList* createLinkedList() {
LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
if (list != NULL) {
initLinkedList(list);
}
return list;
}

3. Insertion Operations

/**
* Inserts a node at the beginning of the list
* Time Complexity: O(1)
*/
void insertAtBeginning(LinkedList* list, int data) {
Node* newNode = createNode(data);
if (newNode == NULL) return;
newNode->next = list->head;
list->head = newNode;
// If list was empty, update tail
if (list->tail == NULL) {
list->tail = newNode;
}
list->size++;
printf("Inserted %d at beginning. List size: %d\n", data, list->size);
}
/**
* Inserts a node at the end of the list
* Time Complexity: O(1) with tail pointer, O(n) without
*/
void insertAtEnd(LinkedList* list, int data) {
Node* newNode = createNode(data);
if (newNode == NULL) return;
// If list is empty
if (list->head == NULL) {
list->head = newNode;
list->tail = newNode;
} else {
list->tail->next = newNode;
list->tail = newNode;
}
list->size++;
printf("Inserted %d at end. List size: %d\n", data, list->size);
}
/**
* Inserts a node at a specific position (0-based index)
* Time Complexity: O(n)
* @return true if successful, false otherwise
*/
bool insertAtPosition(LinkedList* list, int data, int position) {
if (position < 0 || position > list->size) {
printf("Invalid position! Valid positions: 0 to %d\n", list->size);
return false;
}
if (position == 0) {
insertAtBeginning(list, data);
return true;
}
if (position == list->size) {
insertAtEnd(list, data);
return true;
}
Node* newNode = createNode(data);
if (newNode == NULL) return false;
// Traverse to position-1
Node* current = list->head;
for (int i = 0; i < position - 1; i++) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
list->size++;
printf("Inserted %d at position %d\n", data, position);
return true;
}
/**
* Inserts in sorted order (ascending)
* Assumes list is already sorted
*/
void insertSorted(LinkedList* list, int data) {
// If list is empty or data should be first
if (list->head == NULL || data < list->head->data) {
insertAtBeginning(list, data);
return;
}
Node* current = list->head;
Node* prev = NULL;
// Find the correct position
while (current != NULL && current->data < data) {
prev = current;
current = current->next;
}
// If we reached the end
if (current == NULL) {
insertAtEnd(list, data);
return;
}
// Insert between prev and current
Node* newNode = createNode(data);
if (newNode == NULL) return;
newNode->next = current;
prev->next = newNode;
list->size++;
printf("Inserted %d in sorted order\n", data);
}

4. Deletion Operations

/**
* Deletes the first node
* Time Complexity: O(1)
* @return The deleted node's data, or -1 if list is empty
*/
int deleteFromBeginning(LinkedList* list) {
if (list->head == NULL) {
printf("List is empty! Cannot delete.\n");
return -1;
}
Node* temp = list->head;
int data = temp->data;
list->head = list->head->next;
// If list becomes empty, update tail
if (list->head == NULL) {
list->tail = NULL;
}
free(temp);
list->size--;
printf("Deleted %d from beginning. List size: %d\n", data, list->size);
return data;
}
/**
* Deletes the last node
* Time Complexity: O(n) for singly linked list without tail pointer
* @return The deleted node's data, or -1 if list is empty
*/
int deleteFromEnd(LinkedList* list) {
if (list->head == NULL) {
printf("List is empty! Cannot delete.\n");
return -1;
}
// If only one node
if (list->head->next == NULL) {
return deleteFromBeginning(list);
}
// Traverse to second-last node
Node* current = list->head;
while (current->next->next != NULL) {
current = current->next;
}
Node* temp = current->next;
int data = temp->data;
current->next = NULL;
list->tail = current;
free(temp);
list->size--;
printf("Deleted %d from end. List size: %d\n", data, list->size);
return data;
}
/**
* Deletes a node at a specific position
* Time Complexity: O(n)
* @return The deleted node's data, or -1 on failure
*/
int deleteAtPosition(LinkedList* list, int position) {
if (position < 0 || position >= list->size) {
printf("Invalid position! Valid positions: 0 to %d\n", list->size - 1);
return -1;
}
if (position == 0) {
return deleteFromBeginning(list);
}
if (position == list->size - 1) {
return deleteFromEnd(list);
}
// Traverse to node before the one to delete
Node* current = list->head;
for (int i = 0; i < position - 1; i++) {
current = current->next;
}
Node* temp = current->next;
int data = temp->data;
current->next = temp->next;
free(temp);
list->size--;
printf("Deleted %d from position %d\n", data, position);
return data;
}
/**
* Deletes the first occurrence of a specific value
* @return true if value was found and deleted
*/
bool deleteByValue(LinkedList* list, int value) {
if (list->head == NULL) {
printf("List is empty!\n");
return false;
}
// If value is at head
if (list->head->data == value) {
deleteFromBeginning(list);
return true;
}
Node* current = list->head;
Node* prev = NULL;
while (current != NULL && current->data != value) {
prev = current;
current = current->next;
}
if (current == NULL) {
printf("Value %d not found in list\n", value);
return false;
}
prev->next = current->next;
// Update tail if deleting last node
if (current == list->tail) {
list->tail = prev;
}
free(current);
list->size--;
printf("Deleted value %d from list\n", value);
return true;
}

5. Search Operations

/**
* Searches for a value in the list
* Time Complexity: O(n)
* @return Position of first occurrence, or -1 if not found
*/
int search(LinkedList* list, int value) {
Node* current = list->head;
int position = 0;
while (current != NULL) {
if (current->data == value) {
printf("Value %d found at position %d\n", value, position);
return position;
}
current = current->next;
position++;
}
printf("Value %d not found in list\n", value);
return -1;
}
/**
* Returns the value at a given position
* @return Value at position, or -1 if position invalid
*/
int getAtPosition(LinkedList* list, int position) {
if (position < 0 || position >= list->size) {
printf("Invalid position!\n");
return -1;
}
Node* current = list->head;
for (int i = 0; i < position; i++) {
current = current->next;
}
return current->data;
}

6. Traversal and Display

/**
* Displays all elements in the list
*/
void displayList(LinkedList* list) {
if (list->head == NULL) {
printf("List is empty!\n");
return;
}
printf("Linked List (size = %d): ", list->size);
Node* current = list->head;
while (current != NULL) {
printf("%d", current->data);
if (current->next != NULL) {
printf(" -> ");
}
current = current->next;
}
printf(" -> NULL\n");
}
/**
* Displays list with indices
*/
void displayWithIndices(LinkedList* list) {
if (list->head == NULL) {
printf("List is empty!\n");
return;
}
printf("\nIndex\tValue\n");
printf("-----\t-----\n");
Node* current = list->head;
int index = 0;
while (current != NULL) {
printf("%d\t%d\n", index, current->data);
current = current->next;
index++;
}
printf("\n");
}
/**
* Recursive traversal (demonstrates recursion on linked lists)
*/
void displayRecursive(Node* node) {
if (node == NULL) {
printf("NULL\n");
return;
}
printf("%d -> ", node->data);
displayRecursive(node->next);
}
/**
* Displays list in reverse (using recursion)
*/
void displayReverseRecursive(Node* node) {
if (node == NULL) {
return;
}
displayReverseRecursive(node->next);
printf("%d ", node->data);
}

7. Utility Operations

/**
* Returns the length of the list
*/
int getLength(LinkedList* list) {
return list->size;
}
/**
* Checks if the list is empty
*/
bool isEmpty(LinkedList* list) {
return list->head == NULL;
}
/**
* Returns the first element without removing it
*/
int peekFirst(LinkedList* list) {
if (list->head == NULL) {
printf("List is empty!\n");
return -1;
}
return list->head->data;
}
/**
* Returns the last element without removing it
*/
int peekLast(LinkedList* list) {
if (list->tail == NULL) {
printf("List is empty!\n");
return -1;
}
return list->tail->data;
}

8. Advanced Operations

/**
* Reverses the linked list iteratively
* Time Complexity: O(n), Space Complexity: O(1)
*/
void reverseList(LinkedList* list) {
if (list->head == NULL || list->head->next == NULL) {
return; // Empty or single node list
}
Node* prev = NULL;
Node* current = list->head;
Node* next = NULL;
// Update tail to be the old head
list->tail = list->head;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
list->head = prev;
printf("List reversed successfully\n");
}
/**
* Reverses the list recursively
*/
Node* reverseRecursive(Node* head) {
if (head == NULL || head->next == NULL) {
return head;
}
Node* newHead = reverseRecursive(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
/**
* Finds the middle element using fast-slow pointer technique
* Time Complexity: O(n), Space Complexity: O(1)
*/
int findMiddle(LinkedList* list) {
if (list->head == NULL) {
printf("List is empty!\n");
return -1;
}
Node* slow = list->head;
Node* fast = list->head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow->data;
}
/**
* Detects cycle in linked list (Floyd's Cycle Detection)
* @return true if cycle exists
*/
bool hasCycle(Node* head) {
if (head == NULL || head->next == 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;
}
/**
* Removes duplicates from sorted linked list
*/
void removeDuplicatesSorted(LinkedList* list) {
if (list->head == NULL) {
return;
}
Node* current = list->head;
while (current != NULL && current->next != NULL) {
if (current->data == current->next->data) {
Node* duplicate = current->next;
current->next = duplicate->next;
// Update tail if deleting last node
if (duplicate == list->tail) {
list->tail = current;
}
free(duplicate);
list->size--;
} else {
current = current->next;
}
}
}
/**
* Merges two sorted linked lists
* @return Head of merged list
*/
Node* mergeSortedLists(Node* head1, Node* head2) {
// Create a dummy node to simplify logic
Node dummy;
Node* tail = &dummy;
dummy.next = NULL;
while (head1 != NULL && head2 != NULL) {
if (head1->data <= head2->data) {
tail->next = head1;
head1 = head1->next;
} else {
tail->next = head2;
head2 = head2->next;
}
tail = tail->next;
}
// Attach remaining nodes
if (head1 != NULL) {
tail->next = head1;
}
if (head2 != NULL) {
tail->next = head2;
}
return dummy.next;
}

9. Memory Management

/**
* Frees all nodes in the list
*/
void freeList(LinkedList* list) {
Node* current = list->head;
Node* next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
list->head = NULL;
list->tail = NULL;
list->size = 0;
printf("List freed successfully\n");
}
/**
* Destroys the list and frees the list structure
*/
void destroyList(LinkedList** list) {
if (list == NULL || *list == NULL) {
return;
}
freeList(*list);
free(*list);
*list = NULL;
}

Doubly Linked List Operations

/**
* Doubly Linked List structure
*/
typedef struct DoublyLinkedList {
DNode* head;
DNode* tail;
int size;
} DoublyLinkedList;
/**
* Initialize doubly linked list
*/
void initDoublyList(DoublyLinkedList* list) {
list->head = NULL;
list->tail = NULL;
list->size = 0;
}
/**
* Insert at beginning of doubly linked list
*/
void dllInsertAtBeginning(DoublyLinkedList* list, int data) {
DNode* newNode = createDNode(data);
if (newNode == NULL) return;
if (list->head == NULL) {
list->head = newNode;
list->tail = newNode;
} else {
newNode->next = list->head;
list->head->prev = newNode;
list->head = newNode;
}
list->size++;
}
/**
* Insert at end of doubly linked list
*/
void dllInsertAtEnd(DoublyLinkedList* list, int data) {
DNode* newNode = createDNode(data);
if (newNode == NULL) return;
if (list->tail == NULL) {
list->head = newNode;
list->tail = newNode;
} else {
newNode->prev = list->tail;
list->tail->next = newNode;
list->tail = newNode;
}
list->size++;
}
/**
* Delete from beginning of doubly linked list
*/
int dllDeleteFromBeginning(DoublyLinkedList* list) {
if (list->head == NULL) {
return -1;
}
DNode* temp = list->head;
int data = temp->data;
list->head = list->head->next;
if (list->head != NULL) {
list->head->prev = NULL;
} else {
list->tail = NULL; // List became empty
}
free(temp);
list->size--;
return data;
}
/**
* Display doubly linked list forward
*/
void dllDisplayForward(DoublyLinkedList* list) {
if (list->head == NULL) {
printf("List is empty!\n");
return;
}
printf("Forward: ");
DNode* current = list->head;
while (current != NULL) {
printf("%d", current->data);
if (current->next != NULL) {
printf(" <-> ");
}
current = current->next;
}
printf(" -> NULL\n");
}
/**
* Display doubly linked list backward
*/
void dllDisplayBackward(DoublyLinkedList* list) {
if (list->tail == NULL) {
printf("List is empty!\n");
return;
}
printf("Backward: ");
DNode* current = list->tail;
while (current != NULL) {
printf("%d", current->data);
if (current->prev != NULL) {
printf(" <-> ");
}
current = current->prev;
}
printf(" -> NULL\n");
}

Complete Example Program

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Include all the above function definitions here
int main() {
printf("=== Linked List Operations Demo ===\n\n");
// Create and initialize a linked list
LinkedList* list = createLinkedList();
// Demonstrate insertions
printf("1. Insertion Operations:\n");
printf("------------------------\n");
insertAtEnd(list, 10);
insertAtEnd(list, 20);
insertAtEnd(list, 30);
displayList(list);
insertAtBeginning(list, 5);
insertAtBeginning(list, 2);
displayList(list);
insertAtPosition(list, 15, 3);
insertAtPosition(list, 25, 5);
displayList(list);
// Demonstrate search
printf("\n2. Search Operations:\n");
printf("--------------------\n");
search(list, 15);
search(list, 100);
// Demonstrate deletions
printf("\n3. Deletion Operations:\n");
printf("----------------------\n");
deleteFromBeginning(list);
displayList(list);
deleteFromEnd(list);
displayList(list);
deleteAtPosition(list, 2);
displayList(list);
deleteByValue(list, 20);
displayList(list);
// Demonstrate advanced operations
printf("\n4. Advanced Operations:\n");
printf("----------------------\n");
printf("Middle element: %d\n", findMiddle(list));
reverseList(list);
printf("After reversal: ");
displayList(list);
// Test sorted insertion
LinkedList* sortedList = createLinkedList();
insertSorted(sortedList, 30);
insertSorted(sortedList, 10);
insertSorted(sortedList, 20);
insertSorted(sortedList, 40);
insertSorted(sortedList, 5);
printf("\n5. Sorted List:\n");
printf("---------------\n");
displayList(sortedList);
// Test duplicate removal
insertAtEnd(sortedList, 30);
insertAtEnd(sortedList, 30);
insertAtEnd(sortedList, 40);
printf("\nList with duplicates: ");
displayList(sortedList);
removeDuplicatesSorted(sortedList);
printf("After removing duplicates: ");
displayList(sortedList);
// Demonstrate doubly linked list
printf("\n6. Doubly Linked List:\n");
printf("---------------------\n");
DoublyLinkedList dll;
initDoublyList(&dll);
dllInsertAtEnd(&dll, 100);
dllInsertAtEnd(&dll, 200);
dllInsertAtEnd(&dll, 300);
dllInsertAtBeginning(&dll, 50);
dllDisplayForward(&dll);
dllDisplayBackward(&dll);
// Clean up
printf("\n7. Cleanup:\n");
printf("-----------\n");
destroyList(&list);
destroyList(&sortedList);
// Free doubly linked list nodes
while (dll.head != NULL) {
dllDeleteFromBeginning(&dll);
}
printf("All memory freed successfully\n");
return 0;
}

Time Complexity Summary

Best Practices and Common Pitfalls

1. Always check malloc return: Memory allocation can fail; always verify pointers before use
2. Handle edge cases: Empty list, single node, first/last node operations
3. Update all pointers: When modifying lists, ensure all relevant pointers are updated
4. Free memory: Prevent memory leaks by freeing nodes when deleting
5. Use tail pointer: For frequent end insertions, maintain a tail pointer
6. Consider sentinel nodes: Dummy nodes can simplify edge cases
7. Validate input: Check positions and indices before operations

Conclusion

Linked lists are fundamental data structures that every C programmer must master. They demonstrate the power of dynamic memory allocation and pointer manipulation while providing efficient insertions and deletions. Understanding linked lists thoroughly prepares you for more complex data structures and algorithms, and the skills gained—particularly in memory management and pointer operations—are essential for systems programming and embedded development.

The implementations provided here cover all essential operations with proper error handling and memory management, serving as a solid foundation for building more sophisticated data structures and applications in C.