Project 1 - Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a linked list node
struct Node {
int data;
struct Node* next;
};
// Function to insert a new node at the end of a linked list
struct Node* insertEnd(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL) {
return newNode;
}
struct Node* last = head;
while (last->next != NULL) {
last = last->next;
}
last->next = newNode;
return head;
}
// Function to print a linked list
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
// Function to find the intersection of two linked lists
struct Node* getIntersection(struct Node* list1, struct Node* list2) {
struct Node* result = NULL;
struct Node* lastPtr = NULL;
while (list1 != NULL && list2 != NULL) {
if (list1->data == list2->data) {
result = insertEnd(result, list1->data);
if (lastPtr == NULL) {
lastPtr = result;
} else {
lastPtr = lastPtr->next;
}
list1 = list1->next;
list2 = list2->next;
} else if (list1->data < list2->data) {
list1 = list1->next;
} else {
list2 = list2->next;
}
}
return result;
}
// Function to find the union of two linked lists
struct Node* getUnion(struct Node* list1, struct Node* list2) {
struct Node* result = NULL;
struct Node* lastPtr = NULL;
while (list1 != NULL || list2 != NULL) {
if (list1 == NULL) {
result = insertEnd(result, list2->data);
list2 = list2->next;
} else if (list2 == NULL) {
result = insertEnd(result, list1->data);
list1 = list1->next;
} else if (list1->data < list2->data) {
result = insertEnd(result, list1->data);
list1 = list1->next;
} else if (list1->data > list2->data) {
result = insertEnd(result, list2->data);
list2 = list2->next;
} else {
// list1->data == list2->data
result = insertEnd(result, list1->data);
list1 = list1->next;
list2 = list2->next;
}
if (lastPtr == NULL) {
lastPtr = result;
} else {
lastPtr = lastPtr->next;
}
}
return result;
}
// Function to free the memory occupied by a linked list
void freeList(struct Node* head) {
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
int main() {
// Example usage
struct Node* list1 = NULL;
struct Node* list2 = NULL;
// Insert elements into the first linked list
list1 = insertEnd(list1, 1);
list1 = insertEnd(list1, 2);
list1 = insertEnd(list1, 0);
list1 = insertEnd(list1, 4);
list1 = insertEnd(list1, 6);
// Insert elements into the second linked list
list2 = insertEnd(list2, 2);
list2 = insertEnd(list2, 4);
list2 = insertEnd(list2, 6);
list2 = insertEnd(list2, 8);
// Print the original linked lists
printf("List 1: ");
printList(list1);
printf("List 2: ");
printList(list2);
// Find and print the intersection
struct Node* intersection = getIntersection(list1, list2);
printf("Intersection: ");
printList(intersection);
// Find and print the union
struct Node* unionList = getUnion(list1, list2);
printf("Union: ");
printList(unionList);
// Free the memory occupied by the linked lists
freeList(list1);
freeList(list2);
freeList(intersection);
freeList(unionList);
return 0;
}
