Josephus Problem Using Singly Circular Linked List in Data Structure Using C++

on

Data Structure Using C++

List Data Structure

Josephus Problem Using Singly Circular Linked List

class node
{
 private:
  int data;
  node *next;
 public:
  node(int);
  void set(int);
  int get();
  void setNext(node *);
  node* getNext ();
  void showData();
};
node::node(int x)
{
 set(x);
 next=NULL;
}
void node::set(int x)
{
 data=x;
}
int node::get()
{
 return data;
}
void node::setNext(node *ptr)
{
 next=ptr;
}
node* node::getNext()
{
 return next;
}
void node::showData()
{
 cout<<get()<<"\t";
}
class LinkedList{
 private:
  node* headNode;
  node* currentNode;
  int size;
 public:
  LinkedList();
  void start();
  void next();
  int get();
  int length();
  void add(int d);
  void update(int d);
  void remove();
  void find(int d);
  void showList();
};
LinkedList::LinkedList(){
 headNode=NULL;
 currentNode=NULL;
 size=0;
}
void LinkedList::start(){
 currentNode=headNode; 
}
void LinkedList::next(){
 if(currentNode->getNext()!=NULL){
  currentNode=currentNode->getNext();
 }
}
int LinkedList::get(){
 if(currentNode!=NULL){
  return currentNode->get();
 }
}
int LinkedList::length() 
{  
 return size;  
}
void LinkedList::add(int d) 
{ 
    node* newNode=new node(d); 
    if(size==0){
     currentNode=newNode;
     headNode=newNode;
     currentNode->setNext(headNode);
 }
 else{
        newNode->setNext(currentNode->getNext());
        currentNode->setNext(newNode);
        currentNode = newNode;
 }
    size ++;
}
void LinkedList::update(int d){
 if(currentNode!=NULL){
  currentNode->set(d);
 }
}
void LinkedList::remove() {
 if(currentNode!=NULL){
  if(currentNode!=headNode){
   node* ptr;
   ptr=headNode;
   while(ptr->getNext()!=currentNode){
    ptr=ptr->getNext();
   }
   ptr->setNext(currentNode->getNext());
   currentNode=ptr;
   size--; 
  }
  else{
   currentNode=currentNode->getNext();
   node* ptr;
   ptr=headNode;
   while(ptr->getNext()!=headNode){
    ptr=ptr->getNext();
   }
   ptr->setNext(currentNode);
   headNode=currentNode;  
   size--;
  }
 }
 else{
  cout<<"List is empty";
 }
}
void LinkedList::find(int d){
 node* ptr;
 ptr=headNode;
 do{
  if(ptr->get()==d)
  {
   cout<<"Value is found"<<endl;
  }
  else
  {
   cout<<"Value is not found!"<<endl;
  }
  ptr=ptr->getNext();
 }while(ptr!=headNode);
 
}
void LinkedList::showList(){
 node* ptr;
 ptr=headNode;
 do{
  ptr->showData();
  ptr=ptr->getNext();
 }while(ptr!=headNode);
 cout<<endl;
}
int main(){
 LinkedList l;
 for(int i=1;i<=10;i++)
 {
  l.add(i);
 }
 l.showList();
 cout<<endl;
 int m=3;
 l.start();
 while(l.length()>1)
 {
  int i;
  for(i=0;i<m;i++)
  {
   l.next();
  }
  l.remove();
 }
 cout<<"Leader is : ";
 l.showList();
}

Let me know in the comment section if you have any question.

Previous Post:
List Data Structure Using Singly Circular Linked List In C++

Comments

Post a Comment