Linked Lists
Contents
Define, declare, and classify the Linked List 1
Recall need of the Linked List 2
Recall Merits and Demerits of the Linked List 3
Differentiate between Array and Linked List 4
Create and display a singly linked list 6
Create and display a singly circular linked list 6
Recall the limitations of singly linked and singly circular linked list 6
Perform the following operation with the Singly Linked List: Insertion of an element 6
Create a Doubly Circular Linked List 6
Recall the concept of Generalized Linked List 6
Describe the concept of Linked List with Header Node 6
Define Linked List representation of a Polynomial 6
Write a Program in C for the Addition of two Polynomials 6
Define, declare, and classify the Linked List
A linked list is a data structure that consists of a sequence of nodes, where each node contains a data element and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation and can dynamically grow or shrink in size.
Here are the key components of a linked list:
- Node: Each node in a linked list contains two parts: data and a link/reference to the next node. The data part stores the actual value or information of the node, and the link part holds the memory address of the next node in the sequence.
- Head: The head is the first node in the linked list. It serves as the starting point and allows traversal through the list.
- Tail: The tail is the last node in the linked list. It points to NULL or contains a special marker to indicate the end of the list.
Linked lists can be classified into different types based on their properties and functionalities:
- Singly Linked List: In a singly linked list, each node has a reference to the next node in the sequence. It allows traversal only in the forward direction.
- Doubly Linked List: In a doubly linked list, each node has references to both the next node and the previous node. It enables traversal in both forward and backward directions, offering more flexibility but requiring additional memory for the previous pointers.
- Circular Linked List: In a circular linked list, the last node’s link points back to the first node, forming a circular structure. It allows traversal throughout the list endlessly.
Linked lists are useful when you need dynamic memory allocation, frequent insertions/deletions, or a flexible data structure that can grow or shrink dynamically. However, they require more memory overhead due to the additional references compared to arrays. The choice of linked list type depends on the specific requirements of the problem you are trying to solve.
Recall need of the Linked List
Linked lists are useful in various scenarios where dynamic memory allocation, efficient insertions and deletions, or flexibility in data structure size are required.
Here are some common situations where linked lists are beneficial:
- Dynamic Size: Linked lists allow for dynamic memory allocation, which means they can grow or shrink as needed. Unlike arrays, which have a fixed size, linked lists can expand or contract by simply creating or removing nodes. This feature is particularly useful when the size of the data is unknown or can change over time.
- Efficient Insertions and Deletions: Linked lists excel in performing insertions and deletions at any position within the list. Unlike arrays, where inserting or deleting an element requires shifting the existing elements, linked lists can insert or delete nodes by updating the appropriate pointers. This results in faster and more efficient operations, especially for large lists.
- Memory Efficiency: Linked lists offer memory efficiency in terms of allocation. Each node in a linked list only requires memory for the data element and the reference to the next node, whereas arrays allocate contiguous memory for all elements, regardless of whether they are used or not. This allows linked lists to optimize memory usage and allocate memory dynamically as needed.
- Flexibility: Linked lists provide flexibility in terms of data structure. With linked lists, you can easily rearrange, insert, or delete elements without affecting the overall structure. This flexibility is valuable in scenarios where the order or positioning of elements is subject to change.
- Circular or Self-referential Structures: Linked lists can be easily used to create circular or self-referential structures, where the last node points back to the first node or a node refers to itself. Circular linked lists are useful in applications that require cyclic or repetitive behavior, such as scheduling algorithms or circular buffers.
- Separate Memory Allocation: Linked lists allow for separate memory allocation for each node, which can be advantageous in situations where memory blocks of different sizes need to be managed independently.
Overall, the linked list data structure provides a range of advantages in terms of dynamic memory allocation, efficient insertions/deletions, memory efficiency, flexibility, and support for circular structures. These benefits make linked lists a powerful tool in many programming scenarios.
Recall Merits and Demerits of the Linked List
Linked lists have both merits and demerits. Let’s discuss them:
Merits of Linked List:
- Dynamic Size: Linked lists can grow or shrink dynamically as elements are added or removed. This flexibility makes them suitable for situations where the size of the data structure needs to change dynamically.
- Efficient Insertions and Deletions: Insertions and deletions in linked lists are efficient, especially when working with large lists, as they involve updating pointers rather than shifting elements. Adding or removing an element at the beginning or end of the list can be done in constant time.
- Memory Efficiency: Linked lists utilize memory efficiently by allocating memory for each element individually. This eliminates the need for contiguous memory allocation, allowing efficient utilization of available memory.
- Flexibility: Linked lists offer flexibility in terms of data structure manipulation. Elements can be easily rearranged, inserted, or removed without affecting the overall structure of the list.
- Dynamic Memory Allocation: Linked lists allow for dynamic memory allocation, which means memory can be allocated as needed. This is particularly useful when the size of the data structure is unknown or varies during runtime.
Demerits of Linked List:
- Sequential Access: Unlike arrays, which provide direct access to any element through indexing, linked lists require sequential access. Traversing a linked list to access a specific element takes linear time, which can be inefficient for certain operations.
- Extra Memory Overhead: Linked lists require additional memory space for storing the pointers/references to the next node, resulting in higher memory overhead compared to arrays.
- No Random Access: Linked lists do not support random access to elements. To access an element, you need to traverse the list from the beginning until the desired position is reached. This can be a drawback if frequent random access is required.
- Inefficient Memory Utilization: Linked lists can suffer from inefficient memory utilization due to the need for separate memory allocations for each node. This overhead can be significant when dealing with large numbers of small-sized elements.
- Lack of Cache Locality: Linked lists do not exhibit good cache locality since nodes are scattered in memory. This can lead to increased cache misses and slower performance compared to arrays.
It’s important to consider these merits and demerits when choosing the appropriate data structure for a specific problem. While linked lists offer advantages in terms of flexibility and efficient insertions/deletions, they may not be the optimal choice in scenarios that require frequent random access or demand high memory efficiency.
Differentiate between Array and Linked List
Here’s a comparison between arrays and linked lists in tabular form:
| Array | Linked List | |
| Memory Allocation | Contiguous memory allocation | Dynamic memory allocation |
| Size Flexibility | Fixed size | Dynamic size |
| Insertions/Deletions | Inefficient for insertions/deletions at arbitrary positions as it requires shifting elements | Efficient insertions/deletions at any position without shifting elements |
| Random Access | Supports random access to elements using indices | Sequential access, requires traversal to access elements |
| Memory Overhead | Low memory overhead | Higher memory overhead due to pointers/references |
| Memory Utilization | May have inefficient memory utilization when dealing with large numbers of small-sized elements | Efficient memory utilization |
| Cache Locality | Good cache locality, elements are stored together in memory | Poor cache locality, nodes are scattered in memory |
| Memory Access Pattern | Direct access to elements using indexing | Sequential access pattern, traversal through nodes |
| Complexity | Constant time complexity for element access and modification | Linear time complexity for element access and modification |
| Implementation | Fixed-size, predetermined structure | Dynamic structure that can grow or shrink |
It’s important to note that the choice between an array and a linked list depends on the specific requirements of the problem. Arrays are more suitable for scenarios where random access and efficient memory utilization are important, while linked lists excel in dynamic size, efficient insertions/deletions, and flexibility.
Create and display a singly linked list
A singly linked list is a linear data structure in which each node contains an element of the list and a pointer to the next node in the list. To create a singly linked list, one needs to start by defining a class or structure to represent the nodes in the list. This class or structure should contain two data members, one to store the element and another to store the pointer to the next node in the list. To create a singly linked list, one needs to create a set of nodes and connect them by updating the pointers in each node to point to the next node in the list. Once the linked list is created, one can display its elements by traversing the list from the first node and printing the element stored in each node.
Here’s an example C program to create and display a singly linked list:
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a node in the linked list
struct Node {
int data;
struct Node* next;
};
// 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 display the linked list
void displayLinkedList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“\n”);
}
int main() {
// Create nodes for the linked list
struct Node* head = createNode(1);
struct Node* second = createNode(2);
struct Node* third = createNode(3);
// Link the nodes together
head->next = second;
second->next = third;
// Display the linked list
printf(“Linked List: “);
displayLinkedList(head);
// Free the allocated memory
free(head);
free(second);
free(third);
return 0;
}
In this program, we define a structure Node that represents a node in the linked list. The structure has two members: data to store the data value and next to store the reference to the next node.
The createNode function is used to dynamically allocate memory for a new node, assign the given data to it, and initialize the next pointer to NULL.
The displayLinkedList function takes the head of the linked list as input and traverses the list, printing the data of each node.
In the main function, we create three nodes and link them together by assigning the next pointers accordingly. Finally, we call the displayLinkedList function to display the elements of the linked list.
Remember to free the allocated memory at the end of the program to avoid memory leaks.
Create and display a singly circular linked list
A singly circular linked list is a type of linked list in which the last node points back to the first node, creating a circular arrangement of nodes. To create a singly circular linked list, one needs to create a set of nodes and connect them as in a singly linked list. The difference is that the pointer in the last node should be updated to point to the first node instead of null. Once the linked list is created, one can display its elements by traversing the list from the first node and printing the element stored in each node. One should keep track of the last node visited to stop the traversal when it reaches the first node again.
Here’s an example C program to create and display a singly circular linked list:
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a node in the linked list
struct Node {
int data;
struct Node* next;
};
// 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 display the linked list
void displayLinkedList(struct Node* head) {
struct Node* temp = head;
if (head != NULL) {
do {
printf(“%d “, temp->data);
temp = temp->next;
} while (temp != head);
}
printf(“\n”);
}
int main() {
// Create nodes for the linked list
struct Node* head = createNode(1);
struct Node* second = createNode(2);
struct Node* third = createNode(3);
// Link the nodes together to form a circular list
head->next = second;
second->next = third;
third->next = head;
// Display the circular linked list
printf(“Circular Linked List: “);
displayLinkedList(head);
// Free the allocated memory
free(head);
free(second);
free(third);
return 0;
}
In this program, we define a structure Node that represents a node in the circular linked list. The structure has two members: data to store the data value and next to store the reference to the next node.
The createNode function is used to dynamically allocate memory for a new node, assign the given data to it, and initialize the next pointer to NULL.
The displayLinkedList function takes the head of the circular linked list as input and traverses the list in a circular manner. It prints the data of each node until it reaches the head node again.
In the main function, we create three nodes and link them together to form a circular list by assigning the next pointers accordingly. Finally, we call the displayLinkedList function to display the elements of the circular linked list.
Remember to free the allocated memory at the end of the program to avoid memory leaks.
Recall the limitations of singly linked and singly circular linked list
The limitations of singly linked lists and singly circular linked lists include:
- Limited Access: Singly linked lists and singly circular linked lists do not support direct access to elements based on their indices. To access an element, you need to traverse the list from the beginning until the desired position is reached. This can result in slower performance when frequent random access is required.
- Memory Overhead: Linked lists require additional memory overhead compared to arrays. Each node in the list requires memory for the data element and a pointer/reference to the next node. This overhead can be significant, especially for large lists.
- Lack of Reverse Traversal: Singly linked lists and singly circular linked lists do not support reverse traversal. Since each node only has a reference to the next node, it is not possible to traverse the list in reverse order without additional modifications or data structures.
- Lack of Memory Locality: Linked lists do not exhibit good cache locality since nodes are scattered in memory. This can result in increased cache misses and slower performance compared to arrays, where elements are stored contiguously.
- Insertion and Deletion at Arbitrary Positions: While insertion and deletion at the beginning or end of the list are efficient, performing these operations at arbitrary positions can be inefficient. It requires traversing the list to find the desired position, resulting in linear time complexity.
- Extra Pointer Overhead in Circular Linked Lists: Singly circular linked lists require an extra pointer/reference in each node to maintain the circular connection. This increases the memory overhead compared to singly linked lists.
- Sequential Access Pattern: Singly linked lists and singly circular linked lists have a sequential access pattern, requiring traversal from one node to the next. This can be inefficient for certain operations that require frequent access to arbitrary elements.
It’s important to consider these limitations when choosing a data structure for a specific problem. While linked lists offer advantages such as dynamic size and efficient insertions/deletions, they may not be the optimal choice in scenarios that require frequent random access or have strict memory constraints.
Perform the following operation with the Singly Linked List: Insertion of an element
Here’s an example of C functions to perform insertion of an element in the beginning, end, and at a given position in a singly linked list:
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a node in the linked list
struct Node {
int data;
struct Node* next;
};
// 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 insert a new node at the beginning of the linked list
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
// Function to insert a new node at the end of the linked list
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
// Function to insert a new node at a given position in the linked list
void insertAtPosition(struct Node** head, int data, int position) {
struct Node* newNode = createNode(data);
if (position == 1) {
newNode->next = *head;
*head = newNode;
} else {
struct Node* temp = *head;
for (int i = 1; i < position – 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf(“Invalid position\n”);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
}
// Function to display the linked list
void displayLinkedList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“\n”);
}
int main() {
struct Node* head = NULL;
// Insert elements into the linked list
insertAtBeginning(&head, 2); // Insert 2 at the beginning
insertAtEnd(&head, 4); // Insert 4 at the end
insertAtPosition(&head, 3, 2); // Insert 3 at position 2
// Display the linked list
printf(“Linked List: “);
displayLinkedList(head);
// Free the allocated memory
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}
In this program, we define a structure Node that represents a node in the singly linked list. The structure has two members: data to store the data value and next to store the reference to the next node.
The createNode function is used to dynamically allocate memory for a new node, assign the given data to it, and initialize the next pointer to NULL.
The insertAtBeginning function inserts a new node at the beginning of the linked list. It creates a new node, assigns the given data to it, and updates the next pointer of the new node to point to the current head of the list. Finally, it updates the head pointer to the new node.
The insertAtEnd function inserts a new node at the end of the linked list. It creates a new node, assigns the given data to it, and traverses the list until the last node is reached. Then, it updates the next pointer of the last node to point to the new node.
The insertAtPosition function inserts a new node at a given position in the linked list. If the position is 1, it calls the insertAtBeginning function to insert the node at the beginning. Otherwise, it traverses the list to the position just before the desired position, creates a new node, and updates the next pointers accordingly.
The displayLinkedList function takes the head of the linked list as input and traverses the list, printing the data of each node.
In the main function, we declare the head pointer as NULL to indicate an empty list. We then call the insertAtBeginning, insertAtEnd, and insertAtPosition functions to insert elements into the linked list. Finally, we display the linked list and free the allocated memory.
Perform the following operations with the Singly Linked List: Deletion, and count the number of elements
Here’s an example of C functions to perform deletion from the beginning, end, and at a given position in a singly linked list:
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a node in the linked list
struct Node {
int data;
struct Node* next;
};
// 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 insert a new node at the beginning of the linked list
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
// Function to delete the first node from the linked list
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“Linked list is empty\n”);
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
// Function to delete the last node from the linked list
void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf(“Linked list is empty\n”);
return;
}
if ((*head)->next == NULL) {
free(*head);
*head = NULL;
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
prev->next = NULL;
free(temp);
}
// Function to delete a node at a given position from the linked list
void deleteFromPosition(struct Node** head, int position) {
if (*head == NULL) {
printf(“Linked list is empty\n”);
return;
}
if (position == 1) {
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
int count = 1;
while (temp != NULL && count < position) {
prev = temp;
temp = temp->next;
count++;
}
if (temp == NULL) {
printf(“Invalid position\n”);
return;
}
prev->next = temp->next;
free(temp);
}
// Function to display the linked list
void displayLinkedList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“\n”);
}
int main() {
struct Node* head = NULL;
// Insert elements into the linked list
insertAtBeginning(&head, 3); // Insert 3 at the beginning
insertAtBeginning(&head, 2); // Insert 2 at the beginning
insertAtBeginning(&head, 1); // Insert 1 at the beginning
// Display the linked list
printf(“Linked List: “);
displayLinkedList(head);
// Delete elements from the linked list
deleteFromBeginning(&head); // Delete from the beginning
deleteFromEnd(&head); // Delete from the end
deleteFromPosition(&head, 2); // Delete from position 2
// Display the modified linked list
printf(“Modified Linked List: “);
displayLinkedList(head);
// Free the allocated memory
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}
In this program, we have the same structure and functions for creating nodes, inserting at the beginning, and displaying the linked list as we did in the previous example.
The deleteFromBeginning function deletes the first node from the linked list. It checks if the list is empty and if not, updates the head pointer to the next node and frees the memory of the deleted node.
The deleteFromEnd function deletes the last node from the linked list. It handles two cases: when the list is empty and when it contains only one node. If there are more than one nodes, it traverses the list until the last node and updates the next pointer of the second-last node to NULL. Finally, it frees the memory of the deleted node.
The deleteFromPosition function deletes a node at a given position in the linked list. It handles two cases: when the position is the first node and when it is any other position. If the position is the first node, it updates the head pointer to the next node and frees the memory of the deleted node. Otherwise, it traverses the list to the position just before the desired position and updates the next pointer of the previous node to skip the node to be deleted. Finally, it frees the memory of the deleted node.
In the main function, we first insert elements into the linked list using the insertAtBeginning function. Then, we display the original linked list.
After that, we call the deletion functions deleteFromBeginning, deleteFromEnd, and deleteFromPosition to delete elements from the linked list. Finally, we display the modified linked list and free the allocated memory.
Here are C functions to count the number of nodes in a singly linked list and a singly circular linked list:
For a singly linked list:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// 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 count the number of nodes in a singly linked list
int countNodes(struct Node* head) {
int count = 0;
struct Node* temp = head;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}
// Function to display the linked list
void displayLinkedList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“\n”);
}
int main() {
struct Node* head = NULL;
// Create a singly linked list
head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = createNode(5);
// Display the linked list
printf(“Linked List: “);
displayLinkedList(head);
// Count the number of nodes
int count = countNodes(head);
printf(“Number of nodes: %d\n”, count);
// Free the allocated memory
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}
For a singly circular linked list:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// 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 count the number of nodes in a singly circular linked list
int countNodes(struct Node* head) {
if (head == NULL) {
return 0;
}
int count = 1;
struct Node* current = head->next;
while (current != head) {
count++;
current = current->next;
}
return count;
}
// Function to display the linked list
void displayLinkedList(struct Node* head) {
struct Node* current = head;
if (head == NULL) {
printf(“Empty List\n”);
return;
}
do {
printf(“%d “, current->data);
current = current->next;
} while (current != head);
printf(“\n”);
}
int main() {
struct Node* head = NULL;
// Create a singly circular linked list
head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = createNode(5);
head->next->next->next->next->next = head;
// Display the linked list
printf(“Linked List: “);
displayLinkedList(head);
// Count the number of nodes
int count = countNodes(head);
printf(“Number of nodes: %d\n”, count);
// Free the allocated memory
struct Node* temp;
struct Node* current = head->next;
while (current != head) {
temp = current;
current = current->next;
free(temp);
}
free(head);
return 0;
}
In both examples, we have a structure called Node to represent a node in the linked list. The createNode function creates a new node and returns a pointer to it.
For the singly linked list example, we have the countNodes function that takes the head of the linked list as input and counts the number of nodes by traversing the list using a temp pointer. The displayLinkedList function is used to print the elements of the linked list.
In the main function, we create a singly linked list by creating nodes and linking them together. Then, we display the linked list and call the countNodes function to count the number of nodes. Finally, we free the allocated memory using a temp pointer to traverse the list and free each node.
For the singly circular linked list example, the countNodes function is similar, but it handles the case where the head is NULL and the circular linking of nodes is done by setting the next pointer of the last node to the head. The displayLinkedList function is modified to handle the circular nature of the list by using a do-while loop to print the elements.
In the main function, we create a singly circular linked list, display it, count the number of nodes, and then free the memory by traversing the list and freeing each node.
Create a Doubly Linked List
A Doubly Linked List is a type of linked list that contains a pointer to both the next and the previous node in the list. This type of linked list allows for bi-directional traversal, making it easier to traverse the list in both directions and to perform operations like deletion and insertion at both the beginning and end of the list.
Here’s an example of a Doubly Linked List implementation in C:
#include <stdio.h>
#include <stdlib.h>
// Node structure
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
// Doubly Linked List structure
typedef struct DoublyLinkedList {
Node* head;
Node* tail;
} DoublyLinkedList;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to initialize a Doubly Linked List
DoublyLinkedList* initializeList() {
DoublyLinkedList* newList = (DoublyLinkedList*)malloc(sizeof(DoublyLinkedList));
newList->head = NULL;
newList->tail = NULL;
return newList;
}
// Function to insert a node at the beginning of the list
void insertAtBeginning(DoublyLinkedList* list, int data) {
Node* newNode = createNode(data);
if (list->head == NULL) {
list->head = newNode;
list->tail = newNode;
} else {
newNode->next = list->head;
list->head->prev = newNode;
list->head = newNode;
}
}
// Function to insert a node at the end of the list
void insertAtEnd(DoublyLinkedList* list, int data) {
Node* newNode = createNode(data);
if (list->tail == NULL) {
list->head = newNode;
list->tail = newNode;
} else {
newNode->prev = list->tail;
list->tail->next = newNode;
list->tail = newNode;
}
}
// Function to display the elements of the list
void displayList(DoublyLinkedList* list) {
if (list->head == NULL) {
printf(“List is empty.\n”);
return;
}
Node* current = list->head;
printf(“Doubly Linked List: “);
while (current != NULL) {
printf(“%d “, current->data);
current = current->next;
}
printf(“\n”);
}
int main() {
DoublyLinkedList* list = initializeList();
// Inserting elements
insertAtBeginning(list, 10);
insertAtBeginning(list, 20);
insertAtEnd(list, 30);
insertAtEnd(list, 40);
// Displaying the list
displayList(list);
return 0;
}
This program creates a Doubly Linked List and demonstrates the insertion of nodes at the beginning and end of the list. Finally, it displays the elements of the list. You can modify the main function to perform other operations on the Doubly Linked List as needed.
Create a Doubly Circular Linked List
A Doubly Circular Linked List is similar to a Doubly Linked List, but it has a circular structure where the last node in the list points back to the first node, and the first node points to the last node. This type of linked list allows for bi-directional traversal without the need for null pointers, making it easier to traverse the list and perform operations.
Here’s an example of a C program to create and display a doubly circular linked list:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a new node at the beginning of the doubly circular linked list
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
newNode->prev = newNode;
newNode->next = newNode;
} else {
newNode->prev = (*head)->prev;
newNode->next = *head;
(*head)->prev->next = newNode;
(*head)->prev = newNode;
}
*head = newNode;
}
// Function to display the doubly circular linked list
void displayLinkedList(struct Node* head) {
if (head == NULL) {
printf(“Empty List\n”);
return;
}
struct Node* current = head;
do {
printf(“%d “, current->data);
current = current->next;
} while (current != head);
printf(“\n”);
}
int main() {
struct Node* head = NULL;
// Insert elements into the doubly circular linked list
insertAtBeginning(&head, 5); // Insert 5 at the beginning
insertAtBeginning(&head, 4); // Insert 4 at the beginning
insertAtBeginning(&head, 3); // Insert 3 at the beginning
insertAtBeginning(&head, 2); // Insert 2 at the beginning
insertAtBeginning(&head, 1); // Insert 1 at the beginning
// Display the doubly circular linked list
printf(“Doubly Circular Linked List: “);
displayLinkedList(head);
// Free the allocated memory
if (head != NULL) {
struct Node* temp = head->next;
while (temp != head) {
struct Node* current = temp;
temp = temp->next;
free(current);
}
free(head);
}
return 0;
}
In this program, we have a structure called Node to represent a node in the doubly circular linked list. The createNode function creates a new node and returns a pointer to it.
The insertAtBeginning function is used to insert a new node at the beginning of the doubly circular linked list. It handles two cases: when the list is empty and when it is not. In the case of an empty list, the prev and next pointers of the new node are set to point to itself. Otherwise, the prev pointer of the new node is set to the prev pointer of the head node, and the next pointer is set to the head node. Additionally, the prev and next pointers of the adjacent nodes are updated to maintain the circular linking. Finally, the head pointer is updated to point to the new node.
The displayLinkedList function is used to print the elements of the doubly circular linked list. It starts from the head node and iterates through the list using a do-while loop, printing the data of each node until it reaches the head again.
In the main function, we create a doubly circular linked list by inserting nodes at the beginning using the insertAtBeginning function. Then, we display the linked list using the displayLinkedList function. Finally, we free the allocated memory by traversing the list and freeing each node.
Perform the following operations with the Doubly and Doubly Circular Linked List: i. Insertion of an element
Here are C functions to perform the insertion of an element in the beginning, end, and at a given position for both Doubly Linked List and Doubly Circular Linked List:
For Doubly Linked List:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a new node at the beginning of the doubly linked list
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
// Function to insert a new node at the end of the doubly linked list
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
// Function to insert a new node at a given position in the doubly linked list
void insertAtPosition(struct Node** head, int data, int position) {
if (position <= 0) {
insertAtBeginning(head, data);
} else {
struct Node* newNode = createNode(data);
struct Node* temp = *head;
int count = 1;
while (temp != NULL && count < position) {
temp = temp->next;
count++;
}
if (temp != NULL) {
newNode->next = temp->next;
if (temp->next != NULL) {
temp->next->prev = newNode;
}
newNode->prev = temp;
temp->next = newNode;
} else {
printf(“Invalid position!\n”);
}
}
}
// Function to display the doubly linked list
void displayDoublyLinkedList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“\n”);
}
int main() {
struct Node* head = NULL;
// Insert elements into the doubly linked list
insertAtBeginning(&head, 1); // Insert 1 at the beginning
insertAtEnd(&head, 3); // Insert 3 at the end
insertAtPosition(&head, 2, 1); // Insert 2 at position 1
// Display the doubly linked list
printf(“Doubly Linked List: “);
displayDoublyLinkedList(head);
// Free the allocated memory
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}
For Doubly Circular Linked List:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a new node at the beginning of the doubly circular linked list
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
newNode->prev = newNode;
newNode->next = newNode;
} else {
newNode->prev = (*head)->prev;
newNode->next = *head;
(*head)->prev->next = newNode;
(*head)->prev = newNode;
}
*head = newNode;
}
// Function to insert a new node at the end of the doubly circular linked list
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
newNode->prev = newNode;
newNode->next = newNode;
*head = newNode;
} else {
newNode->prev = (*head)->prev;
newNode->next = *head;
(*head)->prev->next = newNode;
(*head)->prev = newNode;
}
}
// Function to insert a new node at a given position in the doubly circular linked list
void insertAtPosition(struct Node** head, int data, int position) {
if (position <= 0) {
insertAtBeginning(head, data);
} else {
struct Node* newNode = createNode(data);
struct Node* temp = *head;
int count = 1;
while (temp->next != *head && count < position) {
temp = temp->next;
count++;
}
newNode->prev = temp;
newNode->next = temp->next;
temp->next->prev = newNode;
temp->next = newNode;
}
}
// Function to display the doubly circular linked list
void displayDoublyCircularLinkedList(struct Node* head) {
if (head == NULL) {
printf(“Empty List\n”);
return;
}
struct Node* temp = head;
do {
printf(“%d “, temp->data);
temp = temp->next;
} while (temp != head);
printf(“\n”);
}
int main() {
struct Node* head = NULL;
// Insert elements into the doubly circular linked list
insertAtBeginning(&head, 1); // Insert 1 at the beginning
insertAtEnd(&head, 3); // Insert 3 at the end
insertAtPosition(&head, 2, 1); // Insert 2 at position 1
// Display the doubly circular linked list
printf(“Doubly Circular Linked List: “);
displayDoublyCircularLinkedList(head);
// Free the allocated memory
struct Node* temp;
if (head != NULL) {
temp = head->next;
while (temp != head) {
struct Node* current = temp;
temp = temp->next;
free(current);
}
free(head);
}
return 0;
}
In both examples, we have a structure called Node to represent a node in the linked list. The createNode function creates a new node and returns a pointer to it.
For the Doubly Linked List example, we have the insertAtBeginning function to insert a new node at the beginning, the insertAtEnd function to insert a new node at the end, and the insertAtPosition function to insert a new node at a given position.
For the Doubly Circular Linked List example, we have the same three functions (insertAtBeginning, insertAtEnd, and insertAtPosition), but with slight modifications to handle the circular nature of the list. The displayDoublyCircularLinkedList function is used to display the elements of the circular linked list.
Remember to free the allocated memory after performing the operations to avoid memory leaks.
Perform the following operations with the Doubly and Doubly Circular Linked List: ii. Deletion of an element
Here are the C functions to perform the deletion of an element from the beginning, end, and at a given position for both Doubly Linked List and Doubly Circular Linked List:
For Doubly Linked List:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a new node at the beginning of the doubly linked list
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
// Function to insert a new node at the end of the doubly linked list
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
// Function to delete the first node from the doubly linked list
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“List is empty!\n”);
} else {
struct Node* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}
}
// Function to delete the last node from the doubly linked list
void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf(“List is empty!\n”);
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
if (temp->prev != NULL) {
temp->prev->next = NULL;
} else {
*head = NULL;
}
free(temp);
}
}
// Function to delete a node from the doubly linked list at a given position
void deleteFromPosition(struct Node** head, int position) {
if (*head == NULL) {
printf(“List is empty!\n”);
} else {
struct Node* temp = *head;
int count = 1;
while (temp != NULL && count < position) {
temp = temp->next;
count++;
}
if (temp != NULL) {
if (temp->prev != NULL) {
temp->prev->next = temp->next;
} else {
*head = temp->next;
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
free(temp);
} else {
printf(“Invalid position!\n”);
}
}
}
// Function to display the doubly linked list
void displayDoublyLinkedList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“\n”);
}
int main() {
struct Node* head = NULL;
// Insert elements into the doubly linked list
insertAtEnd(&head, 1); // Insert 1 at the end
insertAtEnd(&head, 2); // Insert 2 at the end
insertAtEnd(&head, 3); // Insert 3 at the end
// Display the doubly linked list
printf(“Doubly Linked List: “);
displayDoublyLinkedList(head);
// Delete elements from the doubly linked list
deleteFromBeginning(&head); // Delete from the beginning
deleteFromEnd(&head); // Delete from the end
deleteFromPosition(&head, 1); // Delete from position 1
// Display the modified doubly linked list
printf(“Modified Doubly Linked List: “);
displayDoublyLinkedList(head);
// Free the allocated memory
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}
For Doubly Circular Linked List:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a new node at the beginning of the doubly circular linked list
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
(*head)->prev = *head;
(*head)->next = *head;
} else {
newNode->next = *head;
newNode->prev = (*head)->prev;
(*head)->prev->next = newNode;
(*head)->prev = newNode;
*head = newNode;
}
}
// Function to insert a new node at the end of the doubly circular linked list
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
(*head)->prev = *head;
(*head)->next = *head;
} else {
newNode->next = *head;
newNode->prev = (*head)->prev;
(*head)->prev->next = newNode;
(*head)->prev = newNode;
}
}
// Function to delete the first node from the doubly circular linked list
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“List is empty!\n”);
} else {
struct Node* temp = *head;
if ((*head)->next == *head) {
*head = NULL;
} else {
(*head)->prev->next = (*head)->next;
(*head)->next->prev = (*head)->prev;
*head = (*head)->next;
}
free(temp);
}
}
// Function to delete the last node from the doubly circular linked list
void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf(“List is empty!\n”);
} else {
struct Node* temp = (*head)->prev;
if ((*head)->next == *head) {
*head = NULL;
} else {
temp->prev->next = *head;
(*head)->prev = temp->prev;
}
free(temp);
}
}
// Function to delete a node from the doubly circular linked list at a given position
void deleteFromPosition(struct Node** head, int position) {
if (*head == NULL) {
printf(“List is empty!\n”);
} else {
struct Node* temp = *head;
int count = 1;
while (temp != NULL && count < position) {
temp = temp->next;
count++;
}
if (temp != NULL) {
if (temp == *head) {
deleteFromBeginning(head);
} else if (temp->next == *head) {
deleteFromEnd(head);
} else {
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
}
} else {
printf(“Invalid position!\n”);
}
}
}
// Function to display the doubly circular linked list
void displayDoublyCircularLinkedList(struct Node* head) {
if (head == NULL) {
printf(“List is empty!\n”);
} else {
struct Node* temp = head;
do {
printf(“%d “, temp->data);
temp = temp->next;
} while (temp != head);
printf(“\n”);
}
}
int main() {
struct Node* head = NULL;
// Insert elements into the doubly circular linked list
insertAtEnd(&head, 1); // Insert 1 at the end
insertAtEnd(&head, 2); // Insert 2 at the end
insertAtEnd(&head, 3); // Insert 3 at the end
// Display the doubly circular linked list
printf(“Doubly Circular Linked List: “);
displayDoublyCircularLinkedList(head);
// Delete elements from the doubly circular linked list
deleteFromBeginning(&head); // Delete from the beginning
deleteFromEnd(&head); // Delete from the end
deleteFromPosition(&head, 1); // Delete from position 1
// Display the modified doubly circular linked list
printf(“Modified Doubly Circular Linked List: “);
displayDoublyCircularLinkedList(head);
// Free the allocated memory
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}
These programs demonstrate thedeletion operations on both Doubly Linked List and Doubly Circular Linked List. You can modify them according to your requirements and test them to see the results.
Perform the following operations with the Doubly and Doubly Circular Linked List: iii. Count the number of nodes
Here are the C functions to count the number of nodes in a Doubly Linked List and Doubly Circular Linked List:
For Doubly Linked List:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a new node at the beginning of the doubly linked list
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
// Function to count the number of nodes in the doubly linked list
int countNodes(struct Node* head) {
int count = 0;
struct Node* temp = head;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}
// Function to display the doubly linked list
void displayDoublyLinkedList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“\n”);
}
int main() {
struct Node* head = NULL;
// Insert elements into the doubly linked list
insertAtBeginning(&head, 1);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 3);
// Display the doubly linked list
printf(“Doubly Linked List: “);
displayDoublyLinkedList(head);
// Count the number of nodes in the doubly linked list
int count = countNodes(head);
printf(“Number of nodes: %d\n”, count);
// Free the allocated memory
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}
For Doubly Circular Linked List:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a new node at the beginning of the doubly circular linked list
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
(*head)->prev = *head;
(*head)->next = *head;
} else {
newNode->next = *head;
newNode->prev = (*head)->prev;
(*head)->prev->next = newNode;
(*head)->prev = newNode;
*head = newNode;
}
}
// Function to count the number of nodes in the doubly circular linked list
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;
}
// Function to display the doubly circular linked list
void displayDoublyCircularLinkedList(struct Node* head) {
if (head == NULL) {
printf(“List is empty!\n”);
} else {
struct Node* temp = head;
do {
printf(“%d “, temp->data);
temp = temp->next;
} while (temp != head);
printf(“\n”);
}
}
int main() {
struct Node* head = NULL;
// Insert elements into the doubly circular linked list
insertAtBeginning(&head, 1);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 3);
// Display the doubly circular linked list
printf(“Doubly Circular Linked List: “);
displayDoublyCircularLinkedList(head);
// Count the number of nodes in the doubly circular linked list
int count = countNodes(head);
printf(“Number of nodes: %d\n”, count);
// Free the allocated memory
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
if (head != NULL) {
head->prev = temp->prev;
temp->prev->next = head;
}
free(temp);
}
return 0;
}
These programs demonstrate the count operations on both Doubly Linked List and Doubly Circular Linked List, along with the counting of nodes. You can modify them according to your requirements and test them to see the results.
Recall the concept of Generalized Linked List
A Generalized Linked List is a data structure that allows different data types to be stored in its nodes. Unlike a traditional linked list, where each node contains a single data element, a generalized linked list can store various types of data elements in its nodes.
In a generalized linked list, each node contains two fields: a tag field and a union field. The tag field is used to identify the type of data stored in the node, while the union field is a variant field that can hold different types of data based on the tag value.
The tag field typically takes on values such as 0 or 1 to represent different types of data. For example, a tag value of 0 might indicate that the node contains an integer value, while a tag value of 1 might indicate that the node contains a character value. The union field is then used to store the actual data based on the tag value.
The structure of a generalized linked list can be defined using a C struct as follows:
struct Node {
int tag; // tag field to identify the type of data
union {
int intValue; // integer value
char charValue; // character value
float floatValue; // float value
// other data types as needed
} data; // union field to store different types of data
struct Node* next; // pointer to the next node in the list
};
With a generalized linked list, you can store and manipulate different types of data in a single list. It provides flexibility in representing complex data structures and is often used in scenarios where the data elements vary in type or structure.
Describe the concept of Linked List with Header Node
A Linked List with a Header Node, also known as a Sentinel Node or a Dummy Node, is a variation of the traditional linked list data structure. In this variation, an additional node called the header node is added at the beginning of the list. The header node does not contain any actual data but serves as a dummy node to provide several advantages in the implementation of the linked list.
The header node contains pointers to the first and last nodes of the list. It acts as a placeholder and simplifies the implementation of various operations on the linked list. The pointers in the header node allow easy access to the first and last nodes, even when the list is empty.
Here are some key features and advantages of a Linked List with a Header Node:
- Simplified Insertion and Deletion: The header node simplifies the insertion and deletion operations. When inserting a node at the beginning or end of the list, there is no need to handle the special case of an empty list separately. The header node ensures that the pointers are updated correctly.
- Easy List Traversal: The header node provides a consistent starting point for traversing the linked list. The traversal can start from the node following the header node, ensuring that the actual data nodes are traversed without any special handling for an empty list.
- Enhanced List Management: The header node allows efficient management of the linked list. It provides information about the size of the list, such as the total number of nodes. This information can be useful for various list operations and algorithms.
- Improved Code Readability: The presence of the header node often leads to cleaner and more readable code. It eliminates the need for complex conditional checks and special cases for an empty list. The code becomes more concise and easier to understand.
While a Linked List with a Header Node provides these advantages, it also introduces some additional overhead in terms of memory usage. The header node requires additional space, but it simplifies the implementation and improves the efficiency of certain operations.
Overall, a Linked List with a Header Node is a useful variation of the traditional linked list that simplifies the implementation and enhances the management of the list. It provides a convenient starting point for operations and improves the code readability, making it a valuable data structure in many scenarios.
Here’s an example of a C program that implements a singly linked list with a header node:
#include <stdio.h>
#include <stdlib.h>
// Structure for a node in the linked list
struct Node {
int data;
struct Node* next;
};
// 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 insert a node at the beginning of the list
void insertAtBeginning(struct Node* header, int data) {
struct Node* newNode = createNode(data);
newNode->next = header->next;
header->next = newNode;
}
// Function to display the linked list
void displayLinkedList(struct Node* header) {
if (header->next == NULL) {
printf(“Linked list is empty!\n”);
return;
}
struct Node* temp = header->next;
while (temp != NULL) {
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“\n”);
}
int main() {
// Create the header node
struct Node* header = createNode(0);
// Insert nodes at the beginning
insertAtBeginning(header, 4);
insertAtBeginning(header, 3);
insertAtBeginning(header, 2);
insertAtBeginning(header, 1);
// Display the linked list
printf(“Linked List: “);
displayLinkedList(header);
// Free the allocated memory
struct Node* temp;
while (header != NULL) {
temp = header;
header = header->next;
free(temp);
}
return 0;
}
In this program, we define a structure Node to represent each node in the linked list. The createNode function is used to create a new node with the given data. The insertAtBeginning function inserts a new node at the beginning of the list by updating the pointers. The displayLinkedList function traverses the list and prints the data values of each node.
In the main function, we create the header node using the createNode function. We then insert nodes at the beginning of the list using the insertAtBeginning function. Finally, we display the linked list using the displayLinkedList function.
After the program finishes, we free the allocated memory by traversing the list and freeing each node using a temporary pointer.
This program demonstrates the implementation of a singly linked list with a header node in C. You can modify it as needed and test different operations on the linked list.
Define Linked List representation of a Polynomial
In a polynomial, the terms are represented by coefficients and exponents. One way to represent a polynomial in C is by using a linked list. Each node in the linked list represents a term in the polynomial, with the coefficient and exponent stored as data in the node.
Here’s an example of a C structure and functions to represent a polynomial using a linked list:
#include <stdio.h>
#include <stdlib.h>
// Structure for a term in the polynomial
struct Term {
int coefficient;
int exponent;
struct Term* next;
};
// Function to create a new term
struct Term* createTerm(int coefficient, int exponent) {
struct Term* newTerm = (struct Term*)malloc(sizeof(struct Term));
newTerm->coefficient = coefficient;
newTerm->exponent = exponent;
newTerm->next = NULL;
return newTerm;
}
// Function to insert a term at the end of the polynomial
void insertTerm(struct Term** poly, int coefficient, int exponent) {
struct Term* newTerm = createTerm(coefficient, exponent);
if (*poly == NULL) {
*poly = newTerm;
} else {
struct Term* temp = *poly;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newTerm;
}
}
// Function to display the polynomial
void displayPolynomial(struct Term* poly) {
if (poly == NULL) {
printf(“Polynomial is empty!\n”);
return;
}
struct Term* temp = poly;
while (temp != NULL) {
printf(“%dx^%d “, temp->coefficient, temp->exponent);
if (temp->next != NULL) {
printf(“+ “);
}
temp = temp->next;
}
printf(“\n”);
}
int main() {
struct Term* polynomial = NULL;
// Insert terms into the polynomial
insertTerm(&polynomial, 5, 2);
insertTerm(&polynomial, -3, 1);
insertTerm(&polynomial, 2, 0);
// Display the polynomial
printf(“Polynomial: “);
displayPolynomial(polynomial);
// Free the allocated memory
struct Term* temp;
while (polynomial != NULL) {
temp = polynomial;
polynomial = polynomial->next;
free(temp);
}
return 0;
}
In this program, we define a structure Term to represent each term in the polynomial. Each term has a coefficient and an exponent, and a pointer to the next term in the linked list.
The createTerm function is used to create a new term with the given coefficient and exponent. The insertTerm function inserts a new term at the end of the polynomial by traversing the linked list and updating the pointers. The displayPolynomial function traverses the linked list and prints each term in the polynomial.
In the main function, we create an empty polynomial represented by a NULL pointer. We then insert terms into the polynomial using the insertTerm function. Finally, we display the polynomial using the displayPolynomial function.
After the program finishes, we free the allocated memory by traversing the linked list and freeing each term using a temporary pointer.
This program demonstrates the representation of a polynomial using a linked list in C. You can modify it as needed and perform various operations on the polynomial, such as addition, subtraction, and evaluation.
Write a Program in C for the Addition of two Polynomials
Here’s a program in C for the addition of two polynomials represented using linked lists:
#include <stdio.h>
#include <stdlib.h>
// Structure for a term in the polynomial
struct Term {
int coefficient;
int exponent;
struct Term* next;
};
// Function to create a new term
struct Term* createTerm(int coefficient, int exponent) {
struct Term* newTerm = (struct Term*)malloc(sizeof(struct Term));
newTerm->coefficient = coefficient;
newTerm->exponent = exponent;
newTerm->next = NULL;
return newTerm;
}
// Function to insert a term at the end of the polynomial
void insertTerm(struct Term** poly, int coefficient, int exponent) {
struct Term* newTerm = createTerm(coefficient, exponent);
if (*poly == NULL) {
*poly = newTerm;
} else {
struct Term* temp = *poly;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newTerm;
}
}
// Function to add two polynomials
struct Term* addPolynomials(struct Term* poly1, struct Term* poly2) {
struct Term* result = NULL;
struct Term* current = NULL;
while (poly1 != NULL && poly2 != NULL) {
if (poly1->exponent > poly2->exponent) {
insertTerm(&result, poly1->coefficient, poly1->exponent);
poly1 = poly1->next;
} else if (poly1->exponent < poly2->exponent) {
insertTerm(&result, poly2->coefficient, poly2->exponent);
poly2 = poly2->next;
} else {
int sum = poly1->coefficient + poly2->coefficient;
if (sum != 0) {
insertTerm(&result, sum, poly1->exponent);
}
poly1 = poly1->next;
poly2 = poly2->next;
}
if (current == NULL) {
current = result;
} else {
while (current->next != NULL) {
current = current->next;
}
}
}
// Append remaining terms from either polynomial
struct Term* remainingPoly = (poly1 != NULL) ? poly1 : poly2;
while (remainingPoly != NULL) {
insertTerm(¤t, remainingPoly->coefficient, remainingPoly->exponent);
remainingPoly = remainingPoly->next;
}
return result;
}
// Function to display the polynomial
void displayPolynomial(struct Term* poly) {
if (poly == NULL) {
printf(“Polynomial is empty!\n”);
return;
}
struct Term* temp = poly;
while (temp != NULL) {
printf(“%dx^%d “, temp->coefficient, temp->exponent);
if (temp->next != NULL) {
printf(“+ “);
}
temp = temp->next;
}
printf(“\n”);
}
int main() {
struct Term* polynomial1 = NULL;
struct Term* polynomial2 = NULL;
struct Term* result = NULL;
// Insert terms into the first polynomial
insertTerm(&polynomial1, 3, 4);
insertTerm(&polynomial1, 2, 3);
insertTerm(&polynomial1, 1, 2);
// Insert terms into the second polynomial
insertTerm(&polynomial2, 2, 3);
insertTerm(&polynomial2, -3, 2);
insertTerm(&polynomial2, 4, 0);
// Add the polynomials
result = addPolynomials(polynomial1, polynomial2);
// Display the polynomials and the result
printf(“Polynomial 1: “);
displayPolynomial(polynomial1);
printf(“Polynomial 2: “);
displayPolynomial(polynomial2);
printf(“Result: “);
displayPolynomial(result);
// Free the allocated memory
struct Term* temp;
while (polynomial1 != NULL) {
temp = polynomial1;
polynomial1 = polynomial1->next;
free(temp);
}
while (polynomial2 != NULL) {
temp = polynomial2;
polynomial2 = polynomial2->next;
free(temp);
}
while (result != NULL) {
temp = result;
result = result->next;
free(temp);
}
return 0;
}
In this program, we define a structure Term to represent each term in the polynomial. Each term has a coefficient and an exponent, and a pointer to the next term in the linked list.
The createTerm function is used to create a new term with the given coefficient and exponent. The insertTerm function inserts a new term at the end of the polynomial by traversing the linked list and updating the pointers. The addPolynomials function adds two polynomials together by iterating through the terms of both polynomials and adding the corresponding terms. The result is stored in a new linked list. The displayPolynomial function traverses the linked list and prints each term in the polynomial.
In the main function, we create two polynomials represented by NULL pointers and insert terms into them using the insertTerm function. We then call the addPolynomials function to add the two polynomials together, and store the result in a new polynomial. Finally, we display the original polynomials and the result using the displayPolynomial function.
After the program finishes, we free the allocated memory by traversing the linked lists and freeing each term using a temporary pointer.
This program demonstrates the addition of two polynomials using linked lists in C. You can modify it as needed and perform various operations on the polynomials, such as subtraction, multiplication, and evaluation.