1

The code below is from the book Programming Interviews Exposed 4th, now, to fix this, there are two possible ways,

bool insertInFront( IntElement *head, int data ){
    IntElement *newElem = malloc( sizeof(IntElement) );
    if ( !newElem ) return false;

    newElem->data = data;
    newElem->next = head;
    head = newElem; // Incorrect! Updates only the local head pointer
    return true;
}

The first way is to give a pointer to pointer as is suggested and taken from the book again...

bool insertInFront( IntElement **head, int data ){
    IntElement *newElem = malloc( sizeof(IntElement) );
    if ( !newElem ) return false;

    newElem->data = data;
    newElem->next = *head;
    *head = newElem;
    return true;
}

The second way is where I simply dereference the head to update it's value by assigning the value dereferenced from the newElem.

bool insertInFront( IntElement *head, int data ){
    IntElement *newElem = malloc( sizeof(IntElement) );
    if ( !newElem ) return false;

    newElem->data = data;
    newElem->next = head;
    *head = *newElem; // <---------- check this line here!
    return true;
}

my question is that is there any difference between doing it with pointer to pointer or simply updating the value pointed to, strictly in context to the use case of linked lists.

4

2 回答 2

2

In a strict context to doubly linked lists in C, which is the right way to insert an element?

For starters it seems you mean a singly-linked list instead of a doubly-linked list because neither provided code deals with a doubly-linked list.

You need to update the pointer head that the first function performs because the pointer head is passed to the function by reference (through a pointer to it) and dereferencing the parameter that accepts a pointer to the pointer head the function has a direct access to the pointer head.

As for this function

bool insertInFront( IntElement *head, int data ){
    IntElement *newElem = malloc( sizeof(IntElement) );
    if ( !newElem ) return false;

    newElem->data = data;
    newElem->next = head;
    *head = *newElem; // <---------- check this line here!
    return true;
}

then it does not do that, It tries to assign the node pointed to by the pointer head with the dynamically allocated node pointed to by the pointer newElem.

Pay attention to that the expression *head yields an object of the type IntElement that is a node instead of a pointer to a node.

As a result the function can invoke undefined behavior when head is equal to NULL due to dereferencing a null pointer. Moreover it has a memory leak because the dynamically allocated memory is not freed and its address will be lost after exiting the function. And it does not insert a new node. Instead it tries to change already existent node pointed to by the pointer head.

As for a doubly-linked list then the function can look the following way provided that there is no one more declared structure that indeed defines a doubly-linked list by having pointers to the head and tail nodes.

bool insertInFront( IntElement **head, int data )
{
    IntElement *newElem = malloc( sizeof( IntElement ) );
    bool success = newElem != NULL;

    if ( success )
    {
        newElem->data = data;
        newElem->prev = NULL;
        newElem->next = *head;
        if ( *head ) ( *head )->prev = newElem;
        *head = newElem;
    }

    return success;
}
于 2021-01-26T23:11:06.140 回答
0

The third way - avoiding side effects.

IntElement *insertInFront( IntElement *head, int data )
{
    IntElement *newElem = malloc( sizeof( *newElem ) );
    bool success = newElem != NULL;

    if ( success )
    {
        newElem->data = data;
        newElem->prev = NULL;
        newElem->next = head;
        if(head) head -> prev = newElem;
    }
    return newElem;
}

and in the calling function

IntElement *newHead = insertInFront(head, data);
if(newHead) head = newHead;
else {/* error handling*/}

also note the use of the object instead of type in sizeof:

    IntElement *newElem = malloc( sizeof( *newElem ) );

It is safer - if you change the type you do not have to change all the sizeof`s in your code.

于 2021-01-26T23:43:33.430 回答