using c++ , implement a linked list ADT using actual pointers. The purpose of th

Question

using c++ ,

implement a linked list ADT using actual pointers. The purpose of this program is to :

A) Build 2 list (list_1 and List_2 ). Each list consist of 15 random integer numbers that are between 0 and 20 exclusive Display List_1 and List_2.

B) Creat new list ( List_3 ) that contain all elements of list_1 followed by all elements of list_2. Display list_3

C) Display the number of occurrences of the First element in List_3.

D) Creat a new list ( list_4) by removing all duplicate numbers that are in list_3. Display list_4.

E) Display number of elements in list_4.

F) Display list_4 backwards.

G) Move the last element in list_4 and places it in the 3rd element in the same list. Display list_4.

H) Sort list_4 in increasing order. Display list 4

repeat the procces A-H untill user terminates the program

Explanation / Answer

#include<iostream>
#include<cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int data;
struct node *next;
};

//inserting node at the end

void add_node(node * &s,int value){
node* temp = new node; // creating new node with given value
temp->data = value;
temp->next = NULL;

if(!s) { // empty list becomes the new node
s = temp;
return;
} else { // find last and link the new node
node* last = s;
while(last->next) last=last->next;
last->next = temp;
}
}

// printing link list
void print(node *s){
node *temp=s;
while(temp)
{
cout<<temp->data<<" "; // printing data at current position
temp=temp->next;
}
cout<<endl;
}

// appending list_2 after list_1

node * append(node *s1,node *s2){
node *temp=s1;
while(temp->next)
temp=temp->next;
temp->next=s2; // adding list_2 at the end of list_1
return s1; // returning new list
}

// number of times 1st element of list is found
void first_occurance_in_list(node *s){
node *temp=s;
int value=temp->data;
int count=0;
while(temp){
if(value==temp->data) // checking each element by 1st element
count++; // increasing count
temp=temp->next;
}
cout<<"Number of times "<<value<<" is "<<count<<endl; // printing count
}

// removing duplicate from link list using hashing
void remove_duplicate_from_list_3(node *s){
node *curr=s;
node *prev=NULL;
bool *arr=new bool[21];
while(curr){
if(arr[curr->data]==true){// if current data is already present
prev->next=curr->next; // removing current position
delete(curr);
}
else{
arr[curr->data]=true; // setting new data in array that this value has occurred earlier
prev=curr; // setting prev as current
}
curr=prev->next;
}
}

// counting number of nodes in link list
int count(node *s){
node *temp=s;
int count=0;
while(temp){
temp=temp->next;
count++;
}
return count;
}

// printing reverse order of link list using recursion
void reverse_print(node *s){
node *temp=s;
if(temp==NULL){
cout<<endl;
return;
}
reverse_print(temp->next); // going to next element before printing the element
cout<<temp->data<<" ";
}

// replacing 3rd node value with last element
void replace(node *s){
int start=2,v1=0;
int count=0;
node *temp=s;
node *new_node;
while(temp->next){
if(count==start){ // storing value of 3rd node and pointing at that node
v1=temp->data;
new_node=temp;
}
temp=temp->next;
count++;
}

// swapping data of 3rd node and last node
new_node->data=temp->data;
temp->data=v1;
}

// prinitng sorted link list
void sort_print(node *s){

node *temp=s;
bool *arr=new bool[21];
for(int i=0;i<21;i++){
arr[i]=false; // storing arr element as false
}
while(temp){
arr[temp->data]=true; // making element as true for all element in link list
temp=temp->next;
}
for(int i=0;i<21;i++){
if(arr[i]==true)
cout<<i<<" "; // printing position in increasing order
}
cout<<endl;
}
int main(){
bool x=true;
while(x){
node *s1=NULL,*s2=NULL;
for(int i=0;i<20;i++){
int value=rand()%21;
add_node(s1,value);
value=rand()%21;
add_node(s2,value);
}
cout<<"LinkList List_1 is ";
print(s1);
cout<<"LinkList List_2 is ";
print(s2);
node *s3=append(s1,s2);
cout<<"New link list List_3 is ";
print(s3);
first_occurance_in_list(s3);
remove_duplicate_from_list_3(s3);
cout<<"After duplication removal ";
print(s3);
cout<<"Number of element in list 4 are "<<count(s3)<<endl;
cout<<"Reverse list 4 is ";
reverse_print(s3);
cout<<endl;
replace(s3);
cout<<"After replacement ";
print(s3);
cout<<"After sorting ";
sort_print(s3);
cout<<"Do you want to repeat?"<<endl;
cout<<"1 to continue 0 to break"<<endl;
cin>>x; // taking input from user 1 or 0 1 to continue and 0 to exit
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.