In C++ Part - 1: Implement a singly linked list ADT to store a collection of dou
ID: 3856271 • Letter: I
Question
In C++
Part - 1: Implement a singly linked list ADT to store a collection of doubles.
(You are allowed to extend the demo code posted on GitHub for this homework. link: https://github.com/Premdeep/CSC340-Summer-2017/tree/master/LinkedList ).
Make sure to provide an interactive user interface to test these new functions in the main() for grader . Your ADT will include the following member functions:
--- a default constructor
--- the "big-3": destructor, copy constructor and overloaded assignment operator
1. a member function pushFront(data) that inserts a node with data at the front of the list
2. a member function pushBack(data) that appends a node with data at the back of the list
3. a member function popFront() that removes first node of the list.
4. a member function popBack() that removes last node of the list.
5. a member function insert(index, val) that inserts a new node with value "val" at a specific position mentioned by the index argument.
6. a member function deleteDuplicates(val) that deletes a node with that number and all its copies from the list, where these copies can be located anywhere in the list.
7. a member function mtoLastElement(M) that returns Mth to the last element of a list such that when M = 0, the last element of the list is returned.
8. a member function size() that returns the size of the list.
9. an overloaded put operator (<<) to print out all the data items stored in a linked list. Note that you are recommended to overload this operator as a friend function of the LinkedList class.
10. a member function reverseList() that reverses a linked list without recreating a temporary copy of this linked list. In other words, your function CAN NOT use the 'new' operator. Here is an example, if a list contains the following data items, 3 -> 5 -> 1 -> 7; this reverse() function will change the list to 7 -> 1 -> 5 -> 3.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct node
{
struct node *prev;
int n;
struct node *next;
}*h,*temp,*temp1,*temp2,*temp4;
void insert1();
void insert2();
void insert3();
void traversebeg();
void traverseend(int);
void sort();
void search();
void update();
void delete();
int count = 0;
void main()
{
int ch;
h = NULL;
temp = temp1 = NULL;
printf(" 1 - Insert at beginning");
printf(" 2 - Insert at end");
printf(" 3 - Insert at position i");
printf(" 4 - Delete at i");
printf(" 5 - Display from beginning");
printf(" 6 - Display from end");
printf(" 7 - Search for element");
printf(" 8 - Sort the list");
printf(" 9 - Update an element");
printf(" 10 - Exit");
while (1)
{
printf(" Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert1();
break;
case 2:
insert2();
break;
case 3:
insert3();
break;
case 4:
delete();
break;
case 5:
traversebeg();
break;
case 6:
temp2 = h;
if (temp2 == NULL)
printf(" Error : List empty to display ");
else
{
printf(" Reverse order of linked list is : ");
traverseend(temp2->n);
}
break;
case 7:
search();
break;
case 8:
sort();
break;
case 9:
update();
break;
case 10:
exit(0);
default:
printf(" Wrong choice menu");
}
}
}
void create()
{
int data;
temp =(struct node *)malloc(1*sizeof(struct node));
temp->prev = NULL;
temp->next = NULL;
printf(" Enter value to node : ");
scanf("%d", &data);
temp->n = data;
count++;
}
void insert1()
{
if (h == NULL)
{
create();
h = temp;
temp1 = h;
}
else
{
create();
temp->next = h;
h->prev = temp;
h = temp;
}
}
void insert2()
{
if (h == NULL)
{
create();
h = temp;
temp1 = h;
}
else
{
create();
temp1->next = temp;
temp->prev = temp1;
temp1 = temp;
}
}
void insert3()
{
int pos, i = 2;
printf(" Enter position to be inserted : ");
scanf("%d", &pos);
temp2 = h;
if ((pos < 1) || (pos >= count + 1))
{
printf(" Position out of range to insert");
return;
}
if ((h == NULL) && (pos != 1))
{
printf(" Empty list cannot insert other than 1st position");
return;
}
if ((h == NULL) && (pos == 1))
{
create();
h = temp;
temp1 = h;
return;
}
else
{
while (i < pos)
{
temp2 = temp2->next;
i++;
}
create();
temp->prev = temp2;
temp->next = temp2->next;
temp2->next->prev = temp;
temp2->next = temp;
}
}
void delete()
{
int i = 1, pos;
printf(" Enter position to be deleted : ");
scanf("%d", &pos);
temp2 = h;
if ((pos < 1) || (pos >= count + 1))
{
printf(" Error : Position out of range to delete");
return;
}
if (h == NULL)
{
printf(" Error : Empty list no elements to delete");
return;
}
else
{
while (i < pos)
{
temp2 = temp2->next;
i++;
}
if (i == 1)
{
if (temp2->next == NULL)
{
printf("Node deleted from list");
free(temp2);
temp2 = h = NULL;
return;
}
}
if (temp2->next == NULL)
{
temp2->prev->next = NULL;
free(temp2);
printf("Node deleted from list");
return;
}
temp2->next->prev = temp2->prev;
if (i != 1)
temp2->prev->next = temp2->next;
if (i == 1)
h = temp2->next;
printf(" Node deleted");
free(temp2);
}
count--;
}
void traversebeg()
{
temp2 = h;
if (temp2 == NULL)
{
printf("List empty to display ");
return;
}
printf(" Linked list elements from begining : ");
while (temp2->next != NULL)
{
printf(" %d ", temp2->n);
temp2 = temp2->next;
}
printf(" %d ", temp2->n);
}
void traverseend(int i)
{
if (temp2 != NULL)
{
i = temp2->n;
temp2 = temp2->next;
traverseend(i);
printf(" %d ", i);
}
}
void search()
{
int data, count = 0;
temp2 = h;
if (temp2 == NULL)
{
printf(" Error : List empty to search for data");
return;
}
printf(" Enter value to search : ");
scanf("%d", &data);
while (temp2 != NULL)
{
if (temp2->n == data)
{
printf(" Data found in %d position",count + 1);
return;
}
else
temp2 = temp2->next;
count++;
}
printf(" Error : %d not found in list", data);
}
void update()
{
int data, data1;
printf(" Enter node data to be updated : ");
scanf("%d", &data);
printf(" Enter new data : ");
scanf("%d", &data1);
temp2 = h;
if (temp2 == NULL)
{
printf(" Error : List empty no node to update");
return;
}
while (temp2 != NULL)
{
if (temp2->n == data)
{
temp2->n = data1;
traversebeg();
return;
}
else
temp2 = temp2->next;
}
printf(" Error : %d not found in list to update", data);
}
void sort()
{
int i, j, x;
temp2 = h;
temp4 = h;
if (temp2 == NULL)
{
printf(" List empty to sort");
return;
}
for (temp2 = h; temp2 != NULL; temp2 = temp2->next)
{
for (temp4 = temp2->next; temp4 != NULL; temp4 = temp4->next)
{
if (temp2->n > temp4->n)
{
x = temp2->n;
temp2->n = temp4->n;
temp4->n = x;
}
}
}
traversebeg();
}