sorted insert

[cash]

I need to insert a node into a sorted link list, but I'm getting errors. Can someone help with whats wrong?

struct NodeType
{
ItemType value;
NodeType * next;
}

  void sortedInsert( NodeType * & head, int data )
{
    NodeType * p = head;
    NodeType * prev = NULL;
    while (p->value < data)
    {
        prev = p;
        p= p -> next;
    }
    NodeType * newnode = new NodeType;
    newnode -> value = data;
    newnode -> next = prev;
    p -> next = newnode ;
}

[salem c]

What about the two special cases?
- when the list is empty, and head is NULL.
- when the data to add is before the first entry in the list, and you need to move head to a new node.

[dhayden]

You can handle both special cases that salem c brings up by using a pointer to pointer to NodeType. This points to head, or to the "next" pointer of a node. I'll call it headOrNext to be clear:

void sortedInsert( NodeType * & head, int data )
{
    NodeType **headOrNext;
    NodeType * p;
    for (headOrNext = &head, p = *headOrNext; headOrNext = &p->next) {
        if (p->value < data) break;
    }
    NodeType * newnode = new NodeType;
    newnode -> value = data;
    newnode -> next = p;
    *headOrNext = newnode;
}