Bool sorted insert function with check if int already exist in list

Question

I am trying to implement one bool function that receives List and Int as arguments and should insert int and return true if the int does not exist in the list, or false if it is already there, i have been working for several hours with this function, and the if-else statements can insert sorted int, the problem (and crash) is how to check if the value already exist and return false, here is my function: declaration of struct

typedef struct E_Type * List;
struct E_Type
 {
  int data;
  List next = 0;
 };

and function

bool insert(List & l, int data)
{   

   List current = l;
       do{//check if the int is already in the list
          current->data;
          current = current->next;
        //return false;
     }while (current->data == data);

      if (l == 0 || l->data > data){
              List new_list = new E_Type;
              new_list->data = data;
               new_list->next = l;
               l = new_list;
           return true;
      }

       else if(l->data < data){
             insert(l->next, data);
           return true;
     }



  }

Unless this is something like homework where you need to write all the code yourself, consider using a std::set, which already does almost exactly what you're trying to implement. — Jerry Coffin
yeah, i know about set, but this is a kind of homework/assignment/lab for one course — EmilDo
Okay -- glancing at the code, I don't see anything that looks like a check whether the next pointer is non-null, which is usually needed for traversing a linked list. — Jerry Coffin

femtoRgon femtoRgon · Accepted Answer · 2012-12-05T22:20:57

do{
      //this line doesn't really do anything...
      current->data;
      //moving current forward, good.
      current = current->next;
 //If current->data is less than data in the list, it will exit the loop here anyway.
}while (current->data == data);

You also aren't checking whether you have reached the end of the list. Perhaps what you are attempting to do is something like this:

//This is correct for for iterative approach, but I don't think this is really what you need, either...
while(current != null) {
    if (current->data == data)
        return false;
    current = current->next;
}

However, you probably don't want to use iteration like this to make this check in a recursive function, so instead, simply replace that whole bit with:

if (current->data == data)
   return false;

And to return the correct value through the recursive calls, you'll want to change:

else if(l->data < data){
     insert(l->next, data);         //Recursive call
     return true;  //you don't want to just return true, return what the recursive call returns!
}

To:

else if(l->data < data){
     return insert(l->next, data);
}

Bool sorted insert function with check if int already exist in list

1 Answers