Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List

//---------------------------------Implementation details of the Project-------------------------------------
/*
The written program below is an implementation of linked lists in C language. It performs two operations, intersection and
union of two linked lists.

A linked list is a data structure consisting of a group of nodes in which each node points to the next node in the
sequence. In a singly linked list, each node has only one pointer to the next node, while in a doubly linked list,
each node has two pointers, one to the next node and another to the previous node.

The written program below uses singly linked lists, where each node has a data field and a pointer field that points to the
next node in the list. The program defines a structure Node to represent a node in the list, and the typedef keyword
is used to give the name Node to this structure.

The main() function of the program creates two linked lists list1 and list2. It then inserts some values into these
lists using the insertNode() function, which inserts a new node at the end of the list. The program then prints the
contents of these lists using the printList() function.

The program then finds the intersection of the two lists using the intersection() function. This function takes two
linked lists as input arguments and returns a new linked list that contains the common elements in both input lists.
The program then prints the contents of the intersection list.

Finally, the program written below finds the union of the two lists using the unionSet() function. This function takes two linked
lists as input arguments and returns a new linked list that contains all the elements in both input lists. The
program then prints the contents of the union list.

In addition to these functions, the program also defines a function createNode() that creates a new node with the
given data. This function uses dynamic memory allocation to allocate memory for the new node. The program also uses
the malloc() function from the stdlib.h library to dynamically allocate memory for the nodes.

Overall, the program written below demonstrates the use of linked lists in C language and shows how to perform basic operations
such as inserting elements, printing the contents of a list, and finding the intersection and union of two lists.
*/

//---------------------------------Program of the code----------------------------------------
#include /* we have to include stdio.h(standard input output library for c)its a preprocessor
directive which helps in including inbuilt libraries and function ex. printf*/
#include // declares various utility functions for type conversions, memory allocation, algorithms,

// Define the node structure for linked lists
typedef struct Node
{
int data; // The data stored in the node
struct Node* next;// A pointer to the next node in the list
} Node;

// Function prototypes
Node* createNode(int); // Creates a new node with the given data
void insertNode(Node**, int); // Inserts a new node with the given data at the end of the list
void printList(Node*); // Prints out the linked list
Node* intersection(Node*, Node*);// Finds the intersection of two linked lists
Node* unionSet(Node*, Node*);// Finds the union of two linked lists
int main()
{
// Create the two lists
Node* list1 = NULL; // Create the first list
Node* list2 = NULL; // Create the second list

// Insert data into the first list
insertNode(&list1, 10);//insert 10 in list 1
insertNode(&list1, 15);//insert 15 in list 1
insertNode(&list1, 4);//insert 14 in list 1
insertNode(&list1, 20);//insert 20 in list 1

// Insert data into the second list
insertNode(&list2, 8);//insert 8 in list 2
insertNode(&list2, 4);//insert 4 in list 2
insertNode(&list2, 2);//insert 2 in list 2
insertNode(&list2, 10);//insert 10 in list 2

//print on console
printf("List 1: ");//print on console
printList(list1);//print list 1 on console
printf("List 2: ");//print on console
printList(list2);//print list 2 on console

// Find the intersection of the two lists
Node* intersect = intersection(list1, list2);//call intersection function by passing two arguments(pointers of list).
printf("Intersection: ");//print on console
printList(intersect);//print intersecting integers of two list on console

// Find the union of the two lists
Node* unionset = unionSet(list1, list2);//call unionset function by passing two arguments(pointers of list).
printf("Union: ");//print on console
printList(unionset);//print unionset integers of two list on console

return 0;//return 0 to called function
}

// Create a new node with the given data
Node* createNode(int data)
{
Node* newNode = (Node*)malloc(sizeof(Node));//dynamic memory allocation
//check if dynamic memory allocation happened correctly if not inform user
if (newNode!=NULL)
{
newNode->data = data;//assign data in node
newNode->next = NULL;//assign next place with null
return newNode;//return new node to called function
}
else
{
printf("CANNOT CREATE NEW NODE");//print to console
return NULL;//return null to called function
}
}

// Insert a new node with the given data at the end of the list
void insertNode(Node** head, int data)
{
Node* newNode = createNode(data);//dynamic memory allocation
if(newNode==NULL)
{
printf("CANNOT INSERT NEW NODE");//print to console
return NULL;//return null to called function
}
else
{

if (*head == NULL || (*head)->data >= data)// If the list is empty or the new node is the new head
{
newNode->next = *head; // Set the next pointer of the new node to the current head
*head = newNode;// Set the head pointer to the new node
return;//return
}
Node* curr = *head;
while (curr->next != NULL && curr->next->data < data)// Traverse the list to find the right position for the new node
{
curr = curr->next;//move to next node
}
newNode->next = curr->next; // Set the next pointer of the new node to the next node of the current node
curr->next = newNode;// Set the next pointer of the current node to the new node
}
}

// Print out the linked list
void printList(Node* head)
{
while (head != NULL)
{
printf("%d ", head->data);//print the data of the respective list
head = head->next;//move the pointer to next node
}
printf("n");//print on console
}

// This function takes two linked lists 'list1' and 'list2' as input arguments
// and returns a new linked list that contains the common elements in both input lists.
Node* intersection(Node* list1, Node* list2)
{
// Initialize the 'intersect' and 'tail' pointers to NULL.
Node* intersect = NULL;
Node* tail = NULL;
// Traverse both input lists as long as they are not empty.
while (list1 != NULL && list2 != NULL)
{
// If the current nodes of both lists have the same value,
// create a new node with that value and append it to the 'intersect' list.
if (list1->data == list2->data)
{
Node* newNode = createNode(list1->data);
if (intersect == NULL)
{
// If this is the first node being added to the 'intersect' list,
// set both 'intersect' and 'tail' pointers to point to it.
intersect = tail = newNode;
}
else
{
// Otherwise, append the new node to the end of the 'intersect' list.
tail->next = newNode;
tail = newNode;
}
// Move both input lists forward by one node.
list1 = list1->next;
list2 = list2->next;
}
// If the current node of 'list1' has a smaller value than the current node of 'list2',
// move 'list1' forward by one node.
else if (list1->data < list2->data)
{
list1 = list1->next;
}
// If the current node of 'list2' has a smaller value than the current node of 'list1',
// move 'list2' forward by one node.
else // list2->data < list1->data
{
list2 = list2->next;
}
}

// Return the 'intersect' list.
return intersect;

}

// This function takes two linked lists 'list1' and 'list2' as input arguments
// and returns a new linked list that contains the union of the two input lists,
// i.e., all the elements from both lists without duplicates.

Node* unionSet(Node* list1, Node* list2)
{
// Initialize the 'unionList', 'tail', and 'temp' pointers to NULL.
Node* unionList = NULL;
Node* tail = NULL;
Node* temp = NULL;
// Traverse list1 and add all nodes to the union list.
while (list1 != NULL)
{
temp = createNode(list1->data);
if (unionList == NULL)
{
// If this is the first node being added to the 'unionList' list,
// set both 'unionList' and 'tail' pointers to point to it.
unionList = tail = temp;
}
else
{
// Otherwise, append the new node to the end of the 'unionList' list.
tail->next = temp;
tail = temp;
}
// Move 'list1' forward by one node.
list1 = list1->next;
}

// Traverse list2 and add only the unique nodes to the union list.
while (list2 != NULL)
{
// Check if the current node in list2 is already present in the union list.
Node* curr = unionList;
while (curr != NULL && curr->data != list2->data)
{
curr = curr->next;
}

// If the node is not present in the union list, add it.
if (curr == NULL)
{
temp = createNode(list2->data);
tail->next = temp;
tail = temp;
}

// Move 'list2' forward by one node.
list2 = list2->next;
}

// Return the 'unionList' list.
return unionList;
}