Deleting a linked list node

Question

This is a classic linked list problem.

1. Deleting a node from linked list given the data to be deleted.
2. Inserting a node in a sorted linked list.

I saw various versions of this and here is my version. Could you check and let me know if this code is efficient?

void deletenode(struct node *&first, int data) 
{
    struct node * current = first;// first will have the node after deletion

    struct node * prev = (node *)malloc(sizeof(node));
    while(current!=NULL)
    {
        if(current->data!=data)
        {
            prev=current;
            current = current->next;
        }
        else
        {
            prev->next = current->next;
            delete current;
            break;
        }
    }
}

void insertinsortedlist(struct node *& first, int data)
{
    struct node * current = first;// first will have the node after insertion
    struct node * newnode = (node *)malloc(sizeof(node));
    newnode->data = data;
    struct node * temp = (node *)malloc(sizeof(node));
    while(current)
    {
        if((current->data < data) && (current->next->data > data))
        {
            temp = current->next;
            current->next = newnode;
            newnode->next = temp;
            break;
        }
        current = current->next;
    }
}

Answer 1

The efficiency of your algorithm is fine, however there are a couple of other things you should take care of:

First of all do not free memory, which was allocated with malloc, using delete. delete is for freeing memory which was allocated with new. To free malloced memory use free. Using delete on malloced memory is wrong and leads to undefined behavior.

Also there is almost never a good reason to use malloc in C++ code. If in doubt use new and delete.

Another serious bug in your code is that you allocate memory for prev in deletenode, but never free it.

---

I also don't see why you pass in first as a reference to a pointer. Since you never change first, I see no reason not to pass it in as a plain pointer (or a plain reference which you then take the address of to assign to current).

---

Another thing is that you don't need to add the struct keyword when declaring variables or parameters containing structs in C++ - that's a C thing. You should remove it as it only adds noise.