## Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

## Friday, 27 March 2015

### implementation example of double linked list (set union and intersection operations)

Implementation example of double linked list (set union and intersection operations)

/*
* implementation example of double linked list (set union and intersection operations)
*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

enum BOOL {FALSE, TRUE};
typedef int BOOL;
struct NODE_d;
typedef struct NODE_d Node_d;
typedef Node_d* PtrNode_d;
typedef PtrNode_d List_d;
typedef PtrNode_d Position_d;
typedef int DataType; // this is a default data type

struct NODE_d{ // single link list node
DataType data;
PtrNode_d next;
PtrNode_d previous;
};

PtrNode_d NewList_d() // returns the List's header
{
PtrNode_d tempNode =  malloc(sizeof(Node_d));
tempNode->next = NULL;
tempNode->previous = NULL;
return tempNode;
}
Position_d NewNode_d()
{
return malloc(sizeof(Node_d)); // for old compilers,
// explicit type conversion like (Node) is needed to be
//used.
}

void Delete_d(PtrNode_d node)
{
free(node);
}

BOOL IsLast_d(List_d L, Position_d pos)
{
return (pos->next == NULL);
}

BOOL IsEmpty_d(List_d L)
{
return (L->next == NULL);
}

void Insert_d ( List_d L, DataType data, Position_d pos)
{
Position_d tempPos;
tempPos = NewNode_d(); // creates and allocates memory space
if(tempPos == NULL)
{
fprintf(stderr, "error: request for allocation of memory using function \"malloc\" rejected");
return;
}
tempPos->data = data;
tempPos->next = pos->next;
tempPos->previous = pos;
pos->next = tempPos;
if(!IsLast_d(L, tempPos))
tempPos->next->previous = tempPos;
}

Position_d Find_d(List_d L, DataType element)
{
Position_d tempPos = L->next;
while(tempPos!=NULL && tempPos->data!=element)
tempPos = tempPos->next;
return tempPos; // this return NULL by default when it fails to find the
// element
}

void DisplayElement_d(DataType element)
{
printf("%d\n", element);
}
void Display_d (List_d L)
{

Position_d pos = L->next;
if(IsEmpty_d(L))
return;
while (pos != NULL)
{
DisplayElement_d(pos->data);
pos = pos->next;
}
}

List_d setIntersect(List_d L1, List_d L2) // this function runs at O(N^2) or to be more precise O(MN)
{
Position_d pos_top, tempPos;
List_d L = NewList_d();
pos_top = L;
tempPos = L1->next;
while(tempPos != NULL)
{
if(Find_d(L, tempPos->data)==NULL && Find_d(L2, tempPos->data) != NULL)
{
Insert_d(L, tempPos->data, pos_top);
pos_top = pos_top->next;
}
tempPos = tempPos->next;
}

return L;
}

List_d setUnion(List_d L1, List_d L2) // this function runs at O(N^2) or to be more precise O(MN)
{
Position_d pos_top, tempPos;
List_d L = NewList_d();
pos_top = L;
tempPos = L1->next;
while (tempPos != NULL)
{
if(Find_d(L, tempPos->data) == NULL)
{ // there is a possibility that an element can be repeated in the same list
Insert_d(L, tempPos->data, pos_top);
pos_top = pos_top->next;
}
tempPos = tempPos->next;
}
tempPos = L2->next;
while(tempPos != NULL)
{
if(Find_d(L, tempPos->data) == NULL)
{ // incrementation takes place only if the data record is not found
Insert_d(L, tempPos->data, pos_top);
pos_top = pos_top->next;
}
tempPos = tempPos->next;
}
return L;
}
void getElements(List_d L, const char* A)
{
unsigned int i, n;
int data; Position_d top = L;
printf("enter the number of elements for %s", A);
scanf("%d", &n);
printf("enter the elements of the set %s:", A);
for(i=0; i<n; i++)
{
scanf("%d", &data);
Insert_d(L, data, top);
top = top->next;
}
}
int main()
{
List_d L1 = NewList_d();
List_d L2 = NewList_d();
List_d L_union, L_intersection;
getElements(L1, "A");
getElements(L2, "B");
L_union = setUnion(L1, L2);
printf("\nunion of A and B:\n");
Display_d(L_union);
getch();
L_intersection = setIntersect(L1, L2);
printf("\nintersection of A and B:\n");
Display_d(L_intersection);

getch();
return 0;
}