Question

a. You have to write the steps that we need to insert a new node as the head of an existing linked list.

b.You have to write the code in c++ programming language of the function that we need to insert a new node in the end of an existing node.

c.Suppose that the below main function is executed correctly and all the functions that are invoked are imported from functions.h file. Explain.

int main(){
Node *head=NULL;
insertEnd(&head,"John");//inserts a new node in the end of the list
insertBeg((&head,"Tom");//inserts a new node in the beginning if the list
insertEnd(&head,"Kim");
insertAfter(head->next->next,"Sarah");//inserts a new node after a node
insertEnd(&head,"Jenna");
insertBeg((&head,"Daniel");
insertAfter(head->next->next,"Damon");
insertAfter(head->next->next->next->next,"Dario");
display(head);//it shows the elements of the list from head to tail
return 0;
}
  

Answer 1

#include <iostream>
#include <string>
using namespace std;

// Defines class Node
class Node
{
public:
// To store data
string data;
// To point to next node
Node *next;
};// End of class

// Function to insert a node at the beginning
void insertBeg(Node **headNode, string insData)
{
// Dynamically creates a new node
Node* newNode = new Node();

// Assigns parameter data to new node data
newNode->data = insData;

// Newly created node next points to head node
newNode->next = *headNode;

// Now head node points to the newly created node
*headNode = newNode;
}// End of function

// Function to insert a node after given parameter currentNode
void insertAfter(Node *currentNode, string insData)
{
// Checks if parameter current Node is NULL then
// cannot insert node at previous location
if(currentNode == NULL)
{
cout<<"\n ERROR: Node is NULL cannot insert after.";
return;
}// End of if condition

// Dynamically allocates memory to create a new node
Node *newNode = new Node();

// Assigns parameter data to newly created node
newNode->data = insData;

// Newly created next points to current node next
newNode->next = currentNode->next;

// Current node next points to new node
currentNode->next = newNode;
}// End of function

// Function to insert a node at the end of the single linked list
void insertEnd(Node **headNode, string insData)
{
// Dynamically allocates memory to create a new node
Node *newNode = new Node();
// Creates a temporary node which points to head node
Node *lastNode = *headNode;

// Assigns parameter data to newly created node
newNode->data = insData;

// Assign NULL to newly created node next (because it is the last node)
newNode->next = NULL;

// Checks if head node is equals to NULL then it is the first node to insert
if(*headNode == NULL)
{
// Assigns new node to head node
*headNode = newNode;
return;
}// End of if condition

// Loops till end of the list
while(lastNode->next != NULL)
// Move to next node
lastNode = lastNode->next;

// Last node next points to new node
lastNode->next = newNode;
return;
}// End of function

// Function to display the single linked list data
void display(Node *headNode)
{
// Checks if head node is equals to NULL then empty list
if(headNode == NULL)
{
cout<<"\n ERROR: Empty Single Linked List.";
return;
}// End of if condition

// Loops till end of the single linked list
while(headNode != NULL)
{
// Displays current node data
cout<<" "<<headNode -> data;
// Move to next node
headNode = headNode->next;
}// End of while loop
}// End of function

// main function definition
int main()
{
// Creates a head node
Node *head = NULL;
insertEnd(&head,"John");//inserts a new node in the end of the list
insertBeg(&head,"Tom");//inserts a new node in the beginning if the list
insertEnd(&head,"Kim");
insertAfter(head->next->next,"Sarah");//inserts a new node after a node
insertEnd(&head,"Jenna");
insertBeg(&head,"Daniel");
insertAfter(head->next->next,"Damon");
insertAfter(head->next->next->next->next,"Dario");
display(head);//it shows the elements of the list from head to tail
return 0;
}// End of main function
Sample Output:

Daniel Tom John Damon Kim Dario Sarah Jenna