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, Commented Oct 6, 2013 at 22:16

WhozCraig · Accepted Answer · 2013-10-07 17:11:56Z

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;
}

Thanks a bunch! I guess I was trying to skip a step, but didn't do it correctly. The idea of pointers still isn't really there for me... I guess after this I will have had plenty of practice!
@ChrisCirefice You really need to think about how that pointer-to-pointer in this code works. Just remember this: it always hold the address of a pointer. Which pointer? The next pointer to be filled in with an allocation. Initially it holds the address of the head pointer we'll be returning from our function. That is the reason the head gets the initial population. After that, each newly added node is chained therein, and pp alwaays holds the address of the last node added's next pointer. After the loop, the *pp=NULL terminates the list by nulling the last node next pointer.
Sorry I didn't comment back sooner, I had two exams to study for! Anyway, I do understand the pointer to the pointer. The initial pointer, head keeps track of the first malloc'd node. The tail is a pointer to the other pointer (initially head) that is gradually incremented as new nodes are added. I suppose that the reason (regrettably) that I never really understood pointers to begin with was caused by the fact that students learn Java first, and Java cleverly hides all of this. Everything is working perfectly now though, and pointers aren't such a problem for me :)
@ChrisCirefice correct. As I'm sure you understand by now, just like an int *p is a pointer variable that holds an address where somewhere and int resides (or NULL), an int **pp is a pointer variable that holds an address where somewhere an int * pointer resides (again, or NULL). If you can wrap your head around that, this code makes a ton more sense. Initially pp in the answer code holds the address where the head pointer resides. After that, it always holds the address where the last node's next pointer resides.

ChuckCottrill · Accepted Answer · 2013-10-07 19:16:11Z

0

Also, you will discover that for storing an infix expression such as the above works much better with a binary tree. You denote the nodes of the tree with the operations (+,-,*,/,^), and you also have a parenthesis tree (everything under it is an expression, surrounded by parenthesis.

As you scan through your expression, you build a tree, which you will find you can do recursively.

Printing out your tree is done using a depth-first, left-node-right traversal.

answered Oct 7, 2013 at 19:16

ChuckCottrill

4,4792 gold badges30 silver badges45 bronze badges

1 Comment

Chris Cirefice Over a year ago

I know all about binary trees, and as polynomial math is done through traversing (the data structure) to get coef and exp, a binary tree would be much more efficient (well, let's not get into how much more efficient it would be, considering polynomials probably won't ever get to 10000+ terms...). However, the goal of the assignment was to learn how to malloc in C and build linked lists, not binary trees. But thanks for the suggestion, if I ever can find some spare time in my collegiate life I'll take a whack at adapting it.

Collectives™ on Stack Overflow

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

2 Answers 2

4 Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Related