CS 2123 Data Structures Assignment 2 Due Friday February 19 1. (100 pts) Write a
ID: 3669034 • Letter: C
Question
CS 2123
Data Structures Assignment 2
Due Friday February 19
1. (100 pts) Write a program to implement the following functions on linked lists. Assume that node structure of a singly linked list is as follows.
struct node {
int info;
and node structure of a doubly linked list is as follows
Implement the below functions whose prototypes are given below
CopytoSinglyLinked function makes a singly linked copy of a doubly linked list that is provided as a parameter and returns a pointer to the singly linked list.
Previous function returns the previous node of current in a singly linked list pointed by head. If current is the first node Previous returns null.
PrintReverse function prints a elements of a singly linked list in reverse order. This should be implemented as an iterative function. Use Previous function in your imple- mentation.
RemoveDuplicates function removes duplicate elements in a singly linked list that is provided as a parameter. The contents of the list need not be sorted. You should remove duplicates in an unsorted list without changing the order of elements in the list.
CS 2123 Data Structures Assignment 2 Due Friday February 19 1. (100 pts) Write a program to implement the following functions on linked lists. Assume that node structure of a singly inked list is as follows. struct node int info; struct node next; typedef struct node node; and node structure of a doubly linked list is as follows struct cnode int info; struct cnode next struct enode previous; typedef struct cnode cnode; Implement the below functions whose prototypes are given below node CopytoSinglyLinked (cnode head) node *Previous(node .head, node *current) void PrintReverse (node .head) node *RemoveDuplicates (node head) CopyloSinglyLinked function makes a singly linked copy of a doubly linked list that is provided as a parameter and returns a pointer to the singly linked list. . Previons function returns the previous node of current in a singly linked list pointed by head. If current is the first node Previous returns null. PrintReverse function prints a elements of a singly linked list in reverse order. This should be implemented as an iterative function. Use Previous function in your imple- mentation. .Remove Duplicates function removes duplicate elements in a singly linked list that is provided as a parameter. The contents of the list need not be sorted. You should remove duplicates in an unsorted list without changing the order of elements in the list.Explanation / Answer
node* copytoSinglyLinked(cnode* head){ // Copy a Doubly_linklist to Single_linklist
node* h = new node();
h->info = head->info;
node* temp = h;
cnode* temp_1 = head->next;
while (temp_1 != NULL){ // iterarate each node and add into the list
node* temp_2 = new node();
temp_2.info = temp_1.info;
temp->next = temp_2;
temp = temp_2;
temp_1 = temp_1->next;
}
return h;
}
node* previous(node* head,node* current){
node* prev = NULL;
node* temp = head;
while (temp != null || temp != current){
prev = temp;
temp = temp->next;
}
return prev;
}
void PrintReverse(node* head){
if (head == NULL) return;
node* temp = head;
while (temp->next != NULL){
temp = temp->next;
}
while (temp != NULL){
printf("%d ",temp->info);
temp = previous(head, temp);
}
printf(' ');
}
node* RemoveDuplicate(node* head){
map<int,int> mymap;
node* temp = head;
mymap[temp->info] = 0;
while (temp->next != NULL){
if (mymap.find(temp->next->info) == mymap.end())
temp = temp->next;
else{
temp->next = temp->next->next;
temp = temp->next;
}
}
return head;
}