CODEWITHSUNDEEP
cpointers
Hommer Smith
Hommer Smith

Reputation: 27852

Why not use pointer to pointer when adding an element to linked list?

I have seen this question:

Which uses the following code to add an element o a list: C linked list inserting node at the end

int addNodeBottom(int val, node *head){

    //create new node
    node *newNode = (node*)malloc(sizeof(node));

    if(newNode == NULL){
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(-1);
    }

    newNode->value = val;
    newNode->next = NULL;  // Change 1

    //check for first insertion
    if(head->next == NULL){
        head->next = newNode;
        printf("added at beginning\n");
    }

    else
    {
        //else loop through the list and find the last
        //node, insert next to it
        node *current = head;
        while (true) { // Change 2
            if(current->next == NULL)
            {
                current->next = newNode;
                printf("added later\n");
                break; // Change 3
            }
            current = current->next;
        };
    }
    return 0;
}

Why head is passed as node *head instead of node **head if we are going to change it inside and we want the changes to be propagated outside the function? What am I missing here?

Upvotes: 2

Views: 243

Answers (3)

user4842163
user4842163

Reputation:

You could probably make that code a little bit more elegant using a pointer to a pointer, like so:

int addNodeBottom(int val, node **link){
    node *newNode = ...;
    ...
    if(*link == NULL){
        printf("added at beginning\n");
    }
    else
    {
        while (*link)
            link = &(*link)->next;
        printf("added later\n");
    }
    *link = newNode;
    return 0;
}

...
addNodeBottom(some_val, &head->next);

... something to this effect. Not the biggest difference though but maybe a little bit nicer. It'd be simpler if the list didn't use a dummy node for the head and didn't need to print out when it adds to the beginning of the list vs. the end. In that case we could simply do:

void addNodeBottom(int val, node **link){
    node *newNode = ...;
    ...
    while (*link)
        link = &(*link)->next;
    *link = newNode;
}
...
addNodeBottom(some_val, &head);

... which is starting to look considerably nicer with no special cases to handle. If there's an absolute need to use this kind of dummy head and print out whether the insertion was to the front of the list or not, maybe it'd help to return a pointer to the new node (null on failure, e.g.), like so:

node* addNodeBottom(int val, node **link){
    node *newNode = ...;
    ...
    while (*link)
        link = &(*link)->next;
    *link = newNode;
    return newNode;
}
...
if (addNodeToBottom(some_val, &head->next) == head->next)
     printf("added at beginning\n");
else
     printf("added later\n");

Why head is passed as node *head instead of node **head if we are going to change it inside and we want the changes to be propagated outside the function?

As others pointed out, this is kind of an unusual linked list where the head is some kind of dummy node or something. It never gets modified in that function, only head->next, so changes to head will propagate and cause external side effects.

I never understood the point of those types of linked list implementations storing dummy nodes in languages like C and C++ since they don't cut down on special cases. They just waste memory for no good reason. They might make sense for a language that doesn't allow more than one level of indirection, but make no sense at all in languages that have pointers. Maybe the person who implemented that linked list originally came more from a background of languages without pointers, like Java or Python or something. Probably linked lists of this sort with dummy nodes aren't so unusual in those languages as a workaround to get around the fact that the language doesn't allow pointers to pointers (or references to references) to avoid some if statements here and there.

Upvotes: 0

dyoo
dyoo

Reputation: 12023

Fundamentally, no reason why it couldn't. In fact, this is one of the things that Linus Torvalds points out as demonstrating mastery over pointers. Related question: Using pointers to remove item from singly-linked list

Upvotes: 0

md5
md5

Reputation: 23699

head is never modified directly in this function. Only head->next is assigned to another value. Therefore you don't need to use a pointer to pointer.

Upvotes: 3

Related Questions