How do I access a null pointer (node) of a linked list?

Question

This method is supposed to append a Node at the end of a linked list. The method loops until it reaches the end, which is the null pointer. But when I try to change the null pointer to a value, it crashes. How should I fix this? (The Node pointer has a integer data and another Node variable which the current Node points to).

void appendItem(LinkedList* list, int value)
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp = list->head;

    while(temp != NULL)
    {
        temp = temp->next;
    }

    temp->data = value;
    temp->next = NULL;
}

In the first line you are allocating memory and assigning it to `temp`. In the next line you are overwriting `temp` with something else. Surely it is not something you were intending to do. — Eugene Sh., Jun 03 '21 at 17:30
`while(temp != NULL)` --> `while(temp->next != NULL)` but you also need another variable, as said. — Weather Vane, Jun 03 '21 at 17:31

score 5 · Answer 1 · answered Jun 03 '21 at 17:32

Dereferencing NULL is prohibited.

Instead of that, you should manage a pointer to what should be changed.

Also note that allocating some buffer via malloc() and overwriting the result with another value just after that causes a memory leak.

One more point is that casting results of malloc() family is considered as a bad practice.

Fixed code:

void appendItem(LinkedList* list, int value)
{
    Node** temp = &list->head;

    while(*temp != NULL)
    {
        temp = &(*temp)->next;
    }

    *temp = malloc(sizeof(Node));
    if (*temp != NULL)
    {
        (*temp)->data = value;
        (*temp)->next = NULL;
    }
}

Vlad from Moscow · Answer 2 · 2021-06-03T17:52:39.160

3

These lines

Node* temp = (Node*)malloc(sizeof(Node));
temp = list->head;

produces a memory leak. At first a memory was allocated and its address was stored in the pointer temp and then the value of the pointer temp was overwritten by the value of the expression list->head. As a result the address of the allocated memory was lost.

After this loop

while(temp != NULL)
{
    temp = temp->next;
}

the pointer temp is equal to NULL. So a null pointer is used to access memory in these statements

temp->data = value;
temp->next = NULL;

that invokes undefined behavior.

The function can be defined for example the following way.

int appendItem( LinkedList *list, int value )
{
    Node *new_node = malloc( sizeof( Node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->data = value;
        new_node->next = NULL;

        if ( list->head == NULL )
        {
            list->head = new_node;
        }
        else
        {
            Node *current = list->head;
            while ( current->next != NULL ) current = current->next;
            current->next = new_node;
        }
    }

    return success;
}

Pay attention to that the memory allocation can fail. You need to process such a case in your function. And the caller of the function should be informed about such a situation.

Also as you allow to append new nodes to a singly-linked list then the list should be defined as a two-sided singly-linked list. That is the list should keep two pointers: one pointer to the head node and other pointer to the tail node. Otherwise appending a node to the list will be inefficient.

edited Jun 03 '21 at 17:52

answered Jun 03 '21 at 17:39

Vlad from Moscow

301,070
26
186
335

1

I don't see much point in the need of having the variable `success`. Why not get rid of it and simply `return 0` if `malloc` fails, and always `return 1` at the end of the function? – Andreas Wenzel Jun 03 '21 at 17:47
@AndreasWenzel The function does exactly this. So your comment does not make a sense. The only difference is that my function has only one return statement instead of two return statements. – Vlad from Moscow Jun 03 '21 at 17:48
There are three things that are hard to get right in programming: naming things and avoiding off by one errors ;). Nice job! Though I would use the expression `while ( NULL != current-next)`. – jwdonahue Jun 03 '21 at 17:51
@AndreasWenzel, it's one of the tenets of [structured programming](https://en.wikipedia.org/wiki/Structured_programming). One entry, one exit. It can be argued that it's easier on code reviewers when every function/method/procedure has a single return at the end. But then it can be carried too far in cases where the reviewer has to carry too much program state in their mind, making harder to manually verify correctness. But I find that to be an argument for simplifying over-complicated functions. – jwdonahue Jun 03 '21 at 18:02
2

@jwdonahue: every rule has exceptions. While it's generally better to have a single exit, it makes no sense to stay in the function if it's unable to do its job. In the case of ```appendItem()``` above, it would be excessive to wrap the entire function body with ```if (list) { }``` as a check that the pointer is valid. If ```list``` is ```NULL```, return immediately. The extra indenting of functionally useless blocks makes code harder to read. – sj95126 Jun 03 '21 at 18:13
@sj95126, I agree that there is such a thing as excessive levels of scope, and I personally prefer the early exit approach, as it allows the reviewer to flush that case from their current cognitive stack. I think the example code is fine however. If it had one more level of scope, or even slightly higher complexity, I'd probably recommend some refactoring. But I recognized the style immediately and did not suffer any cognitive dissonance from reading it. – jwdonahue Jun 03 '21 at 18:20
I agree that structured programming should generally be used, unless there is a good reason not to use it. In this case, having only a single point of exit has the price of an additional variable and of an additional layer of scope. In my opinion, it is not worth the price. – Andreas Wenzel Jun 03 '21 at 18:22
Though I would rename the variable to `result` or `retval`, naming a variable `success` when it very well might mean failure is the only nit I have for that function. – jwdonahue Jun 03 '21 at 18:23
@AndreasWenzel, how to put a "price" on an additional variable, or an additional return statement? Shall we use a complexity metric perhaps? I read a LOT of code and have worked in some massive code bases. When I see nesting at 2 levels, I am not concerned. At 3 levels, I begin to ponder whether a refactoring effort is warranted. Greater than 3, I demand a rewrite. Your suggested change would reduce nesting to 1 level, but I don't think it would change the complexity level enough to bother arguing for a rewrite. – jwdonahue Jun 03 '21 at 18:37

How do I access a null pointer (node) of a linked list?

2 Answers2