Design and implement an ordered or non-ordered dynamic linked list using C++ cla
ID: 3736065 • Letter: D
Question
Design and implement an ordered or non-ordered dynamic linked list using C++ classes including the following methods:
o isEmpty ( ) - returns an integer or bool type; true for an empty list, false for non-empty list
o insertAtFront ( ) – allocates a node dynamically; initializes it to the data passed in; inserts the node at the front of the list only; returns true or false for successful or unsuccessful insertion, respectively
o insertAtEnd ( ) - allocates a node dynamically; initializes it to the data passed in; inserts the node at the tail or end of the list only; returns true or false for successful or unsuccessful insertion, respectively
o insertInOrder ( ) - allocates a node dynamically; initializes it to the data passed in; inserts the node in the list in ascending or descending order only; returns true or false for successful or unsuccessful insertion, respectively
o deleteNode ( ) – de-allocates a node dynamically; returns true if node was de-allocated, false otherwise o printList ( ) – prints out the data in each node of the list; may be printed iteratively or recursively
Explanation / Answer
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
class LinkdList
{
Node *headptr;
public:
LinkdList()
{
headptr=NULL;
}
bool isEmpty()
{
return headptr == NULL;
}
void insertAtFront(int data)
{
Node *newNode = new Node;
newNode ->next =NULL;
newNode ->data = data;
newNode ->next=headptr;
headptr = newNode;
}
void insertAtEnd(int data)
{
// Creates a temp node to hold the last node and set last's data and next
Node *last = new Node;
last->data = data;
last->next = NULL;
// If the linked list is empty then set head = last
if (headptr == NULL) {
headptr = last;
} else {
// Creates a temp node and sets it to head
Node *temp = new Node;
temp = headptr;
// Uses temp to find the last node
while (temp->next != NULL) {
temp = temp->next;
}
// Appends the last node with last
temp->next = last;
}
}
void insertInOrder (int data)
{
// creating the new node
Node *newNode = new Node;
newNode ->next =NULL;
newNode ->data = data;
Node* current;
/* Special case for the head end */
if (headptr == NULL || headptr->data >= data)
{
newNode->next = headptr;
headptr = newNode;
}
else
{
/* Locate the node before the point of insertion */
current = headptr;
while (current->next!=NULL &&
current->next->data < data)
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
void deleteNode()
{
Node *temp = headptr->next;
headptr->data = temp->data;
headptr->next = temp->next;
delete temp;
}
void display()
{
Node *disNode;
disNode = headptr;
cout<<"Display Node Value is "<<endl;
while(disNode !=NULL)
{
cout<<disNode->data<<"->";
disNode = disNode->next;
}
cout<<endl;
}
};
int main()
{
LinkdList linkedList;
while(true)
{
int choice;
cout<<"Enter 1 to check LinkdList is empty"<<endl;
cout<<"Enter 2 to insert at front"<<endl;
cout<<"Enter 3 to insert at end"<<endl;
cout<<"Enter 4 to insert at order"<<endl;
cout<<"Enter 5 to delete the node"<<endl;
cout<<"Enter 6 to display node"<<endl;
cout<<"Enter 7 to quit"<<endl;
cin>>choice;
if(choice == 7)
{
break;
}
switch(choice)
{
case 1: {
bool res = linkedList.isEmpty();
if(res)
{
cout<<"Linked list is enpty"<<endl;
}
else
{
cout<<"Linked list is not empty"<<endl;
}
}
break;
case 2: {
int data;
cout<<"Enter the data to add in LinkdList"<<endl;
cin>>data;
linkedList.insertAtFront(data);
}
break;
case 3:{
int data;
cout<<"Enter the data to add in LinkdList"<<endl;
cin>>data;
linkedList.insertAtEnd(data);
}
break;
case 4:{
int data;
cout<<"Enter the data to add in LinkdList"<<endl;
cin>>data;
linkedList.insertInOrder(data);
}
break;
case 5:
linkedList.deleteNode();
break;
case 6:
linkedList.display();
break;
default:
break;
}
}
return 0;
}
//PLEASE PROVIDE FEEDBACK THUMBS UP
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.