Avoiding Extra Malloc in Linked List (node->next = NULL)

Question

In my linked list, I'm trying to avoid mallocing an extra node without adding a bunch of if statements and such. I have the following:

polynomial create()
{
    polynomial head = NULL;
    polynomial temp = NULL;
    int numTerms, coefficient, exponent;
    int counter = 0;

    printf("Enter the number of terms in the polynomial: ");
    scanf ("%d", &numTerms);
    printf("\n");

    if (numTerms == 0) {
        head = malloc(sizeof(term));
        head->coef = 0; head->exp = 0; head->next = NULL;
        return head;
    }
    while (numTerms != counter) {
        // Ask for input
        printf("Enter the coefficient and exponent of term %d: ", (counter + 1));
        scanf("%d %d", &coefficient, &exponent);
        printf("\n");

        // Create the term
        if (temp == NULL) temp = malloc(sizeof(term));
        temp->coef = coefficient; temp->exp = exponent; temp->next = NULL;
        //if((numTerms - 1) != counter) temp->next = malloc(sizeof(term)); -- this is my workaround
        printf("Created: %d %d\n", temp->coef, temp->exp);

        // If this is the first node created, mark the head
        if (counter == 0) head = temp;
        // Increment the list and counter
        temp = temp->next;
        counter ++;
    }
    return head;
}

But when I go to print the polynomial (I have a function that works perfectly to do so), I get the following:

Polynomial 1: 3x^4 --> in this case, the reference to head->next is NULL

So I tried the following workaround - just allocate memory in advance for new nodes, but only if this would be the last iteration of user input. This is accomplished by:

replace temp->next = NULL; with

if((numTerms - 1) != counter) temp->next = malloc(sizeof(term));

The numTerms - 1 prevents adding the 'extra node', and the malloc is to keep the reference to temp->next alive. If I don't use the if check and just always allocate extra memory, I end up with the following:

Polynomial 1: 3x^4 - 7x^2 + 5 + 10621224x^10617028

What part of allocation am I missing that causes the reference to temp->next to be lost? I'm really really terrible with pointers and memory management in general, so this is probably a terrible question.

@MarkElliot he doesn't For some odd reason academia teaches it this way, and I've yet to see a well-founded reason for why. — WhozCraig

WhozCraig WhozCraig · Accepted Answer · 2013-10-06T22:27:10

You're making this much harder than it needs to be. Consider a simple node-population for a linked list that conforms to the following:

Assumes NULL means an empty list
Allocates the head pointer without having to test it for each allocation.
One, and only one allocation per-node is required.
Nodes are presented in the list in entry-order. The first node in the list is the first one you entered, the second node is the second you entered, etc.

With that, see below for the general algorithm as well as how it adapts to your code:

struct node
{
    // your fields here
    struct node *next;
};

struct node* populate_list()
{
    struct node *head = NULL;
    struct node **pp = &head;
    int i=0, count=0;

    // TODO: set count: get your insertion limit here. 

    // now run the insertion loop
    for (i=0; i<count; ++i)
    {
        struct node *p = malloc(sizeof(*p));

        // TODO: initialize your node members here

        // save to our current tail-pointer, which is initially
        //  also the head pointer. then advance to the new tail
        //  pointer and continue the loop
        *pp = p;
        pp = &p->next;
    }

    // terminate the list.
    *pp = NULL;

    // and return the head pointer.
    return head;
}

Note: p is there only for clarity. You can easily reduce that loop body to the following, which is totally valid:

    // now run the insertion loop
    for (i=0; i<count; ++i)
    {
        *pp = malloc(sizeof(**pp));

        // TODO: initialize your node members here
        //  using (*pp)->member for access

        // save next pointer and continue.    
        pp = &(*pp)->next;
    }

Adapting Your Code

Now that you know how to do this, it will considerably reduce your code to something like this:

polynomial create()
{
    polynomial head = NULL;
    polynomial *pp = &head;

    int numTerms, coefficient, exponent;
    int counter = 0;

    // prompt for valid number of terms.
    printf("Enter the number of terms in the polynomial: ");
    scanf ("%d", &numTerms);

    while (numTerms != counter)
    {
        // Ask for input
        printf("Enter the coefficient and exponent of term %d: ", (counter + 1));
        if (scanf("%d %d", &coefficient, &exponent) == 2)
        {
            *pp = malloc(sizeof(**pp));
            (*pp)->coef = coefficient;
            (*pp)->exp = exponent;
            pp = &(*pp)->next;
            ++counter;
        }
        else
        {   // eat the line and try again.
            scanf("%*[^\n]\n")
        }
    }
    *pp = NULL;

    return head;
}

Avoiding Extra Malloc in Linked List (node->next = NULL)

2 Answers