Question

In: Computer Science

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

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);
}

Solutions

Expert Solution

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.


Related Solutions

How do you write an append function for a linked list that is a that has...
How do you write an append function for a linked list that is a that has a O(1) Big O notation in Python? The one given in class is O(n). He recommended using a variable to track the end the list. This is the code I have written so far. I don't think I'm properly defining the tail in the add possibly class Node: def __init__(self, init_data): self.data = init_data self.next = None def get_data(self): return self.data def get_next(self): return...
Write a Java program to implement a Single Linked List that will take inputs from a...
Write a Java program to implement a Single Linked List that will take inputs from a user as Student Names. First, add Brian and Larry to the newly created linked list and print the output Add "Kathy" to index 1 of the linked list and print output Now add "Chris" to the start of the list and "Briana" to the end of the list using built-in Java functions. Print the output of the linked list.
write a java program to Implement a Priority Queue using a linked list. Include a main...
write a java program to Implement a Priority Queue using a linked list. Include a main method demonstrating enqueuing and dequeuing several numbers, printing the list contents for each.
Write a program where you- 1. Create a class to implement "Double Linked List" of integers....
Write a program where you- 1. Create a class to implement "Double Linked List" of integers. (10) 2. Create the list and print the list in forward and reverse directions. (10)
C++ program Complete the following functions for linked list. You are not allowed to alter the...
C++ program Complete the following functions for linked list. You are not allowed to alter the names or the function prototypes. #ifndef _ULL #define _ULL #include <iostream> #include "nodeType.h" using namespace std; void initializeList(nodeType *&head, nodeType *&tail, int&count); //Initialize the list to an empty state. //Postcondition: head = NULL, tail = NULL, count = 0; bool isEmptyList(const nodeType *head) ; //Function to determine whether the list is empty. //Postcondition: Returns true if the list is empty, // otherwise it returns false. void print(const...
In python: implement a singly linked list with following functions: - add_head(e) - add_tail(e) - find_3rd_to_last()...
In python: implement a singly linked list with following functions: - add_head(e) - add_tail(e) - find_3rd_to_last() - returns element located at third-to-last in the list - reverse() - reveres the linked list, note, this is not just printing elements in reverse order, this is actually reversing the list
(Write a C# program DO NOT USE CLASS)Implement the merge sort algorithm using a linked list...
(Write a C# program DO NOT USE CLASS)Implement the merge sort algorithm using a linked list instead of arrays. You can use any kind of a linked structure, such as single, double, circular lists, stacks and/or queues. You can populate your list from an explicitly defined array in your program. HINT: You will not be using low, middle and high anymore. For finding the middle point, traverse through the linked list while keeping count of the number of nodes. Break...
Write a java program that can create, read, and append a file. Assume that all data...
Write a java program that can create, read, and append a file. Assume that all data written to the file are string type. One driver class and a class that contains the methods. The program should have three methods as follows: CreateFile - only creating a file. Once it create a file successfully, it notifies to the user that it creates a file successfully. ReadingFile - It reads a contents of the file. This method only allow to read a...
In this problem, you will write a program that reverses a linked list. Your program should...
In this problem, you will write a program that reverses a linked list. Your program should take as input a space-separated list of integers representing the original list, and output a space-separated list of integers representing the reversed list. Your algorithm must have a worst-case run- time in O(n) and a worst-case space complexity of O(1) beyond the input. For example, if our input is: 5 7 1 2 3 then we should print: 3 2 1 7 5 Please...
Java Write a menu driven program that implements the following linked list operations : INSERT (at...
Java Write a menu driven program that implements the following linked list operations : INSERT (at the beginning) INSERT_ALPHA (in alphabetical order) DELETE (Identify by contents, i.e. "John", not #3) COUNT CLEAR
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT