Answer:
Check the explanation
Explanation:
#include<iostream>
using namespace std;
class LinkedList
{
private:
// Declare a structure for the list.
struct ListNode
{
int value; // The value in this node.
struct ListNode *next;// To point to the next node.
};
ListNode *head; // List head pointer.
public:
// Constructor.
LinkedList()
{ head = NULL; }
// Destructor
~LinkedList();
// Linked list operations.
void appendNode( int );
void insertNode( int );
void insertNodeAt(int,int);
void deleteNode( int );
void Reverse();
void deleteAt(int);
int Search(int);
void display() const;
};
// appendNode appends a node containing the
// value passed into num, to the end of the list.
void LinkedList::appendNode( int num )
{
ListNode *newNode; // To point to a new node.
ListNode *nodePtr; // To move through the list.
// Allocate a new node and store num there.
newNode = new ListNode;
newNode->value = num;
newNode->next = NULL;
// If there are no nodes in the list.
// make newNode the first node.
if ( !head )
head = newNode;
else // Otherwise, insert newNode at end.
{
// Initialize nodePtr to head of list.
nodePtr = head;
// Find the last node in the list.
while ( nodePtr->next )
nodePtr = nodePtr->next;
// Insert newNode as the last node.
nodePtr->next = newNode;
} // end else-if
display();
} // end function appendNode
// displayList shows the value stored in each
// node of the linked list pointed to by head.
void LinkedList::display() const
{
ListNode *nodePtr; // To move through the list
if ( !head )
{
cout << "\n\tThe list is empty.";
return;
}
// Position nodePtr at the head of the list.
nodePtr = head;
cout << "\n\n\tThe elements in the list are:\n\t";
// While nodePtr points to a node, traverse the list.
while (nodePtr)
{
// Display the value in this node.
cout << nodePtr->value << " -> ";
// Move to the next node.
nodePtr = nodePtr->next;
} // end while.
cout << "Null";
} // end function displayList.
// Reverse function re-arranges node in the list.
void LinkedList::Reverse()
{
ListNode *nodePtr;
ListNode *next;
ListNode *result=NULL;
if ( !head )
{
cout << "\n\tThe list is empty.";
return;
}
// Position nodePtr at the head of the list.
nodePtr = head;
while (nodePtr!=NULL)
{
next=nodePtr->next;
nodePtr->next=result;
result=nodePtr;
nodePtr=next;
}
head=result;
display();
}
// The insertNode function inserts a node with num copied to its value member.
void LinkedList::insertNode( int num )
{
ListNode *newNode; // A new node.
ListNode *nodePtr; // To traverse the list.
ListNode *previousNode = NULL; // The previous node.
// Allocate a new node and store num there.
newNode = new ListNode;
newNode->value = num;
newNode->next = NULL;
// If there are no nodes in the list make newNode the first node.
if ( !head )
head = newNode;
else // Otherwise, insert newNode.
{
// Position nodePtr at the head of list.
nodePtr = head;
// Initialize previousNode to NULL.
previousNode = NULL;
// Skip all nodes whose value is less than num.
while ( nodePtr != NULL && nodePtr->value < num )
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
//If the new node is to be the 1st in the list,
// insert it before all other nodes.
if ( previousNode == NULL )
{
head = newNode;
newNode->next = nodePtr;
}
else // Otherwise insert after the previous node.
{
previousNode->next = newNode;
newNode->next = nodePtr;
}
} // end else-if
display();
} // end function insertNode.
// The insertNode function inserts a node at pos
//with num copied to its value member.
void LinkedList::insertNodeAt( int num ,int pos)
{
ListNode *newNode; // A new node.
ListNode *nodePtr; // To traverse the list.
ListNode *previousNode = NULL; // The previous node.
int i=0;
// Allocate a new node and store num there.
newNode = new ListNode;
newNode->value = num;
newNode->next = NULL;
// Position nodePtr at the head of list.
nodePtr = head;
if(pos==0)//to inserted at first.
{
newNode->next=head;
head=newNode;
}
else
{
while(nodePtr != NULL && i<pos) //loop to reach position.
{
previousNode=nodePtr;
nodePtr=nodePtr->next;
i++;
}
if(nodePtr==NULL)//position not found.
cout<<"Invalid Position :"<<endl;
else//inserts node.
{
newNode->next=nodePtr;
previousNode->next=newNode;
}
}
display();
}
// The deleteNode function searches for a node with num as its value.
//The node, if found, is deleted from the list and from memory.
void LinkedList::deleteNode( int num )
{
ListNode *nodePtr; // To traverse the list.
ListNode *previousNode;//To point to the previous node.
// If the list is empty, do nothing.
if ( !head )
{
cout << "\n\tFailed to delete as list is empty.";
return;
}
// Determine if the first node is the one.
if ( head->value == num )
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
// Initialize nodePtr to head of list.
nodePtr = head;
// Skip all nodes whose value member is not equal to num.
while (nodePtr != NULL && nodePtr->value != num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
