3
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ In the future please indent your code by 4 spaces or use the code button (the one with the ones and zeros) to properly format your code. \$\endgroup\$ – sepp2k Mar 27 '11 at 2:06
  • \$\begingroup\$ It's difficult to give a full review of your code without seeing your definition of node. \$\endgroup\$ – CB Bailey Mar 27 '11 at 10:26
  • \$\begingroup\$ This program has a bug. If I want to delete the first node, it will not work. This is wrong: prev=first=null prev.next !=null \$\endgroup\$ – user22920 Mar 8 '13 at 5:09
  • \$\begingroup\$ This code looks more like C than C++ to me \$\endgroup\$ – Siobhan Dec 4 '16 at 16:03
10
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ All the above, and don't malloc a new node for previous in the first place. Instead, check if previous is still NULL once you found the node to be deleted. If it is, assign first = first->next to delete the first node. \$\endgroup\$ – David Harkness Mar 27 '11 at 7:31
  • \$\begingroup\$ To back this point up it's worth noting that if you use malloc to create instances of C++ objects, then the constructors won't get called. You'd have to use "placement new" manually after allocating the memory. This holds for destruction as well (ie. free doesn't call destructors). \$\endgroup\$ – OJ. Mar 8 '13 at 22:27