C memory leak when inserting into a doubly linked list

Question

Hi I'm new to C and pointers and are having issues trying to implement the below doubly linked list structure. Memory leaks happened in listInsertEnd I believe? I am very confused as to why one work (at least no mem leak in output) and the other one doesn't. I have pasted only parts of the program, any help or explanation is much appreciated.

#include <stdio.h>
#include <stdlib.h>

typedef struct node *Node;
struct node {
    int value;
    Node next;
    Node prev;
};

typedef struct list *List;
struct list {
    Node first;
    Node last;
    int count;
};

Node newNode(int value) {
    Node n = malloc(sizeof(*n));
    if (n == NULL) fprintf(stderr, "couldn't create new node\n");
    n->value = value;
    n->next = NULL;
    n->prev = NULL;
    return n;
}

void listInsertEnd(List newList, int value) {
    Node n = newNode(value);

    if (newList== NULL) { //no item in list
        //why is this giving me memory leaks
        newList->first = newList->last = n;
        //whereas this doesn't?
        newList->first = newList->last = newNode(value);

    } else {  //add to end
        n->prev = newList->last;
        newList->last->next = n;
        newList->last = n;
    }
    nList->count++;
}

Post a program that can be compiled and produces the problem you are experiencing. Also, how can you be sure about memory leakage if you haven't tested it with some tool like `valgrind`? — Marco Bonelli, Apr 02 '20 at 17:26
This `if (newList== NULL) { newList->first = newList->last = n; ...` is dereferencing a `NULL` pointer. You must allocate some memory for a new node. Both statements dereference a `NULL` pointer so for "memory leak" read "crash". — Weather Vane, Apr 02 '20 at 17:28
I count 1 call to `malloc` and 0 calls to `free`, the memory leak is there, why are you surprised? — David Ranieri, Apr 02 '20 at 17:32
@WeatherVane sorry but let's assume I am passing in a valid empty list, if I use if(newList->first == NULL) I am still getting mem leaks from a testing program — Frankieeee, Apr 02 '20 at 17:38

Vlad from Moscow · Answer 1 · 2020-04-02T17:53:06.757

This typedef declaration

typedef struct node *Node;

is confusing and presents a bad style. Consider for example this statement

Node n = malloc(sizeof(*n));

somebody can think that here is a typo and should be written

Node *n = malloc(sizeof(*n));

The function

void listInsertEnd(List newList, int value) {
    Node n = newNode(value);

    if (newList== NULL) { //no item in list
        //why is this giving me memory leaks
        newList->first = newList->last = n;
        //whereas this doesn't?
        newList->first = newList->last = newNode(value);

    } else {  //add to end
        n->prev = newList->last;
        newList->last->next = n;
        newList->last = n;
    }
    nList->count++;
}

has undefined behavior. If newList is equal to NULL then you are trying to use memory pointed to by a null pointer.

    if (newList== NULL) { //no item in list
        //why is this giving me memory leaks
        newList->first = newList->last = n;
        //whereas this doesn't?
        newList->first = newList->last = newNode(value);

And initially data members newList->first and newList->last can be equal to NULL. That also can be reason of undefined behavior because the function does not take this into account.

Before changing the function listInsertEnd you should define the function newNode the following way

Node newNode(int value) 
{
    Node n = malloc(sizeof(*n));

    if ( n != NULL )
    {
        n->value = value;
        n->next = NULL;
        n->prev = NULL;
    }

    return n;
}

The function shall not issue any message. It is the caller of the function that decides whether to issue a message if it is required.

In this case the function listInsertEnd can be written the following way

int listInsertEnd(List newList, int value) 
{
    Node n = newNode(value);
    int success = n != NULL;

    if ( success )
    {
        n->prev = newList->last;  

        if ( newList->first == NULL )
        {
            newList->first = newList->last = n;
        }
        else
        {
            newList->last = newList->last->next = n;
        }

        ++newList->count;
    }

    return success;
}

Within the main you should create the list the following way

int main( void )
{
    struct list list1 = { .first = NULL, .last = NULL, .count = 0 };
    // or
    // struct list list1 = { NULL, NULL, 0 };

and call the function like

listInsertEnd) &list1, some_integer_value );

Marco Bonelli · Accepted Answer · 2020-04-15T06:28:18.700

First of all, talking about memory leaks: there is no direct memory leak in your code. If the leak happens somewhere, it's outside of these functions. It's most probably because you create one or more nodes and then forget to free() them, but this has nothing to do with the two functions you show.

I see that you are using typedef to declare simple pointer types, take a look at this question and answer to understand why that's bad practice and should be avoided: Is it a good idea to typedef pointers?. Also, this particular piece of Linux kernel documentation which explains the issue in more detail.

Secondly, the real problem in the code you show is that you are using pointers after you tested that they are invalid (NULL).

Here:

Node newNode(int value) {
    Node n = malloc(sizeof(*n));
    if (n == NULL) fprintf(stderr, "couldn't create new node\n");
    n->value = value;
//  ^^^^^^^^ BAD!

And also here:

if (newList== NULL) {
    newList->first = newList->last = n;
//  ^^^^^^^^^^^^^^ BAD!

If something is NULL, you cannot dereference it. Change your functions to safely abort after they detect an invalid pointer.

This can be done in multiple ways. Here's an example of correct code:

Node newNode(int value) {
    Node n = malloc(sizeof(*n));
    if (n == NULL) {
        fprintf(stderr, "couldn't create new node\n");
        return NULL;
    }

    n->value = value;
    n->next = NULL;
    n->prev = NULL;
    return n;
}

void listInsertEnd(List newList, int value) {
    Node n;

    if (newList == NULL) {
        return;
        // You probably want to return some error value here.
        // In that case change the function signature accordingly.
    }

    n = newNode(value);

    if (newList->count == 0) {
        newList->first = newList->last = n;
    } else {  //add to end
        n->prev = newList->last;
        newList->last->next = n;
        newList->last = n;
    }

    newList->count++;
}

NOTE: the check newList->count == 0 assumes that you correctly increment/decrement the count when adding/removing elements.

thank you so much sir, sorry couldn't paste the whole working project as it is part of a big program. — Frankieeee, Apr 02 '20 at 17:48

C memory leak when inserting into a doubly linked list

2 Answers2