Bug in Programming Interviews Exposed: Linked Lists

Question

Hello, I was going through the Programming Interviews Exposed book. There's a code given for inserting an element at the front of linked lists.

bool insertInFront( IntElement **head, int data ){
    IntElement *newElem = new IntElement;
    if( !newElem ) return false;
    newElem->data = data;
    *head = newElem;
    return true;
}

IMHO this code forgets to update the next pointer of the new element, doesnt it ? Although I am sure the code is wrong, I just want to confirm my linked list concepts are not horribly wrong.

I believe the code should add the following line at the right place.

newElem->next = *head;

Can someone please just tell me whether I am right or wrong ?

Thanks!

Answer 1

Since this is inserting in the front, you're right. The new nodes's next should be the current head, then head should be set to point to the new node.

bool insertInFront( IntElement **head, int data ){
    IntElement *newElem = new IntElement;
    if( !newElem ) return false;
    newElem->data = data;
    newElem->next = *head;
    *head = newElem;
    return true;
}

Of course, there are several other things here that are bad style and design, or just plain wrong.

Answer 2

I'm not sure what kind of interview book you're reading, but this code example is terrible c++.

Yes, you need to point newElem->next to the old head before overwriting head. Also, there's no reason to check if newElem is NULL - if it couldn't be allocated, C++ throws an exception. Also, insertInFront should be a member function of IntElement, and head should be a data member.