linked list with no duplicates

Question

I have the following code (correct for my simple tests) for a linked list for no duplicates, but I think it is a bit ugly.

Could anyone recommend a cleaner way to handle the duplicate code? The current piece in question is:

if( (val == cur->val) || (cur->next && (val == cur->next->val)) )

But I think that a better solution might exist (that I don't see) using a different use of comparison operators.

Also, can someone give me a suggestion for a "useful" assert or to inside here. It is hard to tell when to assert, especially if you have an if statement doing it for you.

struct Node 
{
    Node(int v):val(v),next(NULL){}
    int val;
    Node * next;
};

void insert(Node ** ppHead, const int val)
{
    if(ppHead == NULL)
     return;
    if(*ppHead == NULL || val < (*ppHead)->val)
    {
     Node * tmp = new Node(val); // new throws
     tmp->next = *ppHead;
     *ppHead = tmp;
    }
    else
    {
     Node * cur = *ppHead;
     while(cur->next && (val > cur->next->val))
      cur = cur->next;

     if( (val == cur->val) || (cur->next && (val == cur->next->val)) )
      return;

     Node * tmp = new Node(val); // new throws
     tmp->next = cur->next;
     cur->next = tmp;
    }
    return;
}


int _tmain(int argc, _TCHAR* argv[])
{
    Node * list = NULL;
    int x[] = { 5, 4, 6, 7, 1, 8, 1, 8, 7, 2, 3, 0, 1, 0, 4, 9, 9 };
    int size = sizeof(x) / sizeof(x[0]);
    for(int i = 0; i < size; i++)
     insert(&list, x[i]);
    Node * cur = list;
    while(cur) {
     printf (" %d", cur->val);
     cur = cur->next;
    }
    printf("\n");
    return 0;
}

Answer 1

I would add a method to Node to perform the find operation (*untested code):

Node* Find(int value)
{
    if( this.val == value ) return this;
    if( this.next == null ) return null;
    return next.Find(value);
}

Then prior to insertion you want to check for existence:

if( null == _head || null == _head.Find(value) )
    ... add value ...

Answer 2

I would write this more like:

void insert(Node ** ppHead, const int val)
{
    if (ppHead == NULL)
        return;
    while (*ppHead && (*ppHead)->val < val)
        ppHead = &(*ppHead)->next;
    if (*ppHead && (*ppHead)->val == val)
        return;
    Node * tmp = new Node(val); // new throws
    tmp->next = *ppHead;
    *ppHead = tmp;
}

Answer 3

Would this work?

// Note the change from > to >=
while(cur->next && (val >= cur->next->val))
{   cur = cur->next;
}

if (val == cur->val)
{   return;
}

Answer 4

Well, first, if you're using this for production code, you should probably be using std:: if that's an option.

The more I think about your code, the more I think that you should be keeping two pointers. Basically one to the current Node and one to the previous Node. If cur == NULL, insert after prev. If cur->value == val, return. Then you can check if cur->value < val and if so, advance both nodes.

You currently have special code to handle *ppHead == NULL. However, this isn't necessary if you have prev as Node** curPtr instead. So start with curPtr=ppHead and cur=*curPtr. Then the above algorithm should work for the whole thing.

Or as the person that just posted coded for you, you can use ppHead as the curPtr variable itself and (*ppHead) as cur. Not sure which is more readable.