Overview of Linked Lists
A linked list is a data structure used for storing collections of data. Unlike arrays, linked lists do not require contiguous memory locations. Each element in a linked list is called a node, and each node contains two parts: data and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements.
Definition and Basic Concepts
Node: The fundamental building block of a linked list. Each node contains data and a reference to the next node.
Head: The first node in a linked list.
Tail: The last node in a linked list, which points to null (or, in circular linked lists, points back to the head).
Pointer/Reference: The link part of the node that points to the next node in the sequence.
Null: Indicates the end of the list.
Advantages of Linked Lists
Dynamic Size: Unlike arrays, linked lists can grow and shrink in size by allocating and deallocating memory as needed.
Ease of Insertion/Deletion: Elements can be inserted or removed without reorganizing the entire data structure. This is particularly useful for applications where frequent addition and removal of elements occur.
Efficient Memory Utilization: Memory is allocated as needed. There is no need to allocate memory for a fixed size in advance.
Disadvantages of Linked Lists
Memory Overhead: Each node requires additional memory for storing the reference to the next node.
Sequential Access: Accessing an element requires traversing from the head to the desired node, resulting in O(n) time complexity for access operations.
Cache Performance: Linked lists may exhibit poor cache performance due to non-contiguous memory allocation, leading to more frequent cache misses.
Applications of Linked Lists
Implementation of Stacks and Queues: Linked lists are used to implement these abstract data types due to their dynamic size and ease of insertion and deletion.
Graph Adjacency List Representation: Linked lists are used to represent adjacency lists in graph algorithms, providing efficient storage and traversal of adjacent vertices.
Dynamic Memory Allocation: Linked lists are used in dynamic memory management systems to keep track of free and allocated memory blocks.
Polynomial Manipulation: Linked lists are used to represent and manipulate polynomials, where each node represents a term of the polynomial.
Representation of Linked Lists
A linked list can be represented as a collection of nodes, where each node contains:
Data: The actual value or information stored in the node.
Next: A reference or pointer to the next node in the list.
This is a simple representation of a singly linked list node in C-like pseudocode:
struct Node {
int data;
struct Node* next;
};
To create a linked list, you need to manage the head of the list and ensure that each node points to the next node. For example:
struct Node* head = NULL; // Initialize an empty linked list
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to add a node at the beginning of the list
void insertAtBeginning(int data) {
struct Node* newNode = createNode(data);
newNode->next = head;
head = newNode;
}
In this example, head points to the first node in the list, and each node points to the next node, forming the linked list structure.
Types of Linked Lists
Singly Linked List
A singly linked list is the simplest type of linked list. In this structure, each node contains data and a reference (or link) to the next node in the sequence. The list terminates with a node pointing to null, indicating the end of the list.
Structure of a Singly Linked List Node:
struct Node {
int data;
struct Node* next;
};
Advantages:
Simple to implement.
Efficient insertion and deletion operations, especially at the beginning of the list.
Disadvantages:
Only supports traversal in one direction (forward).
Cannot easily access the previous node without traversing from the head.
Applications:
Implementing stacks and queues.
Basic data storage when dynamic memory allocation is needed.
Doubly Linked List
A doubly linked list is an extension of the singly linked list. Each node contains data and two references: one pointing to the next node and another pointing to the previous node. This allows traversal in both directions.
Structure of a Doubly Linked List Node:
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
Advantages:
Supports efficient bidirectional traversal.
Easier to delete a node when given a reference to it, as the previous node is directly accessible.
Disadvantages:
Requires more memory per node due to the additional reference.
Slightly more complex to implement and manage.
Applications:
Implementing navigation systems (e.g., browsers' forward and backward navigation).
Managing data structures where bidirectional traversal is required.
Circular Linked List
In a circular linked list, the last node's next reference points back to the head of the list, forming a circular structure. Circular linked lists can be either singly or doubly linked.
Structure of a Circular Singly Linked List Node:
struct Node {
int data;
struct Node* next;
};
Advantages:
The list can be traversed from any node.
Efficient for implementing circular buffers or round-robin scheduling.
Disadvantages:
More complex to implement compared to a standard linked list.
Care must be taken to avoid infinite loops during traversal.
Applications:
Implementing circular buffers.
Scheduling algorithms like round-robin.
Header Linked List
A header linked list is a variation of the linked list where an additional node, called the header node, is introduced at the beginning of the list. This header node does not contain meaningful data but serves as a reference point for the start of the list.
Structure of a Header Linked List Node:
struct Node {
int data;
struct Node* next;
};
Header Node:
struct Node* header;
header = (struct Node*)malloc(sizeof(struct Node));
header->next = NULL; // Initially, the list is empty
Advantages:
Simplifies the implementation by eliminating special cases for the head of the list.
Easier to manage an empty list.
Disadvantages:
- Requires an extra node, leading to slight memory overhead.
Applications:
Used in implementations where simplifying list management is beneficial.
Useful in scenarios requiring frequent insertions and deletions at the beginning of the list.
Single Linked List Operations in C
1. Traversal
Traversal is the process of visiting each node in the linked list and performing some operation (e.g., printing the data).
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to traverse and print the linked list
void traverse(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
2. Insertion
Insertion can be done at various positions: at the beginning, at the end, or at a specified position.
Insert at Beginning:
// Function to insert a node at the beginning of the linked list
void insertAtBeginning(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
Insert at End:
// Function to insert a node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
}
Insert at a Given Position:
// Function to insert a node after a given previous node
void insertAfter(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
printf("The given previous node cannot be NULL");
return;
}
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
3. Deletion
Delete a Node at the Beginning:
cCopy code// Function to delete the first node of the linked list
void deleteAtBeginning(struct Node** head_ref) {
if (*head_ref == NULL) return;
struct Node* temp = *head_ref;
*head_ref = temp->next;
free(temp);
}
Delete a Node in the Middle (by Key):
cCopy code// Function to delete the first occurrence of a given key in the linked list
void deleteAtMiddle(struct Node** head_ref, int key) {
struct Node* temp = *head_ref;
struct Node* prev = NULL;
// If the head node itself holds the key to be deleted
if (temp != NULL && temp->data == key) {
*head_ref = temp->next;
free(temp);
return;
}
// Search for the key to be deleted, keeping track of the previous node
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// If the key was not present in the list
if (temp == NULL) return;
// Unlink the node from the linked list
prev->next = temp->next;
free(temp);
}
Delete the Last Node:
cCopy code// Function to delete the last node of the linked list
void deleteAtEnd(struct Node** head_ref) {
if (*head_ref == NULL) return;
struct Node* temp = *head_ref;
struct Node* prev = NULL;
// If there is only one node in the list
if (temp->next == NULL) {
free(temp);
*head_ref = NULL;
return;
}
// Traverse to the last node
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
// Unlink the last node
prev->next = NULL;
free(temp);
}
Example program demonstrating all the operations:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function prototypes
void traverse(struct Node* head);
void insertAtBeginning(struct Node** head_ref, int new_data);
void insertAtEnd(struct Node** head_ref, int new_data);
void deleteAtBeginning(struct Node** head_ref);
void deleteAtMiddle(struct Node** head_ref, int key);
void deleteAtEnd(struct Node** head_ref);
int main() {
struct Node* head = NULL;
// Insert nodes
insertAtBeginning(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
insertAtEnd(&head, 4);
printf("Linked List after insertion: ");
traverse(head);
// Delete at beginning
deleteAtBeginning(&head);
printf("Linked List after deleting at beginning: ");
traverse(head);
// Delete node with data 3
deleteAtMiddle(&head, 3);
printf("Linked List after deleting node with data 3: ");
traverse(head);
// Delete at end
deleteAtEnd(&head);
printf("Linked List after deleting at end: ");
traverse(head);
return 0;
}
// Function implementations as given above
Doubly Linked List Operations in C
Structure of a Doubly Linked List Node
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
1. Traversal
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Function to traverse and print the doubly linked list from the head
void traverseForward(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// Function to traverse and print the doubly linked list from the tail
void traverseBackward(struct Node* tail) {
struct Node* current = tail;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->prev;
}
printf("NULL\n");
}
2. Insertion
Insert at Beginning:
// Function to insert a node at the beginning of the doubly linked list
void insertAtBeginning(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = *head_ref;
new_node->prev = NULL;
if (*head_ref != NULL) {
(*head_ref)->prev = new_node;
}
*head_ref = new_node;
}
Insert at End:
// Function to insert a node at the end of the doubly linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
new_node->prev = last;
}
Insert at a Given Position:
// Function to insert a node after a given previous node
void insertAfter(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
printf("The given previous node cannot be NULL");
return;
}
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
new_node->prev = prev_node;
if (prev_node->next != NULL) {
prev_node->next->prev = new_node;
}
prev_node->next = new_node;
}
3. Deletion
Delete a Node at the Beginning:
// Function to delete the first node of the doubly linked list
void deleteAtBeginning(struct Node** head_ref) {
if (*head_ref == NULL) return;
struct Node* temp = *head_ref;
*head_ref = temp->next;
if (*head_ref != NULL) {
(*head_ref)->prev = NULL;
}
free(temp);
}
Delete a Node in the Middle (by Key):
// Function to delete the first occurrence of a given key in the doubly linked list
void deleteAtMiddle(struct Node** head_ref, int key) {
struct Node* temp = *head_ref;
// Search for the key to be deleted
while (temp != NULL && temp->data != key) {
temp = temp->next;
}
// If the key was not present in the list
if (temp == NULL) return;
// Unlink the node from the doubly linked list
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
if (temp->prev != NULL) {
temp->prev->next = temp->next;
} else { // Node to be deleted is the head node
*head_ref = temp->next;
}
free(temp);
}
Delete the Last Node:
// Function to delete the last node of the doubly linked list
void deleteAtEnd(struct Node** head_ref) {
if (*head_ref == NULL) return;
struct Node* temp = *head_ref;
// Traverse to the last node
while (temp->next != NULL) {
temp = temp->next;
}
// Unlink the last node
if (temp->prev != NULL) {
temp->prev->next = NULL;
} else { // The list only had one node
*head_ref = NULL;
}
free(temp);
}
Example program demonstrating traversal, insertion at the beginning, middle, and end, and deletion at the beginning, middle, and end:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Function prototypes
void traverseForward(struct Node* head);
void traverseBackward(struct Node* tail);
void insertAtBeginning(struct Node** head_ref, int new_data);
void insertAtEnd(struct Node** head_ref, int new_data);
void insertAfter(struct Node* prev_node, int new_data);
void deleteAtBeginning(struct Node** head_ref);
void deleteAtMiddle(struct Node** head_ref, int key);
void deleteAtEnd(struct Node** head_ref);
int main() {
struct Node* head = NULL;
// Insert nodes
insertAtBeginning(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
insertAfter(head->next, 4);
printf("Doubly Linked List after insertion: ");
traverseForward(head);
// Delete at beginning
deleteAtBeginning(&head);
printf("Doubly Linked List after deleting at beginning: ");
traverseForward(head);
// Delete node with data 3
deleteAtMiddle(&head, 3);
printf("Doubly Linked List after deleting node with data 3: ");
traverseForward(head);
// Delete at end
deleteAtEnd(&head);
printf("Doubly Linked List after deleting at end: ");
traverseForward(head);
return 0;
}
// Function implementations as given above
Circular Linked List Operations in C
Structure of a Circular Linked List Node
struct Node {
int data;
struct Node* next;
};
1. Traversal
Traversal in a circular linked list involves starting from the head and continuing until we reach the head again.
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to traverse and print the circular linked list
void traverse(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return;
}
struct Node* current = head;
do {
printf("%d -> ", current->data);
current = current->next;
} while (current != head);
printf("(head)\n");
}
2. Insertion
Insertion in a circular linked list can be done at the beginning, end, or after a given node.
Insert at Beginning:
// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = *head_ref;
if (*head_ref != NULL) {
while (last->next != *head_ref) {
last = last->next;
}
last->next = new_node;
} else {
new_node->next = new_node; // For the first node
}
*head_ref = new_node;
}
Insert at End:
// Function to insert a node at the end of the circular linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = *head_ref;
if (*head_ref == NULL) {
new_node->next = new_node;
*head_ref = new_node;
return;
}
while (last->next != *head_ref) {
last = last->next;
}
last->next = new_node;
}
Insert After a Given Node:
// Function to insert a node after a given node in the circular linked list
void insertAfter(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
printf("The given previous node cannot be NULL");
return;
}
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
3. Deletion
Delete a Node at the Beginning:
// Function to delete the first node of the circular linked list
void deleteAtBeginning(struct Node** head_ref) {
if (*head_ref == NULL) return;
struct Node* last = *head_ref;
struct Node* temp = *head_ref;
if ((*head_ref)->next == *head_ref) {
*head_ref = NULL;
free(temp);
return;
}
while (last->next != *head_ref) {
last = last->next;
}
last->next = (*head_ref)->next;
*head_ref = (*head_ref)->next;
free(temp);
}
Delete a Node by Key:
// Function to delete the first occurrence of a given key in the circular linked list
void deleteAtMiddle(struct Node** head_ref, int key) {
if (*head_ref == NULL) return;
struct Node* temp = *head_ref;
struct Node* prev = NULL;
while (temp->data != key) {
if (temp->next == *head_ref) {
printf("Given node not found in the list\n");
return;
}
prev = temp;
temp = temp->next;
}
if (temp == *head_ref && temp->next == *head_ref) {
*head_ref = NULL;
free(temp);
return;
}
if (temp == *head_ref) {
prev = *head_ref;
while (prev->next != *head_ref) {
prev = prev->next;
}
*head_ref = temp->next;
prev->next = *head_ref;
free(temp);
} else if (temp->next == *head_ref) {
prev->next = *head_ref;
free(temp);
} else {
prev->next = temp->next;
free(temp);
}
}
Delete the Last Node:
// Function to delete the last node of the circular linked list
void deleteAtEnd(struct Node** head_ref) {
if (*head_ref == NULL) return;
struct Node* last = *head_ref;
struct Node* prev = NULL;
if (last->next == *head_ref) {
*head_ref = NULL;
free(last);
return;
}
while (last->next != *head_ref) {
prev = last;
last = last->next;
}
prev->next = *head_ref;
free(last);
}
Example program demonstrating traversal, insertion at the beginning, middle, and end, and deletion at the beginning, middle, and end:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function prototypes
void traverse(struct Node* head);
void insertAtBeginning(struct Node** head_ref, int new_data);
void insertAtEnd(struct Node** head_ref, int new_data);
void insertAfter(struct Node* prev_node, int new_data);
void deleteAtBeginning(struct Node** head_ref);
void deleteAtMiddle(struct Node** head_ref, int key);
void deleteAtEnd(struct Node** head_ref);
int main() {
struct Node* head = NULL;
// Insert nodes
insertAtBeginning(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
insertAfter(head->next, 4);
printf("Circular Linked List after insertion: ");
traverse(head);
// Delete at beginning
deleteAtBeginning(&head);
printf("Circular Linked List after deleting at beginning: ");
traverse(head);
// Delete node with data 3
deleteAtMiddle(&head, 3);
printf("Circular Linked List after deleting node with data 3: ");
traverse(head);
// Delete at end
deleteAtEnd(&head);
printf("Circular Linked List after deleting at end: ");
traverse(head);
return 0;
}
// Function implementations as given above
Polynomial Representation Using Linked Lists
Polynomials can be represented using linked lists where each node represents a term of the polynomial. Each node contains the coefficient and exponent of the term, along with a pointer to the next term.
Structure of a Polynomial Node
struct Node {
int coeff;
int exp;
struct Node* next;
};
Polynomial Operations
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int coeff;
int exp;
struct Node* next;
};
// Function prototypes
struct Node* createNode(int coeff, int exp);
void insertNode(struct Node** poly, int coeff, int exp);
void printPolynomial(struct Node* poly);
struct Node* addPolynomials(struct Node* poly1, struct Node* poly2);
struct Node* subtractPolynomials(struct Node* poly1, struct Node* poly2);
struct Node* multiplyPolynomials(struct Node* poly1, struct Node* poly2);
struct Node* dividePolynomials(struct Node* poly1, struct Node* poly2, struct Node** remainder);
// Main function
int main() {
struct Node* poly1 = NULL;
struct Node* poly2 = NULL;
struct Node* quotient = NULL;
struct Node* remainder = NULL;
// Create first polynomial: 5x^2 + 4x + 2
insertNode(&poly1, 5, 2);
insertNode(&poly1, 4, 1);
insertNode(&poly1, 2, 0);
// Create second polynomial: x + 1
insertNode(&poly2, 1, 1);
insertNode(&poly2, 1, 0);
printf("Polynomial 1: ");
printPolynomial(poly1);
printf("Polynomial 2: ");
printPolynomial(poly2);
quotient = dividePolynomials(poly1, poly2, &remainder);
printf("Quotient: ");
printPolynomial(quotient);
printf
("Remainder: ");
printPolynomial(remainder);
return 0;
}
// Function to create a new node
struct Node* createNode(int coeff, int exp) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->coeff = coeff;
new_node->exp = exp;
new_node->next = NULL;
return new_node;
}
// Function to insert a new node into the polynomial linked list
void insertNode(struct Node** poly, int coeff, int exp) {
struct Node* new_node = createNode(coeff, exp);
if (*poly == NULL) {
*poly = new_node;
} else {
struct Node* temp = *poly;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
}
}
// Function to print the polynomial linked list
void printPolynomial(struct Node* poly) {
while (poly != NULL) {
printf("%dx^%d", poly->coeff, poly->exp);
poly = poly->next;
if (poly != NULL) printf(" + ");
}
printf("\n");
}
// Function to add two polynomials
struct Node* addPolynomials(struct Node* poly1, struct Node* poly2) {
struct Node* result = NULL;
while (poly1 != NULL && poly2 != NULL) {
if (poly1->exp > poly2->exp) {
insertNode(&result, poly1->coeff, poly1->exp);
poly1 = poly1->next;
} else if (poly1->exp < poly2->exp) {
insertNode(&result, poly2->coeff, poly2->exp);
poly2 = poly2->next;
} else {
insertNode(&result, poly1->coeff + poly2->coeff, poly1->exp);
poly1 = poly1->next;
poly2 = poly2->next;
}
}
while (poly1 != NULL) {
insertNode(&result, poly1->coeff, poly1->exp);
poly1 = poly1->next;
}
while (poly2 != NULL) {
insertNode(&result, poly2->coeff, poly2->exp);
poly2 = poly2->next;
}
return result;
}
// Function to subtract two polynomials
struct Node* subtractPolynomials(struct Node* poly1, struct Node* poly2) {
struct Node* result = NULL;
while (poly1 != NULL && poly2 != NULL) {
if (poly1->exp > poly2->exp) {
insertNode(&result, poly1->coeff, poly1->exp);
poly1 = poly1->next;
} else if (poly1->exp < poly2->exp) {
insertNode(&result, -poly2->coeff, poly2->exp);
poly2 = poly2->next;
} else {
insertNode(&result, poly1->coeff - poly2->coeff, poly1->exp);
poly1 = poly1->next;
poly2 = poly2->next;
}
}
while (poly1 != NULL) {
insertNode(&result, poly1->coeff, poly1->exp);
poly1 = poly1->next;
}
while (poly2 != NULL) {
insertNode(&result, -poly2->coeff, poly2->exp);
poly2 = poly2->next;
}
return result;
}
// Function to multiply two polynomials
struct Node* multiplyPolynomials(struct Node* poly1, struct Node* poly2) {
struct Node* result = NULL;
struct Node* poly1_temp = poly1;
struct Node* poly2_temp = poly2;
while (poly1_temp != NULL) {
while (poly2_temp != NULL) {
int coeff = poly1_temp->coeff * poly2_temp->coeff;
int exp = poly1_temp->exp + poly2_temp->exp;
insertNode(&result, coeff, exp);
poly2_temp = poly2_temp->next;
}
poly2_temp = poly2;
poly1_temp = poly1_temp->next;
}
return result;
}
// Function to divide two polynomials
struct Node* dividePolynomials(struct Node* poly1, struct Node* poly2, struct Node** remainder) {
struct Node* quotient = NULL;
*remainder = poly1;
while (*remainder != NULL && (*remainder)->exp >= poly2->exp) {
int coeff = (*remainder)->coeff / poly2->coeff;
int exp = (*remainder)->exp - poly2->exp;
insertNode("ient, coeff, exp);
struct Node* term = createNode(coeff, exp);
struct Node* temp = multiplyPolynomials(poly2, term);
*remainder = subtractPolynomials(*remainder, temp);
}
return quotient;
}
Problems:
Reverse a Single Linked List: Develop a C function to reverse a single linked list. The function should return the head of the reversed list.
Detect a Cycle in a Single Linked List: Write a C program to detect whether a cycle (loop) exists in a single linked list. Use Floyd’s Cycle-Finding Algorithm (Tortoise and Hare).
Merge Two Sorted Single Linked Lists: Implement a function in C to merge two sorted single linked lists into one sorted list. The merged list should maintain the sorted order.
Find the Middle of a Single Linked List: Write a C function to find the middle element of a single linked list. If the list has an even number of nodes, return the second middle element.
Convert a Single Linked List into a Circular Linked List: Write a C program to convert a single linked list into a circular linked list by linking the last node to the first node.
Solutions:
1. Reverse a Single Linked List
#include <stdio.h>
#include <stdlib.h>
// Definition for the singly linked list node
struct Node {
int data;
struct Node* next;
};
// Function to reverse a singly linked list
struct Node* reverseList(struct Node* head) {
struct Node* prev = NULL;
struct Node* current = head;
struct Node* next = NULL;
while (current != NULL) {
next = current->next; // Store the next node
current->next = prev; // Reverse the current node's pointer
prev = current; // Move pointers one position ahead
current = next;
}
return prev; // New head of the reversed list
}
// Utility function to print the list
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// Utility function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
int main() {
// Creating a simple linked list 1->2->3->4->NULL
struct Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
printf("Original List: ");
printList(head);
head = reverseList(head);
printf("Reversed List: ");
printList(head);
return 0;
}
2. Detect a Cycle in a Single Linked List (Floyd's Cycle-Finding Algorithm)
#include <stdio.h>
#include <stdlib.h>
// Definition for the singly linked list node
struct Node {
int data;
struct Node* next;
};
// Function to detect a cycle in the linked list
int detectCycle(struct Node* head) {
struct Node* slow = head;
struct Node* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next; // Move slow pointer by one step
fast = fast->next->next; // Move fast pointer by two steps
if (slow == fast) { // Cycle detected
return 1;
}
}
return 0; // No cycle detected
}
// Utility function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
int main() {
// Creating a linked list with a cycle: 1->2->3->4->2 (cycle)
struct Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = head->next; // Creating a cycle
if (detectCycle(head))
printf("Cycle detected\n");
else
printf("No cycle detected\n");
return 0;
}
3. Merge Two Sorted Single Linked Lists
#include <stdio.h>
#include <stdlib.h>
// Definition for the singly linked list node
struct Node {
int data;
struct Node* next;
};
// Function to merge two sorted linked lists
struct Node* mergeLists(struct Node* l1, struct Node* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
struct Node* result = NULL;
// Choose either l1 or l2, and recursively merge the remaining lists
if (l1->data <= l2->data) {
result = l1;
result->next = mergeLists(l1->next, l2);
} else {
result = l2;
result->next = mergeLists(l1, l2->next);
}
return result;
}
// Utility function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
// Utility function to print the list
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
// Creating two sorted lists: 1->3->5->NULL and 2->4->6->NULL
struct Node* l1 = newNode(1);
l1->next = newNode(3);
l1->next->next = newNode(5);
struct Node* l2 = newNode(2);
l2->next = newNode(4);
l2->next->next = newNode(6);
printf("List 1: ");
printList(l1);
printf("List 2: ");
printList(l2);
struct Node* mergedList = mergeLists(l1, l2);
printf("Merged List: ");
printList(mergedList);
return 0;
}
4. Find the Middle of a Single Linked List
#include <stdio.h>
#include <stdlib.h>
// Definition for the singly linked list node
struct Node {
int data;
struct Node* next;
};
// Function to find the middle of the linked list
struct Node* findMiddle(struct Node* head) {
struct Node* slow = head;
struct Node* fast = head;
// Move fast pointer by 2 steps and slow by 1 step
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow; // Slow pointer is now at the middle
}
// Utility function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
// Utility function to print the list
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
// Creating a simple linked list 1->2->3->4->5->NULL
struct Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
printf("List: ");
printList(head);
struct Node* middle = findMiddle(head);
if (middle != NULL)
printf("Middle element is %d\n", middle->data);
return 0;
}
5. Convert a Single Linked List into a Circular Linked List
#include <stdio.h>
#include <stdlib.h>
// Definition for the singly linked list node
struct Node {
int data;
struct Node* next;
};
// Function to convert a singly linked list into a circular linked list
void convertToCircular(struct Node* head) {
if (head == NULL) return;
struct Node* temp = head;
// Traverse the list till the last node
while (temp->next != NULL) {
temp = temp->next;
}
// Link the last node to the first node
temp->next = head;
}
// Utility function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
// Utility function to print the list (for circular, stops at the starting node)
void printCircularList(struct Node* head) {
if (head == NULL) return;
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(back to start)\n");
}
int main() {
// Creating a simple linked list 1->2->3->4->NULL
struct Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
printf("Original List: ");
printCircularList(head);
convertToCircular(head);
printf("Circular List: ");
printCircularList(head);
return 0;
}