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

Singly Linked list: It is the most basic linked list in which traversal is unidirectional i.e. from head node to the last node. Doubly Linked list: In this linked list traversal can be done in both ways and hence it requires an extra pointer. Circular Linked list: This linked list is unidirectional but in this list, the last node points to the first i.e. the head node and hence it becomes circular in nature. Circular doubly Linked list: The circular doubly linked list is a combination of the doubly linked list and the circular linked list. It means that this linked list is bidirectional and contains two pointers and the last pointer points to the first pointer.

Linked list are commonly used for:

• Linked list are mostly used because of their effective insertion and deletion.
• Insertion and deletion in the linked list are very effective and take less time complexity as compared to the array data strucure.
• This data structure is simple and can be also used to implement a stack, queues and other abstract data structures

Application of Linked lists:

• Linked lists are used to implement stacks and queues.
• It is used for the various representations of trees and graphs.
• It is used in dynamic memory allocation.
• It is used for representing sparse matrices.
• It is used for manipulation of polynomials.
• It is also used for performing arithmatic operations on long integers.
• It is used for finding paths in networks.

Applications of Linked list in the real world:

• The list of song in music player are linked to the previous and next songs.
• In a web browser, previous and next web page URLs are linked through the previous and next buttons.
• In image viewer, the previous and next images are linked with the help of previous and next buttons.
• Switching between two applications is carried out by using "alt+tab" in windows and "cmd+tab" in mac book. It requires the functionality of circular linked list.
• In mobile phones, we save the conacts of the people. the newly entered contact details will be placed at the correct alphabetical order. This can be achieved by linked list to set contact at correct alphabetical position.
• The modification that we are made in the documents are actually created as nodes in doubly linked list. We can can simply use the undo option by pressing Ctrl+Z to modify the contents. It is done by the functionality of linked list.

Advantages

• Insertion and deletion in linked lists are very efficient.
• Linked list can be expanded in constant time.
• For implementation of stacks and queues and for representation of trees and graphs.
• Linked lists are used for dynamic memory allocation which means effective memory utilization hence no memory wastage.

Disadvantages

• Use of pointers is more in linked lists hence complex and requires more memory.
• searching an element is costly and requires 0(n) time complexity.
• Traversing is more time consuming and reverse traversing is not possible in singly linked lists.
• Random access is not possible due to dynamic memory allocation.

/* Program to find union and inyersection using linked list */

#include <stdio.h>
#include <stdlib.h>

// A structure of linked list node
struct node

{
int data;
struct node *next;

} *LLOne, *LLTwo, *unionLL, *intersectionLL;

void initialize()

{
LLOne = LLTwo = NULL;
}
//Given a Inserts a node in front of a singly linked list.

void insert(struct node **head, int num)

{
// Create a new Linked List node
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = num;
// Next pointer of new node will point to head node of linked list
newNode->next = *head;
//make new node as new head of linked list
*head = newNode;
}

// Searches an element in Linked List by linearly traversing from head to tail
int search(struct node *head, int num)

{
while (head != NULL)

{
if (head->data == num)

{
return 1;
}
head = head->next;
}
return 0;

}

//Returns the union of two given linked list

struct node* findunion(struct node *LLOne, struct node *LLTwo)

{
unionLL = NULL;
// Add all nodes of first Linked List to unionLL
struct node *temp = LLOne;
while(temp != NULL)

{
insert(&unionLL, temp->data);
temp = temp->next;
}
// Insert those nodes of LLTwo which is not present in LLOne
while(LLTwo != NULL)

{
if(!search(LLOne, LLTwo->data))

{
insert(&unionLL, LLTwo->data);
}
LLTwo = LLTwo->next;
}
return unionLL;
}

//Returns the Linked List which contains common nodes of two given linked list

struct node* intersection(struct node *LLOne, struct node *LLTwo)

{
intersectionLL = NULL;
//Search every element of LLOne in LLTwo, If found then add it to intersection List
while(LLOne != NULL)

{
if(search(LLTwo, LLOne->data))

{
insert(&intersectionLL, LLOne->data);
}
LLOne = LLOne->next;
}
return intersectionLL;
}
//Prints a linked list from head node till tail node

void printLinkedList(struct node *nodePtr)

{
while (nodePtr != NULL)

{
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf("-->");

}
}

int main()

{
int i, LLOneCount, LLTwoCount, temp;
initialize();
//Creating First linked List
printf("Enter number of nodes in first Linked List\n");
fflush(stdout);
scanf("%d", &LLOneCount);
printf("Enter %d integers\n", LLOneCount);
for(i=0; i<LLOneCount; i++)

{
scanf("%d", &temp);
insert(&LLOne, temp);
}
printLinkedList(LLOne);
printf("\nEnter number of nodes in second Linked List\n");
fflush(stdout);
scanf("%d", &LLTwoCount);
printf("Enter %d integers\n", LLTwoCount);
for(i=0; i<LLTwoCount; i++)

{
scanf("%d", &temp);
insert(&LLTwo, temp);
}
printLinkedList(LLTwo);
//printing Union of two given linked list
findunion(LLOne, LLTwo);
intersection(LLOne, LLTwo);
printf("\nUnion Linked List\n");
printLinkedList(unionLL);
printf("\nIntersection Linked List\n");
printLinkedList(intersectionLL);

return 0;
}

Output:

Conclusion:

1.In this way we have successfully implemented Linked list method for user defined data for working with det theory.

2. using linked list method we find out union and intersection of data which we took it from user.

3. Also dicussed application and real time application of linked list method.