problem in insert circular link list

[AbEeR Q8]

hi;

I'm trying to program a circular link list with a head node , I have a problem with insert function .

wanting to do it like this but with a head node
>> http://geeksforgeeks.org/wp-content/uploads/cll1.gif

this is my function ::

struct node{
       int data;
       node *next;
       node(int x,node *n=NULL){
           data=x;
           next=n;
          }  
       };

void insert (node *h,int d){
      node *p=h;
      while (p->next!=h && d>p->next->data)
             p=p->next;
      p->next =new node(d,p->next);
      }

[Tumlee]

What is the problem you're having?

Are you getting freezes? NULL-pointer access? Just some general crash? Is it not compiling?

[AbEeR Q8]

when I make a compiler and insert the first element the program stop working

#include<iostream>
using namespace std;
struct node {
       int data;
       node *next;
       node (int x,node *n=NULL){
           data=x;
           next=n;
          }  
       };
 
void insert (node *h,int d){
      node *p=h;
      while (p->next!=h && d>p->next->data)
             p=p->next;
      p->next =new node (d,p->next);
      }
void print2 (node *p,node *h){
     if( p->next==NULL)
        cout<<" NULL";
     else if(p!=h ){
        cout<<p->data<<" , ";
     print2 (p->next,h);}
     }
void print (node *h){
     print2(h->next,h);
     }
          
int main(){
    node *x=NULL;
    int a;
    
    for(int i=0;i<5;i++){
        cin>>a;
        insert(x,a);
        }
        
    print(x);

cout<<"\n\n";
system("pause");
return 0;
}

[Taywin]

You are passing a NULL value node *x=NULL; to the insert() function. Then in your insert() function, you attempt to access "next" from the NULL pointer? That's the problem. They are all NULL.

Do you have to pass in a node pointer to the insert() function? Is that one of your requirement for implementation?

[AbEeR Q8]

what about making the main like this

node *x=new node(1,NULL); ??

the idea of this program is having the ( head node \ dummy node ) in the first time
let call it (h)
h = p
h->next = p->next = NULL
and then we add the integers in the linked list in sorting way

http://cis.stvincent.edu/html/tutorials/swd/lists/listins.gif

[Taywin]

Nope, you should check if x is NULL first instead. If it is NULL, create a new node to x and set next to itself; otherwise, pass in the x and the data as in your original code. Hmm... You need a setNext() function here...

node *x=NULL;
int a;

for(int i=0;i<5;i++){
  cin>>a;
  if (x==NULL) {
    x = new node(a, NULL);
    x.setNext(x);  // to make it circular (need to implement setNext()
  }
  else {
    insert(x,a);
  }
}

[AbEeR Q8]

thanks a lot for helping , the program is running now
but it's ignore the first integer . Is it normal ??

#include<iostream>
using namespace std;
struct node {
       int data;
       node *next;
       node (int x,node *n=NULL){
           data=x;
           next=n;
          } 
      void setNext(node *h){
            next=h;
            }  
       };
 
void insert (node *h,int d){
      node *p=h;
      while (p->next!=h && d>p->next->data)
             p=p->next;
      p->next =new node (d,p->next);
      }
void print2 (node *p,node *h){
     if( p->next==NULL)
        cout<<" NULL";
     else if(p!=h ){
        cout<<p->data<<" , ";
     print2 (p->next,h);}
     }
void print (node *h){
     print2(h->next,h);
     }
 
int main(){
    node *x=NULL;
    int a;
 
    for(int i=0;i<5;i++){
        cin>>a;
        if (x==NULL) {
            x = new node(a, NULL);
            x->setNext(x); 
            }
        else 
          insert(x,a);
        }
 
    print(x);
 
cout<<"\n\n";
system("pause");
return 0;
}

[Taywin]

No, it is not normal. It seems that your print() function is not working correctly.

In a circular linked list, there shouldn't be NULL for "next" because the ending is always pointing to the head. In your print(), you could actually implement a while loop in there instead of having print2().

void print (node *h) {
  if (h!=NULL) {  // print out if the list is not empty
    cout << h->data << "  ";
    node *current = h->next;
    while (current!=h) {  // exit if it comes back to head
      ...  // display & move to the next node
    }
  }
  else {
    // display the message that the list is empty
  }
}

[raptr_dflo]

Or simply call print2(h, h); from print(), so that you don't skip the first node....

[AbEeR Q8]

thank you for helping me
the program is running now Successfully
I change the place of ( if statement ) in the main
and use the recursive function in writing ( insert function )

#include<iostream>
using namespace std;
struct node {
       int data;
       node *next;
       node (int x,node *n=NULL){
           data=x;
           next=n;
          } 
      void setNext(node *h){
            next=h;
            }  
       };
 
void insert2(node *h,node *p,int t){
     if( (p->next!=h) && (t>p->next->data) )
        insert2 (h,p->next,t);
      else
          p->next=new node (t,p->next);
      }
void insert (node *h,int t){
     insert2(h,h,t);
     }

void print2 (node *p,node *h){
     if(p!=h){
        cout<<p->data<<" , ";
        print2 (p->next,h);
        }
     }
void print (node *h){
     print2(h->next,h);
     }
 
int main(){
    node *x=NULL;
    int a=-99;
 
    if (x==NULL){
       x=new node(a,NULL);
       x->setNext(x);
       }

    for(int i=0;i<5;i++){
        cin>>a; 
        insert(x,a);
        }
 
    print(x);
 
cout<<"\n\n";
system("pause");
return 0;
}

[raptr_dflo]

Please mark your thread as "solved" when you're finished with it. Thanks!