DSA Assignment Linked Lists

In this blog post, we will explore the implementation of a singly linked list using C++ programming language. We will start by creating a linked list of whole numbers and display its elements using appropriate member functions. Then, we will introduce the concept of loops or cycles in linked lists and create a loop in the previously created linked list using a member function. We will then detect and resolve the loop using another member function and demonstrate the removal of the loop by printing the elements of the linked list. Through this implementation, we will learn about the fundamentals of linked lists and their various operations.

Here is the DSA Assignment for Linked Lists

Question :

write a C++ program that creates a singly linked list of some whole numbers such as the one given as follows:

Next, display the elements of the linked list by implementing and calling appropriate member functions. Make use of another member function named CreateLoop( ) that takes the index as a single parameter representing the position of the node that should be set as the next node of the last node in the linked. For instance, passing 1 as an index to the CreateLoop( ) member function should modify the aforementioned linked list as follows thereby forming a loop/cycle. Print elements of the linked list once more demonstrating the formation of a loop/cycle.

Make use of another member function to Detect & Resolve the loop. The function should return false if no loop is detected. After resolving the loop, print the elements of the linked list demonstrating the removal of the loop (i.e., linked list should be loop-free).

Code:

Here is the DSA Assignment No 01 for Linked Lists

#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node* next;
};

class List
{
public:
Node* head;
int size;
int loop;
void InsertNode(int index, double x)
{
if (index < 0)
cout<<"ERROR…YOU ENTERED INVALID INDEX ";

int currIndex   =   1;
Node* currNode  =   head;
while (currNode && index > currIndex)
{
    currNode    =   currNode->next;
    currIndex++;
}


Node* newNode =new  Node;
newNode->data   =   x;  
if (index == 0)
{
    newNode->next   =   head;
    head        =   newNode;
    size++;
}
else 
{
    newNode->next   =   currNode->next;
    currNode->next  =   newNode;
    size++;
}
return;

}

void DisplayList()
{
   Node* currNode   =   head;
   cout << currNode->data<<" , ";
   while (currNode->next!= NULL){
    currNode=currNode->next;
    cout << currNode->data<<" , ";

   }
}
int sizet()
{
return size;
}
void DisplayLoop(int runtime)
{
   int num=0,inner=0;
   Node* currNode=head;
   cout << currNode->data<<" , ";
   while(num<runtime)
   {
    currNode=currNode->next;
    cout << currNode->data<<" , ";
    inner++;
    if(inner==sizet()-1)
        {
        num++;
        inner=0;
        }
    }
      cout<<"\n\nTHE LOOP HAS BEEN RUNNED "<<num<<" TIMES";    

}
void createloop(int index)
{
    if(!detectloop() && index<sizet())
    {
    int count = 0;
    Node* currNode = head;

    while(count<index)
    {
        currNode = currNode->next;
        count++;

    }

    Node* joint_point = currNode;
    while (currNode->next != NULL)
    {
        currNode = currNode->next;
    }

    currNode->next = joint_point;
    loop=index;
    }else{
        cout<<"THE LOOP CAN NOT BE MADE DUE TO THE INDEX EXCEEDING THE SIZE OF LIST.";
        return;
    }
}

bool detectloop ()
{
      Node* currNode    =   head;
   int count=0;
   while (count<sizet()-1){
    currNode=currNode->next;
   count++;
   }

   if(currNode->next)
    {
        return true;
     }else{
        return false;
    }

}
void resolveloop ()
{
Node* currNode = head;
int count=0;
while (countnext;
count++;
}

   if(currNode->next)
    {
    currNode->next=NULL;
    cout<<"\n\nTHE LOOP HAVE BEEN RESOLVED...";
    }else{

         cout<<"loop not found";
    }

}

};

int main()
{
List *a=new List();
a->InsertNode(0,2);
a->InsertNode(1,3);
a->InsertNode(2,4);
a->InsertNode(3,5);
a->InsertNode(4,7);
a->InsertNode(5,6);
a->DisplayList();
cout<createloop(1);
a->DisplayLoop(5);
a->detectloop();
a->resolveloop();
if(a->detectloop())
{
cout<<"\n\nTHE LOOP IS STILL PRESENT…";
}
else
{
cout<<"\n\nTHE LOOP IS NOT PRESENT NOW…";
}

}

For more details about Huffman coding click here

For other assignments and quizzes click here 

Output: