Question

Write a program to implement linked list data structure that will have following functions:

a. Append a node in the list

b. Insert a node in the list

c. Delete a node from the list

d. Display list

e. Find maximum value in the list

f. Find how many times a value exists in the list.

g. Search

Portion of the code is give below. You have to write code for the items (e, f, g)

Program:

#include<stdlib.h>

#include<stdio.h>

#include<iostream>

struct node {

int data;

node* next;

};

node* head=NULL;

void appendNode(int value){

node *newNode, *curr;

newNode = new node();

newNode->data=value;

newNode->next=NULL;

if (!head)

head=newNode;

else // Otherwise, insert newNode at end

{

curr=head;

while (curr->next)

curr = curr->next;

curr->next = newNode; }

}

void insertNode(int value){

node *newNode, *curr, *previous;

}

newNode = new node();

newNode->data = value;

if (head==NULL) { head = newNode;

newNode->next = NULL;

}

else {

curr = head;

while (curr != NULL && curr->data < value) previous = curr;

curr = curr->next;

}

if (previous == NULL)

{head = newNode;

newNode->next = curr;}

else {previous->next = newNode;

newNode->next = curr;}

}

{

void displayList(void) { node *curr;

curr = head;

while (curr!=NULL)

{

std::cout << curr->data <<" ";

curr = curr->next;

}

std::cout << "\n";

}

void deleteNode(int value){ node *deletedNode, *curr; if (curr == NULL){

// Deleting first node deletedNode = head; head = head ->next;

} else{

// Deleting other nodes deletedNode = curr->next; curr->next = deletedNode ->next;

}

delete deletedNode;

}

int findmaxNode(){

//complete the code here

}

int countNode(){

//complete the code here

}

int search_item() {

int found;

return found; }

int main()

{

int choice;

int x;

do{

system("cls");

std::cout << "1. Append Node"<<"\n"; std::cout << "2. Insert Node"<<"\n";

std::cout << "3. Delete Node"<<"\n";

std::cout << "4. Find Maximum Node"<<"\n"; std::cout << "5. Display Linked List"<<"\n";

std::cout << "6. Search Node"<<"\n";

std::cout << "7. Count nodes "<<"\n";

std::cout << "8. Exit"<<"\n";

std::cout << "Enter your choice(1-8):"; std::cin>>choice;

switch(choice) {

case 1:

std::cout<<"Enter a value:";

std::cin>>x;

appendNode(x);

std::cout<<"value is appened\n";

break;

case 2:

std::cout<<"Enter a value to insert:";

std::cin>>x;

insertNode(x);

std::cout<<"Value is inserted\n";

break;

case 3:

std::cout<<"complete code\n";

std::cout<<"Enter a value to delete:";

std::cin>>x;

deleteNode(x);

//complete code first break;

case 4:

std::cout<<"complete code\n";

//int max = maxNode();

//complete code first //std::cout<<"Maximum is :"<<max;

break;

case 5:

displayList();

break;

case 6:

std::cout<<"Complete code for search\n"; int x;

x= search_item(); if(x==0)

std::cout<<"Not found\n";

else

std::cout<<"found\n";

break;

case 7:

std::cout<<"Complete code\n";

//int count = count_nodes();

//std::cout<<"Number of nodes in the list is:"<<count; break;

}

system("pause");

} while(choice!=8);

}

Answer 1

As per the question we have to implement linked list with given objectives as:

a. Append a node in the list

b. Insert a node in the list

c. Delete a node from the list

d. Display list

e. Find maximum value in the list

f. Find how many times a value exists in the list.

g. Search

As per above objectives you need help only in (E,F,G) as per your mention. So I am implementing the expected result in the program given by you itself. As I am giving you proper discrption og code implemented by me as part of comments. Do refer that for your guidance.

//Start of Code

#include<stdlib.h>

#include<stdio.h>

#include<iostream>

struct node {

int data;

node* next;

};

node* head=NULL;

void appendNode(int value){

node *newNode, *curr;

newNode = new node();

newNode->data=value;

newNode->next=NULL;

if (!head)

head=newNode;

else // Otherwise, insert newNode at end

{

curr=head;

while (curr->next)

curr = curr->next;

curr->next = newNode; }

}

void insertNode(int value){

node *newNode, *curr, *previous;

}

newNode = new node();

newNode->data = value;

if (head==NULL) { head = newNode;

newNode->next = NULL;

}

else {

curr = head;

while (curr != NULL && curr->data < value) previous = curr;

curr = curr->next;

}

if (previous == NULL)

{head = newNode;

newNode->next = curr;}

else {previous->next = newNode;

newNode->next = curr;}

}

{

void displayList(void) {

node *curr;

curr = head;

while (curr!=NULL)

{

std::cout << curr->data <<" ";

curr = curr->next;

}

std::cout << "\n";

}

void deleteNode(int value){ node *deletedNode, *curr; if (curr == NULL){

// Deleting first node deletedNode = head; head = head ->next;

} else{

// Deleting other nodes deletedNode = curr->next; curr->next = deletedNode ->next;

}

delete deletedNode;

}

int findmaxNode(){              //finding max from the list.

struct node *curr = head;

int max;

if(head=NULL){                     //if head is empty that means list is empty.

cout<<”Linked List is empty\n”;

}

else{

max= head->data;                //setting max with head node.

while(curr!=NULL)

{

If(max<curr->data){

//if current node value is greater than max then change current value to max value.

max = curr-> data;

}

curr=curr->next;

}

Cout<<”The maximum value from the linked list is %d\n”<<max;    //Printing maximum value.

}

}

}

int countNode(node *head, int searching){    //for counting the number of occurrences.

node *curr = head;

int cnt=0;

while( curr != NULL)       //until current node is null or not.

{

cnt++;

cnt = cnt -> next;             

}

return cnt;                 //returning node.

}

int search_item(int item,int m) {

struct node *temp;

int found=0;        //position of search.

int cnt;

temp=head;

if(head == NULL) //checking if head is null or not.

{

cout<<”List is empty\n”;

}

else{

while(temp != NULL)   //until temp is null

{

If(temp -> data ==item){                     // if item is present in the list

cout<<”item is found at:”<<(found+1);

cnt=0;

}

else

{

cnt++;

}

found++;

temp=temp -> next;

}

If(cnt == m)           //if item is not present in the list

{

cout<<”Item is not found in the list\n”;

}

}

}

int main()

{

int choice;

int x;

do{

system("cls");

std::cout << "1. Append Node"<<"\n"; std::cout << "2. Insert Node"<<"\n";

std::cout << "3. Delete Node"<<"\n";

std::cout << "4. Find Maximum Node"<<"\n"; std::cout << "5. Display Linked List"<<"\n";

std::cout << "6. Search Node"<<"\n";

std::cout << "7. Count nodes "<<"\n";

std::cout << "8. Exit"<<"\n";

std::cout << "Enter your choice(1-8):"; std::cin>>choice;

switch(choice) {

case 1:

std::cout<<"Enter a value:";

std::cin>>x;

appendNode(x);

std::cout<<"value is appened\n";

break;

case 2:

std::cout<<"Enter a value to insert:";

std::cin>>x;

insertNode(x);

std::cout<<"Value is inserted\n";

break;

case 3:

std::cout<<"complete code\n";

std::cout<<"Enter a value to delete:";

std::cin>>x;

deleteNode(x);

//complete code first break;

case 4:

std::cout<<"complete code\n";

//int max = maxNode();

//complete code first //std::cout<<"Maximum is :"<<max;

break;

case 5:

displayList();

break;

case 6:

std::cout<<"Complete code for search\n"; int x;

x= search_item(); if(x==0)

std::cout<<"Not found\n";

else

std::cout<<"found\n";

break;

case 7:

std::cout<<"Complete code\n";

//int count = count_nodes();

//std::cout<<"Number of nodes in the list is:"<<count; break;

}

system("pause");

} while(choice!=8);

}

As by above code we can fully implement the data structure called list linked list.