Module 6 : Linked List
By the end of this module, students will be able to:
- Understand the concept and structure of linked lists
- Differentiate between arrays and linked lists
- Implement singly linked lists in C
- Perform basic operations: insertion, deletion, traversal, and searching
- Understand doubly linked lists and circular linked lists
- Apply linked lists to solve real-world problems
- Debug common linked list errors
- Analyze time and space complexity of linked list operations

1. Introduction to Linked Lists
1.1 What is a Linked List? 
 A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (called a node ) contains: 
 
 Data: The actual value stored 
 Pointer(s): Reference to the next (and possibly previous) node 
 
 Analogy: 
Think of a linked list like a treasure hunt: 
 
 Each clue (node) contains information (data) 
 Each clue also tells you where to find the next clue (pointer) 
 You start at the first clue (head) 
 The last clue says "End of hunt" (NULL pointer) 
 
 Visual Representation: 
 Array (Contiguous Memory):
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │
└────┴────┴────┴────┴────┘
 [0] [1] [2] [3] [4]

Linked List (Non-contiguous Memory):
HEAD
 ↓
┌────┬────┐ ┌────┬────┐ ┌────┬────┐ ┌────┬────┐
│ 10 │ ●──┼───→│ 20 │ ●──┼───→│ 30 │ ●──┼───→│ 40 │NULL│
└────┴────┘ └────┴────┘ └────┴────┘ └────┴────┘
 data next data next data next data next
 
 1.2 Why Use Linked Lists? 
 Advantages: 
 
 Dynamic Size: Can grow or shrink at runtime 
 Easy Insertion/Deletion: No need to shift elements 
 Memory Efficient: Allocate memory only when needed 
 Flexible Structure: Can implement stacks, queues, graphs 
 
 Disadvantages: 
 
 No Random Access: Must traverse from beginning 
 Extra Memory: Requires space for pointers 
 Sequential Access: Slower than arrays for direct access 
 Cache Performance: Poor cache locality 
 
 1.3 Types of Linked Lists 
 1. Singly Linked List
 HEAD → [data|next] → [data|next] → [data|NULL]

2. Doubly Linked List
 HEAD ⇄ [prev|data|next] ⇄ [prev|data|next] ⇄ [prev|data|NULL]

3. Circular Linked List
 HEAD → [data|next] → [data|next] → [data|next] ──┐
 ↑ │
 └─────────────────────────────────────────────────┘

4. Circular Doubly Linked List
 HEAD ⇄ [prev|data|next] ⇄ [prev|data|next] ──┐
 ↑ │
 └────────────────────────────────────────────┘
 
 1.4 Linked List vs Array 
 
 
 
 Feature 
 Array 
 Linked List 
 
 
 
 
 Memory Allocation 
 Contiguous 
 Non-contiguous 
 
 
 Size 
 Fixed 
 Dynamic 
 
 
 Access Time 
 O(1) 
 O(n) 
 
 
 Insertion (beginning) 
 O(n) 
 O(1) 
 
 
 Insertion (end) 
 O(1) 
 O(n) or O(1) with tail 
 
 
 Deletion (beginning) 
 O(n) 
 O(1) 
 
 
 Memory Usage 
 Less (no pointers) 
 More (pointers) 
 
 
 Cache Performance 
 Better 
 Worse 
 
 
 Random Access 
 Yes 
 No

2. Node Structure
2.1 Defining a Node 
 In C, a node is typically defined using a structure : 
 // Definition of a node
struct Node {
 int data; // Data part
 struct Node *next; // Pointer to next node
};
 
 Memory Layout: 
 Single Node in Memory:
┌──────────┬──────────┐
│ data │ next │
│ (int) │ (pointer)│
└──────────┴──────────┘
 4 bytes 8 bytes (on 64-bit system)
 
 2.2 Creating a Node 
 Method 1: Static Allocation (Limited) 
 struct Node node1;
node1.data = 10;
node1.next = NULL;
 
 Method 2: Dynamic Allocation (Recommended) 
 #include <stdio.h>
#include <stdlib.h>

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

int main() {
 // Allocate memory for new node
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 
 // Check if allocation successful
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return 1;
 }
 
 // Initialize node
 newNode->data = 10;
 newNode->next = NULL;
 
 printf("Node created with data: %d\n", newNode->data);
 
 // Free memory when done
 free(newNode);
 
 return 0;
}
 
 2.3 The Arrow Operator (->) 
 When working with pointers to structures, use the arrow operator: 
 struct Node *ptr;

// These are equivalent:
ptr->data = 10; // Arrow operator (preferred)
(*ptr).data = 10; // Dereference then dot operator
 
 Why use ->? 
 
 More readable 
 Less typing 
 Standard convention in C

3. Singly Linked List Operations
3.1 Creating an Empty List 
 #include <stdio.h>
#include <stdlib.h>

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

// Initialize head pointer
struct Node *head = NULL;
 
 3.2 Insertion Operations 
 3.2.1 Insert at Beginning 
 void insertAtBeginning(struct Node **head, int value) {
 // Create new node
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 
 // Set data and next pointer
 newNode->data = value;
 newNode->next = *head;
 
 // Update head
 *head = newNode;
}

// Usage
int main() {
 struct Node *head = NULL;
 
 insertAtBeginning(&head, 30);
 insertAtBeginning(&head, 20);
 insertAtBeginning(&head, 10);
 
 // List now: 10 → 20 → 30 → NULL
 
 return 0;
}
 
 Visual Steps: 
 Initial: head → NULL

Step 1: Create node with data = 10
newNode → [10|NULL]

Step 2: Point newNode->next to current head
newNode → [10|●] → NULL

Step 3: Update head to newNode
head → [10|NULL]

Step 4: Insert 20
head → [20|●] → [10|NULL]

Step 5: Insert 30
head → [30|●] → [20|●] → [10|NULL]
 
 Time Complexity: O(1)
 Space Complexity: O(1) 
 3.2.2 Insert at End 
 void insertAtEnd(struct Node **head, int value) {
 // Create new node
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 
 newNode->data = value;
 newNode->next = NULL;
 
 // If list is empty
 if (*head == NULL) {
 *head = newNode;
 return;
 }
 
 // Traverse to last node
 struct Node *temp = *head;
 while (temp->next != NULL) {
 temp = temp->next;
 }
 
 // Insert at end
 temp->next = newNode;
}
 
 Visual Steps: 
 List: head → [10|●] → [20|●] → [30|NULL]

Step 1: Create newNode with data = 40
newNode → [40|NULL]

Step 2: Traverse to last node
temp moves: [10] → [20] → [30]

Step 3: Connect last node to newNode
head → [10|●] → [20|●] → [30|●] → [40|NULL]
 
 Time Complexity: O(n) - must traverse entire list
 Space Complexity: O(1) 
 3.2.3 Insert at Position 
 void insertAtPosition(struct Node **head, int value, int position) {
 // Create new node
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 
 newNode->data = value;
 
 // Insert at beginning (position 0)
 if (position == 0) {
 newNode->next = *head;
 *head = newNode;
 return;
 }
 
 // Traverse to position-1
 struct Node *temp = *head;
 for (int i = 0; i < position - 1 && temp != NULL; i++) {
 temp = temp->next;
 }
 
 // Check if position is valid
 if (temp == NULL) {
 printf("Invalid position!\n");
 free(newNode);
 return;
 }
 
 // Insert node
 newNode->next = temp->next;
 temp->next = newNode;
}
 
 Visual Steps (Insert 25 at position 2): 
 Initial: head → [10|●] → [20|●] → [30|NULL]
 0 1 2

Step 1: Create newNode [25|NULL]

Step 2: Traverse to position 1 (position - 1)
temp → [20|●]

Step 3: Connect newNode
newNode->next = temp->next (points to 30)
[25|●] → [30|NULL]

Step 4: Connect temp to newNode
temp->next = newNode
head → [10|●] → [20|●] → [25|●] → [30|NULL]
 
 Time Complexity: O(n)
 Space Complexity: O(1) 
 3.3 Deletion Operations 
 3.3.1 Delete from Beginning 
 void deleteFromBeginning(struct Node **head) {
 // Check if list is empty
 if (*head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 // Store current head
 struct Node *temp = *head;
 
 // Move head to next node
 *head = (*head)->next;
 
 // Free old head
 free(temp);
}
 
 Visual Steps: 
 Initial: head → [10|●] → [20|●] → [30|NULL]

Step 1: temp = head
temp → [10|●] → [20|●] → [30|NULL]
head → [10|●] → [20|●] → [30|NULL]

Step 2: head = head->next
head → [20|●] → [30|NULL]
temp → [10|●] (to be freed)

Step 3: free(temp)
head → [20|●] → [30|NULL]
 
 Time Complexity: O(1)
 Space Complexity: O(1) 
 3.3.2 Delete from End 
 void deleteFromEnd(struct Node **head) {
 // Check if list is empty
 if (*head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 // If only one node
 if ((*head)->next == NULL) {
 free(*head);
 *head = NULL;
 return;
 }
 
 // Traverse to second-last node
 struct Node *temp = *head;
 while (temp->next->next != NULL) {
 temp = temp->next;
 }
 
 // Delete last node
 free(temp->next);
 temp->next = NULL;
}
 
 Visual Steps: 
 Initial: head → [10|●] → [20|●] → [30|NULL]

Step 1: Traverse to second-last node
temp → [20|●] → [30|NULL]

Step 2: Free last node
free(temp->next)

Step 3: Set second-last to NULL
head → [10|●] → [20|NULL]
 
 Time Complexity: O(n)
 Space Complexity: O(1) 
 3.3.3 Delete at Position 
 void deleteAtPosition(struct Node **head, int position) {
 // Check if list is empty
 if (*head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 // Delete first node
 if (position == 0) {
 struct Node *temp = *head;
 *head = (*head)->next;
 free(temp);
 return;
 }
 
 // Traverse to position-1
 struct Node *temp = *head;
 for (int i = 0; i < position - 1 && temp != NULL; i++) {
 temp = temp->next;
 }
 
 // Check if position is valid
 if (temp == NULL || temp->next == NULL) {
 printf("Invalid position!\n");
 return;
 }
 
 // Delete node
 struct Node *nodeToDelete = temp->next;
 temp->next = nodeToDelete->next;
 free(nodeToDelete);
}
 
 Time Complexity: O(n)
 Space Complexity: O(1) 
 3.3.4 Delete by Value 
 void deleteByValue(struct Node **head, int value) {
 // Check if list is empty
 if (*head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 // If head node contains the value
 if ((*head)->data == value) {
 struct Node *temp = *head;
 *head = (*head)->next;
 free(temp);
 return;
 }
 
 // Search for the node
 struct Node *temp = *head;
 while (temp->next != NULL && temp->next->data != value) {
 temp = temp->next;
 }
 
 // If value not found
 if (temp->next == NULL) {
 printf("Value %d not found!\n", value);
 return;
 }
 
 // Delete node
 struct Node *nodeToDelete = temp->next;
 temp->next = nodeToDelete->next;
 free(nodeToDelete);
}
 
 Time Complexity: O(n)
 Space Complexity: O(1) 
 3.4 Traversal and Display 
 void displayList(struct Node *head) {
 if (head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 struct Node *temp = head;
 printf("List: ");
 
 while (temp != NULL) {
 printf("%d", temp->data);
 if (temp->next != NULL) {
 printf(" → ");
 }
 temp = temp->next;
 }
 printf(" → NULL\n");
}

// Alternative: Using for loop
void displayList2(struct Node *head) {
 printf("List: ");
 for (struct Node *temp = head; temp != NULL; temp = temp->next) {
 printf("%d → ", temp->data);
 }
 printf("NULL\n");
}
 
 Time Complexity: O(n)
 Space Complexity: O(1) 
 3.5 Searching 
 int search(struct Node *head, int value) {
 struct Node *temp = head;
 int position = 0;
 
 while (temp != NULL) {
 if (temp->data == value) {
 return position; // Found at position
 }
 temp = temp->next;
 position++;
 }
 
 return -1; // Not found
}

// Usage
int main() {
 struct Node *head = NULL;
 
 insertAtEnd(&head, 10);
 insertAtEnd(&head, 20);
 insertAtEnd(&head, 30);
 
 int pos = search(head, 20);
 if (pos != -1) {
 printf("Found at position: %d\n", pos);
 } else {
 printf("Not found!\n");
 }
 
 return 0;
}
 
 Time Complexity: O(n)
 Space Complexity: O(1) 
 3.6 Length of List 
 int getLength(struct Node *head) {
 int count = 0;
 struct Node *temp = head;
 
 while (temp != NULL) {
 count++;
 temp = temp->next;
 }
 
 return count;
}

// Recursive version
int getLengthRecursive(struct Node *head) {
 if (head == NULL) {
 return 0;
 }
 return 1 + getLengthRecursive(head->next);
}
 
 Time Complexity: O(n)
 Space Complexity: O(1) for iterative, O(n) for recursive

4. Complete Singly Linked List Example
#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
 int data;
 struct Node *next;
};

// Function prototypes
void insertAtBeginning(struct Node **head, int value);
void insertAtEnd(struct Node **head, int value);
void insertAtPosition(struct Node **head, int value, int position);
void deleteFromBeginning(struct Node **head);
void deleteFromEnd(struct Node **head);
void deleteAtPosition(struct Node **head, int position);
void deleteByValue(struct Node **head, int value);
void displayList(struct Node *head);
int search(struct Node *head, int value);
int getLength(struct Node *head);
void freeList(struct Node **head);

int main() {
 struct Node *head = NULL;
 
 printf("=== Linked List Operations Demo ===\n\n");
 
 // Insert operations
 printf("Inserting elements...\n");
 insertAtBeginning(&head, 10);
 insertAtBeginning(&head, 5);
 insertAtEnd(&head, 20);
 insertAtEnd(&head, 25);
 insertAtPosition(&head, 15, 2);
 
 printf("After insertions: ");
 displayList(head);
 printf("Length: %d\n\n", getLength(head));
 
 // Search operation
 int searchValue = 15;
 int pos = search(head, searchValue);
 if (pos != -1) {
 printf("Value %d found at position %d\n\n", searchValue, pos);
 } else {
 printf("Value %d not found\n\n", searchValue);
 }
 
 // Delete operations
 printf("Deleting from beginning...\n");
 deleteFromBeginning(&head);
 displayList(head);
 
 printf("Deleting from end...\n");
 deleteFromEnd(&head);
 displayList(head);
 
 printf("Deleting at position 1...\n");
 deleteAtPosition(&head, 1);
 displayList(head);
 
 printf("Deleting value 10...\n");
 deleteByValue(&head, 10);
 displayList(head);
 
 printf("\nFinal length: %d\n", getLength(head));
 
 // Clean up
 freeList(&head);
 printf("Memory freed.\n");
 
 return 0;
}

// Function implementations
void insertAtBeginning(struct Node **head, int value) {
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 newNode->data = value;
 newNode->next = *head;
 *head = newNode;
}

void insertAtEnd(struct Node **head, int value) {
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 newNode->data = value;
 newNode->next = NULL;
 
 if (*head == NULL) {
 *head = newNode;
 return;
 }
 
 struct Node *temp = *head;
 while (temp->next != NULL) {
 temp = temp->next;
 }
 temp->next = newNode;
}

void insertAtPosition(struct Node **head, int value, int position) {
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 newNode->data = value;
 
 if (position == 0) {
 newNode->next = *head;
 *head = newNode;
 return;
 }
 
 struct Node *temp = *head;
 for (int i = 0; i < position - 1 && temp != NULL; i++) {
 temp = temp->next;
 }
 
 if (temp == NULL) {
 printf("Invalid position!\n");
 free(newNode);
 return;
 }
 
 newNode->next = temp->next;
 temp->next = newNode;
}

void deleteFromBeginning(struct Node **head) {
 if (*head == NULL) {
 printf("List is empty!\n");
 return;
 }
 struct Node *temp = *head;
 *head = (*head)->next;
 free(temp);
}

void deleteFromEnd(struct Node **head) {
 if (*head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 if ((*head)->next == NULL) {
 free(*head);
 *head = NULL;
 return;
 }
 
 struct Node *temp = *head;
 while (temp->next->next != NULL) {
 temp = temp->next;
 }
 free(temp->next);
 temp->next = NULL;
}

void deleteAtPosition(struct Node **head, int position) {
 if (*head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 if (position == 0) {
 struct Node *temp = *head;
 *head = (*head)->next;
 free(temp);
 return;
 }
 
 struct Node *temp = *head;
 for (int i = 0; i < position - 1 && temp != NULL; i++) {
 temp = temp->next;
 }
 
 if (temp == NULL || temp->next == NULL) {
 printf("Invalid position!\n");
 return;
 }
 
 struct Node *nodeToDelete = temp->next;
 temp->next = nodeToDelete->next;
 free(nodeToDelete);
}

void deleteByValue(struct Node **head, int value) {
 if (*head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 if ((*head)->data == value) {
 struct Node *temp = *head;
 *head = (*head)->next;
 free(temp);
 return;
 }
 
 struct Node *temp = *head;
 while (temp->next != NULL && temp->next->data != value) {
 temp = temp->next;
 }
 
 if (temp->next == NULL) {
 printf("Value %d not found!\n", value);
 return;
 }
 
 struct Node *nodeToDelete = temp->next;
 temp->next = nodeToDelete->next;
 free(nodeToDelete);
}

void displayList(struct Node *head) {
 if (head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 struct Node *temp = head;
 while (temp != NULL) {
 printf("%d", temp->data);
 if (temp->next != NULL) {
 printf(" → ");
 }
 temp = temp->next;
 }
 printf(" → NULL\n");
}

int search(struct Node *head, int value) {
 struct Node *temp = head;
 int position = 0;
 
 while (temp != NULL) {
 if (temp->data == value) {
 return position;
 }
 temp = temp->next;
 position++;
 }
 return -1;
}

int getLength(struct Node *head) {
 int count = 0;
 struct Node *temp = head;
 
 while (temp != NULL) {
 count++;
 temp = temp->next;
 }
 return count;
}

void freeList(struct Node **head) {
 struct Node *temp;
 while (*head != NULL) {
 temp = *head;
 *head = (*head)->next;
 free(temp);
 }
}

5. Doubly Linked List
5.1 Node Structure 
 struct DNode {
 int data;
 struct DNode *prev; // Pointer to previous node
 struct DNode *next; // Pointer to next node
};
 
 Visual Representation: 
 NULL ← [prev|10|next] ⇄ [prev|20|next] ⇄ [prev|30|next] → NULL
 ↑
 HEAD
 
 5.2 Advantages of Doubly Linked List 
 
 Bidirectional Traversal: Can move forward and backward 
 Easy Deletion: Don't need previous node reference 
 Easier Insertion: Can insert before a node easily 
 
 Disadvantages: 
 
 More Memory: Extra pointer per node 
 Complex Operations: Must update two pointers 
 
 5.3 Basic Operations 
 5.3.1 Insert at Beginning 
 void insertAtBeginning(struct DNode **head, int value) {
 // Create new node
 struct DNode *newNode = (struct DNode*)malloc(sizeof(struct DNode));
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 
 newNode->data = value;
 newNode->prev = NULL;
 newNode->next = *head;
 
 // Update head's prev if list not empty
 if (*head != NULL) {
 (*head)->prev = newNode;
 }
 
 *head = newNode;
}
 
 Visual Steps: 
 Initial: head → [NULL|10|●] ⇄ [●|20|NULL]

Step 1: Create newNode [NULL|5|NULL]

Step 2: Connect newNode to head
newNode: [NULL|5|●] → [NULL|10|●]

Step 3: Update head's prev
[NULL|5|●] ⇄ [●|10|●]

Step 4: Update head
head → [NULL|5|●] ⇄ [●|10|●] ⇄ [●|20|NULL]
 
 5.3.2 Insert at End 
 void insertAtEnd(struct DNode **head, int value) {
 struct DNode *newNode = (struct DNode*)malloc(sizeof(struct DNode));
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 
 newNode->data = value;
 newNode->next = NULL;
 
 // If list is empty
 if (*head == NULL) {
 newNode->prev = NULL;
 *head = newNode;
 return;
 }
 
 // Traverse to last node
 struct DNode *temp = *head;
 while (temp->next != NULL) {
 temp = temp->next;
 }
 
 // Insert at end
 temp->next = newNode;
 newNode->prev = temp;
}
 
 5.3.3 Delete Node 
 void deleteNode(struct DNode **head, struct DNode *nodeToDelete) {
 // Check if list or node is NULL
 if (*head == NULL || nodeToDelete == NULL) {
 return;
 }
 
 // If node is head
 if (*head == nodeToDelete) {
 *head = nodeToDelete->next;
 }
 
 // Update next's prev pointer
 if (nodeToDelete->next != NULL) {
 nodeToDelete->next->prev = nodeToDelete->prev;
 }
 
 // Update prev's next pointer
 if (nodeToDelete->prev != NULL) {
 nodeToDelete->prev->next = nodeToDelete->next;
 }
 
 free(nodeToDelete);
}
 
 5.3.4 Reverse Traversal 
 void displayReverse(struct DNode *head) {
 if (head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 // Go to last node
 struct DNode *temp = head;
 while (temp->next != NULL) {
 temp = temp->next;
 }
 
 // Traverse backward
 printf("List (reverse): ");
 while (temp != NULL) {
 printf("%d", temp->data);
 if (temp->prev != NULL) {
 printf(" ← ");
 }
 temp = temp->prev;
 }
 printf("\n");
}

6. Circular Linked List
6.1 Structure 
 In a circular linked list, the last node points back to the first node (or head). 
 struct Node {
 int data;
 struct Node *next;
};
 
 Visual Representation: 
 ┌───────────────────────────┐
 ↓ │
HEAD → [10|●] → [20|●] → [30|●] ──┘
 
 6.2 Operations 
 6.2.1 Insert at Beginning 
 void insertAtBeginning(struct Node **head, int value) {
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 
 newNode->data = value;
 
 // If list is empty
 if (*head == NULL) {
 newNode->next = newNode; // Points to itself
 *head = newNode;
 return;
 }
 
 // Find last node
 struct Node *temp = *head;
 while (temp->next != *head) {
 temp = temp->next;
 }
 
 // Insert at beginning
 newNode->next = *head;
 temp->next = newNode;
 *head = newNode;
}
 
 6.2.2 Display Circular List 
 void displayCircular(struct Node *head) {
 if (head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 struct Node *temp = head;
 printf("List: ");
 
 do {
 printf("%d", temp->data);
 temp = temp->next;
 if (temp != head) {
 printf(" → ");
 }
 } while (temp != head);
 
 printf(" → (back to %d)\n", head->data);
}
 
 6.2.3 Delete Node 
 void deleteNode(struct Node **head, int value) {
 if (*head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 struct Node *temp = *head;
 struct Node *prev = NULL;
 
 // If head node contains the value
 if (temp->data == value) {
 // If only one node
 if (temp->next == *head) {
 free(temp);
 *head = NULL;
 return;
 }
 
 // Find last node
 while (temp->next != *head) {
 temp = temp->next;
 }
 
 // Delete head
 temp->next = (*head)->next;
 free(*head);
 *head = temp->next;
 return;
 }
 
 // Search for the node
 prev = *head;
 temp = (*head)->next;
 
 while (temp != *head && temp->data != value) {
 prev = temp;
 temp = temp->next;
 }
 
 // If value not found
 if (temp == *head) {
 printf("Value %d not found!\n", value);
 return;
 }
 
 // Delete node
 prev->next = temp->next;
 free(temp);
}
 
 6.2.4 Count Nodes 
 int countNodes(struct Node *head) {
 if (head == NULL) {
 return 0;
 }
 
 int count = 1;
 struct Node *temp = head->next;
 
 while (temp != head) {
 count++;
 temp = temp->next;
 }
 
 return count;
}

7. Advanced Linked List Operations
7.1 Reverse a Singly Linked List 
 Method 1: Iterative 
 void reverseList(struct Node **head) {
 struct Node *prev = NULL;
 struct Node *current = *head;
 struct Node *next = NULL;
 
 while (current != NULL) {
 // Store next
 next = current->next;
 
 // Reverse current node's pointer
 current->next = prev;
 
 // Move pointers one position ahead
 prev = current;
 current = next;
 }
 
 *head = prev;
}
 
 Visual Steps: 
 Initial: head → [10|●] → [20|●] → [30|NULL]

Step 1: prev=NULL, current=[10], next=[20]
NULL ← [10] [20|●] → [30|NULL]

Step 2: prev=[10], current=[20], next=[30]
NULL ← [10] ← [20] [30|NULL]

Step 3: prev=[20], current=[30], next=NULL
NULL ← [10] ← [20] ← [30]

Final: head → [30|●] → [20|●] → [10|NULL]
 
 Time Complexity: O(n)
 Space Complexity: O(1) 
 Method 2: Recursive 
 struct Node* reverseRecursive(struct Node *head) {
 // Base case: empty list or single node
 if (head == NULL || head->next == NULL) {
 return head;
 }
 
 // Reverse the rest of the list
 struct Node *newHead = reverseRecursive(head->next);
 
 // Make next node point back
 head->next->next = head;
 head->next = NULL;
 
 return newHead;
}

// Wrapper function
void reverseListRecursive(struct Node **head) {
 *head = reverseRecursive(*head);
}
 
 Time Complexity: O(n)
 Space Complexity: O(n) - recursion stack 
 7.2 Find Middle Element 
 Method 1: Two-Pass 
 int findMiddle(struct Node *head) {
 if (head == NULL) {
 printf("List is empty!\n");
 return -1;
 }
 
 // Count nodes
 int count = 0;
 struct Node *temp = head;
 while (temp != NULL) {
 count++;
 temp = temp->next;
 }
 
 // Go to middle
 temp = head;
 for (int i = 0; i < count / 2; i++) {
 temp = temp->next;
 }
 
 return temp->data;
}
 
 Method 2: Slow-Fast Pointer (Optimal) 
 int findMiddleFast(struct Node *head) {
 if (head == NULL) {
 printf("List is empty!\n");
 return -1;
 }
 
 struct Node *slow = head;
 struct Node *fast = head;
 
 // Fast moves 2 steps, slow moves 1 step
 while (fast != NULL && fast->next != NULL) {
 slow = slow->next;
 fast = fast->next->next;
 }
 
 return slow->data;
}
 
 Visual Steps: 
 List: [10] → [20] → [30] → [40] → [50] → NULL

Step 1: slow=[10], fast=[10]
Step 2: slow=[20], fast=[30]
Step 3: slow=[30], fast=[50]
Step 4: fast->next=NULL, stop

Middle: 30
 
 Time Complexity: O(n)
 Space Complexity: O(1) 
 7.3 Detect Cycle (Floyd's Algorithm) 
 int hasCycle(struct Node *head) {
 if (head == NULL) {
 return 0;
 }
 
 struct Node *slow = head;
 struct Node *fast = head;
 
 while (fast != NULL && fast->next != NULL) {
 slow = slow->next;
 fast = fast->next->next;
 
 // If they meet, there's a cycle
 if (slow == fast) {
 return 1;
 }
 }
 
 return 0; // No cycle
}
 
 Visual Representation: 
 Cycle Example:
 ┌──────────────┐
 ↓ │
[10] → [20] → [30] → [40]
 ↑ ↓
 └─────┘

Without cycle:
[10] → [20] → [30] → [40] → NULL
 
 Time Complexity: O(n)
 Space Complexity: O(1) 
 7.4 Remove Duplicates from Sorted List 
 void removeDuplicates(struct Node *head) {
 if (head == NULL) {
 return;
 }
 
 struct Node *current = head;
 
 while (current->next != NULL) {
 if (current->data == current->next->data) {
 // Duplicate found
 struct Node *temp = current->next;
 current->next = temp->next;
 free(temp);
 } else {
 current = current->next;
 }
 }
}
 
 Visual Steps:

8. Practical Applications
8.1 Polynomial Addition 
 #include <stdio.h>
#include <stdlib.h>

// Node for polynomial term
struct PolyNode {
 int coeff; // Coefficient
 int exp; // Exponent
 struct PolyNode *next;
};

// Insert term in descending order of exponent
void insertTerm(struct PolyNode **poly, int coeff, int exp) {
 struct PolyNode *newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));
 newNode->coeff = coeff;
 newNode->exp = exp;
 newNode->next = NULL;
 
 if (*poly == NULL || (*poly)->exp < exp) {
 newNode->next = *poly;
 *poly = newNode;
 } else {
 struct PolyNode *temp = *poly;
 while (temp->next != NULL && temp->next->exp > exp) {
 temp = temp->next;
 }
 newNode->next = temp->next;
 temp->next = newNode;
 }
}

// Add two polynomials
struct PolyNode* addPolynomials(struct PolyNode *poly1, struct PolyNode *poly2) {
 struct PolyNode *result = NULL;
 
 while (poly1 != NULL && poly2 != NULL) {
 if (poly1->exp > poly2->exp) {
 insertTerm(&result, poly1->coeff, poly1->exp);
 poly1 = poly1->next;
 } else if (poly1->exp < poly2->exp) {
 insertTerm(&result, poly2->coeff, poly2->exp);
 poly2 = poly2->next;
 } else {
 // Same exponent - add coefficients
 int sumCoeff = poly1->coeff + poly2->coeff;
 if (sumCoeff != 0) {
 insertTerm(&result, sumCoeff, poly1->exp);
 }
 poly1 = poly1->next;
 poly2 = poly2->next;
 }
 }
 
 // Add remaining terms
 while (poly1 != NULL) {
 insertTerm(&result, poly1->coeff, poly1->exp);
 poly1 = poly1->next;
 }
 
 while (poly2 != NULL) {
 insertTerm(&result, poly2->coeff, poly2->exp);
 poly2 = poly2->next;
 }
 
 return result;
}

// Display polynomial
void displayPoly(struct PolyNode *poly) {
 if (poly == NULL) {
 printf("0\n");
 return;
 }
 
 while (poly != NULL) {
 printf("%dx^%d", poly->coeff, poly->exp);
 poly = poly->next;
 if (poly != NULL) {
 printf(" + ");
 }
 }
 printf("\n");
}

int main() {
 struct PolyNode *poly1 = NULL;
 struct PolyNode *poly2 = NULL;
 
 // Create first polynomial: 5x^3 + 4x^2 + 2
 insertTerm(&poly1, 5, 3);
 insertTerm(&poly1, 4, 2);
 insertTerm(&poly1, 2, 0);
 
 // Create second polynomial: 3x^3 + 2x + 1
 insertTerm(&poly2, 3, 3);
 insertTerm(&poly2, 2, 1);
 insertTerm(&poly2, 1, 0);
 
 printf("Polynomial 1: ");
 displayPoly(poly1);
 
 printf("Polynomial 2: ");
 displayPoly(poly2);
 
 struct PolyNode *result = addPolynomials(poly1, poly2);
 
 printf("Sum: ");
 displayPoly(result);
 
 return 0;
}

/* Output:
Polynomial 1: 5x^3 + 4x^2 + 2x^0
Polynomial 2: 3x^3 + 2x^1 + 1x^0
Sum: 8x^3 + 4x^2 + 2x^1 + 3x^0
*/
 
 8.2 Music Playlist Implementation 
 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Song {
 char title[100];
 char artist[100];
 int duration; // in seconds
 struct Song *next;
};

// Add song to playlist
void addSong(struct Song **playlist, const char *title, const char *artist, int duration) {
 struct Song *newSong = (struct Song*)malloc(sizeof(struct Song));
 strcpy(newSong->title, title);
 strcpy(newSong->artist, artist);
 newSong->duration = duration;
 newSong->next = NULL;
 
 if (*playlist == NULL) {
 *playlist = newSong;
 } else {
 struct Song *temp = *playlist;
 while (temp->next != NULL) {
 temp = temp->next;
 }
 temp->next = newSong;
 }
}

// Display playlist
void displayPlaylist(struct Song *playlist) {
 if (playlist == NULL) {
 printf("Playlist is empty!\n");
 return;
 }
 
 int count = 1;
 printf("\n=== Playlist ===\n");
 while (playlist != NULL) {
 printf("%d. %s - %s (%d:%02d)\n", 
 count++, 
 playlist->title, 
 playlist->artist,
 playlist->duration / 60, 
 playlist->duration % 60);
 playlist = playlist->next;
 }
}

// Remove song by title
void removeSong(struct Song **playlist, const char *title) {
 if (*playlist == NULL) {
 printf("Playlist is empty!\n");
 return;
 }
 
 // If first song matches
 if (strcmp((*playlist)->title, title) == 0) {
 struct Song *temp = *playlist;
 *playlist = (*playlist)->next;
 free(temp);
 printf("Song removed: %s\n", title);
 return;
 }
 
 // Search for song
 struct Song *temp = *playlist;
 while (temp->next != NULL && strcmp(temp->next->title, title) != 0) {
 temp = temp->next;
 }
 
 if (temp->next == NULL) {
 printf("Song not found: %s\n", title);
 return;
 }
 
 struct Song *toRemove = temp->next;
 temp->next = toRemove->next;
 free(toRemove);
 printf("Song removed: %s\n", title);
}

// Calculate total duration
int totalDuration(struct Song *playlist) {
 int total = 0;
 while (playlist != NULL) {
 total += playlist->duration;
 playlist = playlist->next;
 }
 return total;
}

int main() {
 struct Song *myPlaylist = NULL;
 
 // Add songs
 addSong(&myPlaylist, "Bohemian Rhapsody", "Queen", 354);
 addSong(&myPlaylist, "Stairway to Heaven", "Led Zeppelin", 482);
 addSong(&myPlaylist, "Hotel California", "Eagles", 391);
 addSong(&myPlaylist, "Imagine", "John Lennon", 183);
 
 displayPlaylist(myPlaylist);
 
 int total = totalDuration(myPlaylist);
 printf("\nTotal duration: %d:%02d\n", total / 60, total % 60);
 
 // Remove a song
 removeSong(&myPlaylist, "Hotel California");
 
 displayPlaylist(myPlaylist);
 
 return 0;
}
 
 8.3 Browser History (Back/Forward Navigation) 
 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Page {
 char url[200];
 struct Page *prev;
 struct Page *next;
};

struct Browser {
 struct Page *current;
};

// Visit new page
void visitPage(struct Browser *browser, const char *url) {
 struct Page *newPage = (struct Page*)malloc(sizeof(struct Page));
 strcpy(newPage->url, url);
 newPage->next = NULL;
 
 if (browser->current != NULL) {
 // Clear forward history
 struct Page *temp = browser->current->next;
 while (temp != NULL) {
 struct Page *toDelete = temp;
 temp = temp->next;
 free(toDelete);
 }
 
 browser->current->next = newPage;
 newPage->prev = browser->current;
 } else {
 newPage->prev = NULL;
 }
 
 browser->current = newPage;
 printf("Visited: %s\n", url);
}

// Go back
void goBack(struct Browser *browser) {
 if (browser->current == NULL || browser->current->prev == NULL) {
 printf("Cannot go back!\n");
 return;
 }
 
 browser->current = browser->current->prev;
 printf("Back to: %s\n", browser->current->url);
}

// Go forward
void goForward(struct Browser *browser) {
 if (browser->current == NULL || browser->current->next == NULL) {
 printf("Cannot go forward!\n");
 return;
 }
 
 browser->current = browser->current->next;
 printf("Forward to: %s\n", browser->current->url);
}

// Display current page
void displayCurrent(struct Browser *browser) {
 if (browser->current == NULL) {
 printf("No page loaded!\n");
 } else {
 printf("Current page: %s\n", browser->current->url);
 }
}

int main() {
 struct Browser browser = {NULL};
 
 visitPage(&browser, "https://google.com");
 visitPage(&browser, "https://github.com");
 visitPage(&browser, "https://stackoverflow.com");
 
 printf("\n");
 goBack(&browser);
 goBack(&browser);
 
 printf("\n");
 goForward(&browser);
 
 printf("\n");
 visitPage(&browser, "https://reddit.com");
 
 printf("\n");
 displayCurrent(&browser);
 
 return 0;
}

9. Common Errors and Debugging
9.1 Memory Leaks 
 Problem: 
 void createList() {
 struct Node *head = (struct Node*)malloc(sizeof(struct Node));
 head->data = 10;
 head->next = NULL;
 // MEMORY LEAK! head is lost when function returns
}
 
 Solution: 
 struct Node* createList() {
 struct Node *head = (struct Node*)malloc(sizeof(struct Node));
 head->data = 10;
 head->next = NULL;
 return head; // Return pointer to caller
}

// In main:
struct Node *myList = createList();
// ... use list ...
freeList(&myList); // Free memory when done
 
 9.2 Dereferencing NULL Pointer 
 Problem: 
 void insertAtEnd(struct Node **head, int value) {
 struct Node *temp = *head;
 while (temp->next != NULL) { // CRASH if head is NULL!
 temp = temp->next;
 }
 // ...
}
 
 Solution: 
 void insertAtEnd(struct Node **head, int value) {
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 newNode->data = value;
 newNode->next = NULL;
 
 if (*head == NULL) { // Check for NULL first!
 *head = newNode;
 return;
 }
 
 struct Node *temp = *head;
 while (temp->next != NULL) {
 temp = temp->next;
 }
 temp->next = newNode;
}
 
 9.3 Lost Node References 
 Problem: 
 void deleteNode(struct Node **head, int position) {
 struct Node *temp = *head;
 for (int i = 0; i < position - 1; i++) {
 temp = temp->next;
 }
 temp->next = temp->next->next; // MEMORY LEAK! Node not freed
}
 
 Solution: 
 void deleteNode(struct Node **head, int position) {
 struct Node *temp = *head;
 for (int i = 0; i < position - 1; i++) {
 temp = temp->next;
 }
 struct Node *nodeToDelete = temp->next; // Save reference
 temp->next = nodeToDelete->next;
 free(nodeToDelete); // Free memory
}
 
 9.4 Infinite Loop in Circular List 
 Problem: 
 void display(struct Node *head) {
 struct Node *temp = head;
 while (temp != NULL) { // Never NULL in circular list!
 printf("%d ", temp->data);
 temp = temp->next;
 }
}
 
 Solution: 
 void displayCircular(struct Node *head) {
 if (head == NULL) return;
 
 struct Node *temp = head;
 do {
 printf("%d ", temp->data);
 temp = temp->next;
 } while (temp != head); // Check if back to head
}
 
 9.5 Incorrect Pointer Updates 
 Problem: 
 void insertAtBeginning(struct Node *head, int value) {
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 newNode->data = value;
 newNode->next = head;
 head = newNode; // Only changes local copy!
}
 
 Solution: 
 void insertAtBeginning(struct Node **head, int value) {
 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
 newNode->data = value;
 newNode->next = *head;
 *head = newNode; // Updates actual head pointer
}
 
 9.6 Debugging Techniques 
 Print Node Addresses 
 void debugList(struct Node *head) {
 printf("\n=== Debug Info ===\n");
 struct Node *temp = head;
 int count = 0;
 
 while (temp != NULL) {
 printf("Node %d:\n", count++);
 printf(" Address: %p\n", (void*)temp);
 printf(" Data: %d\n", temp->data);
 printf(" Next: %p\n", (void*)temp->next);
 temp = temp->next;
 }
 printf("==================\n\n");
}
 
 Check List Integrity 
 int checkListIntegrity(struct Node *head) {
 if (head == NULL) {
 return 1; // Empty list is valid
 }
 
 struct Node *slow = head;
 struct Node *fast = head;
 
 // Check for cycles
 while (fast != NULL && fast->next != NULL) {
 slow = slow->next;
 fast = fast->next->next;
 
 if (slow == fast) {
 printf("ERROR: Cycle detected!\n");
 return 0;
 }
 }
 
 printf("List integrity: OK\n");
 return 1;
}
 
 Visualize List 
 void visualizeList(struct Node *head) {
 if (head == NULL) {
 printf("NULL\n");
 return;
 }
 
 struct Node *temp = head;
 printf("HEAD → ");
 
 while (temp != NULL) {
 printf("[%d]", temp->data);
 temp = temp->next;
 if (temp != NULL) {
 printf(" → ");
 }
 }
 printf(" → NULL\n");
}
 
 9.7 Common Error Messages 
 Segmentation Fault: 
 
 Dereferencing NULL pointer 
 Accessing freed memory 
 Buffer overflow 
 
 Memory Leak: 
 
 Not freeing allocated memory 
 Losing references to nodes 
 Not calling free() on all nodes 
 
 Infinite Loop: 
 
 Wrong termination condition 
 Circular list without proper check 
 Pointer not advancing 
 
 9.8 Preventive Measures 
 // Always check malloc return value
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
 fprintf(stderr, "Memory allocation failed!\n");
 return NULL;
}

// Check for NULL before dereferencing
if (head != NULL) {
 // Safe to use head->data
}

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

// Set pointers to NULL after freeing
free(node);
node = NULL;

// Use assertions for debugging
#include <assert.h>
assert(head != NULL); // Program stops if false