Question

ONLY looking for part B!! a. Using C++, define a node structure of the linked list (e.g. value is an integer, next is a node type pointer), construct a linked list of 10 nodes and assign random numbers as the nodes’ values. Use loop to track and print from the first node to the last and output all nodes’ values. Finally, free all memories of the linked list. b. Based on 2.a, (1) define a function which takes the header as parameter, the function will create a new node and assign its value 100; then insert this node at the sixth position of the list; (2) define another function which recursively print the list forwards to verify the result; (3) define the 3rd function which takes the header as parameter, the function will delete the eighth node of the list to keep the linked list having 10 nodes, and (4) define the 4th function which recursively to print the linked list backwards. After creating the four functions, revise your program 2.a, before delete all memories of the list, call the four functions in order to verify the results.

Answer 1

/*Program in C++*/

#include <iostream>
using namespace std; //declare namespace

int flag=0;
typedef struct node* n;    //use n instead of--struct node* using typedef keyword

struct node    //defining linked list structure
{
int data; //integer type value
struct node *next; //node type pointer
};

struct node *head=NULL; //global head pointer declaration

void printfwd(n node) //recursion (forward traversal)
{
if(node==NULL) //for no node, return
return;
cout<<node->data; //print node data
if(node->next!=NULL) //check if next node is null(remove -> from last node)
cout<<"->";
printfwd(node->next);     //calling recursively by passing the next node
}

void printbwd(n node)    //recursion (backward traversal)
{
if(node==NULL)   //for no node, return
return;
printbwd(node->next); //calling recursively by passing the next node
cout<<node->data;    //print node data
if(node!=head)
cout<<"->"; //check if next node is null(remove -> from last node)
}

void insert(int x) //insertion at the beginning
{
struct node *temp=(struct node*)malloc(sizeof(struct node*));
struct node *k=head;
temp->data=x;
if(head==NULL)
{
head=temp;
}
else
{
while(k->next!=NULL)
k=k->next;
k->next=temp;
}
temp->next=NULL;
}

void insertSix(n header) //insertion at the nth position
{
n temp=(n)malloc(sizeof(n)); //create a new node using malloc
struct node *k=header; //use header pointer
temp->data=100; //assign data value 100 to node
for(int i=1;i<5;i++) //find the position of 6th node using loop
k=k->next;
temp->next=k->next;       //new node's(temp's) next to be next of existing 5th node
k->next=temp; //existing 5th node's next is new node (temp)

}

void deleteEight(n header) //deletion at the nth position
{
n temp=header; //using header pointer for head
for(int i=1 ; i<7 ;i++ ) //move to 8th position node
temp=temp->next;
temp->next=temp->next->next; //pointer of 7th node now points to 9th node
}

void display() //displaying the linked list
{
struct node *temp=head;
while(temp!=NULL)
{
cout<<temp->data;
if(temp->next!=NULL)
cout<<"->";
temp=temp->next;
}
cout<<endl;
}

void freeMem(n head)
{
n temp; //a temporary pointer of node type

while (head != NULL) //check till head isn't null
{
temp = head; //assign head to temp;
head = head->next; //move to next node
free(temp); //free memory pointed by temp
}

}

int main ()
{
  
insert(2); //insertion at the beginning
insert(3);
insert(4);
insert(6);
insert(4);
insert(5);
insert(3);
insert(5);
insert(8);
insert(8);
display();
  
insertSix(head); //insert node with value 100 at sixth position
// display();
  
printfwd(head); //recursion print forward
cout<<endl;

deleteEight(head); //delete node from the 8th postion
display();

printbwd(head); //recursion print backwards
cout<<endl;
  

  freeMem(head); //free the memory of the list
return 0;
}
/*OUTPUT

2->3->4->6->1->5->8->9->7->0
2->3->4->6->1->100->5->8->9->7->0
2->3->4->6->1->100->5->9->7->0
0->7->9->5->100->1->6->4->3->2

*/

/* Screenshot of the Code & Output */