Question

Exercise-1:15 points Develop a node class and a singly list class. The node class should have two state variables namely data and nextNode. The singly list class should contain the following methods . Middlelnsert-insert a node somewhere in the middle of the list . Startinsert-insert a node at start of the Linked list Endinsert-insert a node at the end of the Linked list . Delete-delete a node Traverse-prints all the node's data Reverse -reverses the linked list Note: Choose appropriate inputs for the above functions You can refer any source but try to follow the algorithm described in the lecture-4 video (Feb 19th . class) . Write the algorithm for each function as comments in the program . Test the class's function with an example. Attach screenshots of the program and results

Answer 1

Code for the above problem :

#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *nextNode;
};
class SinglyList
{
private:
Node* head;
public:
SinglyList() // contructor to initialize head pointer to null
{ head=NULL; }

void StartInsert(int new_data)
{
Node* newNode;
newNode = new Node;
newNode->data = new_data;
newNode->nextNode = head;
head = newNode;
}
void MiddleInsert(int new_data)
{
if(head==NULL) // if no node then insert a new node
{
Node* newNode;
newNode = new Node;
newNode->data = new_data;
newNode->nextNode = NULL;
head = newNode;
}
else
{
int length=0;
Node *temp_pointer = head;
while(temp_pointer!=NULL) // calculating total length
{
length++;
temp_pointer = temp_pointer->nextNode;
}
int middle;
if(length%2==0) // calculating middle
middle = length/2;
else
middle = (length+1)/2;

temp_pointer = head;
while(middle>1) // Traversing while we reach the middle
{
middle--;
temp_pointer = temp_pointer->nextNode;
}
Node* newNode; // Inserting new node at middle
newNode = new Node;
newNode->data = new_data;
newNode->nextNode = temp_pointer->nextNode;
temp_pointer->nextNode = newNode;

}

}

void EndInsert(int new_data)
{
Node* newNode;
newNode = new Node;
newNode->data = new_data;
newNode->nextNode = NULL; // since inserted at last, next node will always be NULL
if(head==NULL)
head = newNode;
else
{
Node *temp_pointer = head;
while(temp_pointer->nextNode!=NULL)
temp_pointer = temp_pointer->nextNode;
temp_pointer->nextNode = newNode;
}

}
void Delete(int del_position)
{
if(head==NULL)
return;
Node *temp_pointer = head;
if(del_position ==1)
{
head = temp_pointer->nextNode;
}
else
{
for(int i=1;temp_pointer!=NULL && i<del_position-1;i++)
temp_pointer = temp_pointer->nextNode;
}
if(temp_pointer==NULL || temp_pointer->nextNode==NULL) // If user enter position more than number of nodes
{ cout<<"Invalid position\n"; return; }

Node *next_pointer = temp_pointer->nextNode->nextNode;
temp_pointer->nextNode = next_pointer;
}

void Reverse() // function to reverse a linked list
{
Node *current_pos = head;
Node *previous_pos = NULL;
Node *next_pos = NULL;
while(current_pos!=NULL) //traversing till end and modifying the nextNode pointers to point at previous node
{
next_pos = current_pos->nextNode;
current_pos->nextNode = previous_pos; // pointing current's nextNode to previous ie. reversing
previous_pos = current_pos; // previous_pos keeps moving forward
current_pos = next_pos; // current_pos also keeps moving forward and is ahead by previous by one.
}
                       head = previous_pos;
}

void Traverse() // to display all the nodes
{
Node *temp_pointer = head;
while(temp_pointer!=NULL) // printer till the pointer reaches null
{
cout<<temp_pointer->data<<" ";
temp_pointer = temp_pointer->nextNode;
}
cout<<endl<<endl;
}
};

int main()
{
SinglyList obj,obj1;
int number;
for(int i=1;i<=5;i++) //Inserting 5 nodes using using for loop and StartInsert function
obj.StartInsert(i);
cout<<"Displaying Linked List made using Start Insert(Inserted elements 1-5 will be printed in reverse order as inserted) : \n" ;
obj.Traverse();

cout<<"Insert a number to be inserted at middle : ";
cin>>number;
obj.MiddleInsert(number);

cout<<"After inserting element at middle, the new Linked List is as follows : \n";
obj.Traverse();

for(int i=5;i<=10;i++) //Inserting 5 nodes using using for loop and EndInsert function
obj1.EndInsert(i);
cout<<"Displaying new Linked List made using End Insert(Inserted elements 5-10 will be printed in order as inserted ) : \n" ;
obj1.Traverse();

int position;
cout<<"Enter the position(starting from 1) of node to be deleted : ";
cin>>position;
obj1.Delete(position);
obj1.Traverse();

cout<<"After reversing the new Linked List , the list looks as follows : \n";
obj1.Reverse();
obj1.Traverse();
}
  

INPUT :

1. For StartInsert method :- Used for loop to insert element 1,2,3,4,5

2. For MiddleInsert method :- Used previous list and user inputs a number.

3. For EndInsert method :- Used for loop to insert element 5,6,7,8,9,10

4. For Delete method :- User inputs a position to be deleted(Position start from 1)

5. Reverse and Traverse method : No inputs required from user.

Following screenshot shows all inputs and functions used :

SinglyList obj,objl: int number: for (int 1=l ; i<=5 i++) //Inserting 5 nodes using using for loop and StartInsert function obj.StartInsert (i) cout<<"Displaying Linked List made using Start Insert (Inserted elements 1-5 will be printed in reverse order as inserted) : \n" obj Traverse ) cout<<"Insert a number to be inserted at middle:": cin>>number obj.MiddleInsert (number) cout<<"After inserting eleent at middle, the new Linked List is as follows n" obj Traverseo for (int i-s;i<-10;i++) //Inserting 5 nodes using using for loop and EndInsert function objl.EndInsert (i) cout<<"Displaying new Linked List made using End Insert (Inserted elements 5-10 will be printed in order as inserted objl.Traverse ) n" int position: cout<<"Enter the position (starting from 1) of node to be deleted : ": cin>>position: obj1 Delete (position): obj1.Traverse ) cout<<"After reversing the new Linked List,the list looks as follows \n"; obj1.Reverse ) objl.Traverse )

OUTPUT :

1. Start Insert : Linked list with data 1,2,3,4,5 is displayed. Since it was inserted using StartInsert method, the result would be in reverse order.

2. Middle Insert: User enters 6 and 6 gets inserted at 4th position(middle)

3. End Insert : Linked list with data 5,6,7,8,9,10 is displayed. Since it was inserted using EndInsert method, the result is displayed in same order as inserted.

4. Delete : User enters 4. So 4th position ie. 8 gets deleted from the list.

5. Reverse : The remaining list gets reversed.

$./2.out Displaying Linked List made using Start Insert (Inserted elements 1-5 will be printed in reverse order as inserted) 5 43 21 Insert a number to be inserted at middle6 After inserting element at middle, the new Linked List is as follows 5 4362 1 Displaying new Linked List made using End Insert (Inserted elements 5-10 will be printed in order as inserted ): 5678 9 10 Enter the position (starting from 1) of node to be deleted 4 5 679 10 After reversing the new Linked List,the list looks as follows 10 976 5

Hope that helped.

Thanks.