How to create nodes in a loop and insert them to a linked list

Question

Here is my structures:

typedef struct gene{
    char* name;
    int length;
    int* sequence;
} gene;

typedef struct genes{
    gene gene;
    struct genes* next;
} genes;

constructors:

genes* createGenes(gene newGene){
    genes* geneArr = malloc(sizeof(genes));
    if (NULL != geneArr){
        geneArr->gene = newGene;
        geneArr->next = NULL;
    }
    return geneArr;
}

void deleteGenes(genes* geneArr){
    if(NULL != geneArr->next){
        deleteGenes(geneArr->next);
    }
    free(geneArr);
}

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        geneList->next = toAdd;
    }
    return geneList;
}

and a function (it creates a sequence with the given length. For 5 -> {2, 2, 2, 2, 2}):

gene twosGene(char* name, int length){
    gene newGene;
    newGene.name = name;
    newGene.length = length;
    newGene.sequence = (int*)malloc(sizeof(int) * length);

    for(int i = 0; i < length; i++){
        newGene.sequence[i] = 2;
    }
    return newGene;
}

here is my main() function:

int main(){
    int count = 1;

    genes* geneArr = createGenes(twosGene("gene1", count++));

    for (int i = 0; i < 4; ++i) {
        geneArr = addGene(geneArr, twosGene("geneLoop", count++));
    }

    genes* iter;
    for (iter = geneArr; NULL != iter; iter = iter->next) {
        printf("gene=%d\n", iter->gene.length);
        free(iter->gene.sequence);
    }

    deleteGenes(geneArr);

    return 0;
}

I expect this output:

gene=1
gene=2
gene=3
gene=4
gene=5

but instead I'm getting this:

gene=1
gene=5

Also when I use Valgrind, there is some leakage in my program.

==20580== HEAP SUMMARY:
==20580==     in use at exit: 132 bytes in 6 blocks
==20580==   total heap usage: 11 allocs, 5 frees, 1,244 bytes allocated

I cannot figure it out why. Thanks for your helps.

twosGene seems like a rather odd function--can you explain the significance of the magic number 2? What sort of structure are you expecting to create (the stdout doesn't print the sequence). — ggorlen
– ggorlen, Commented Oct 28, 2019 at 15:59
@ggorlen, I checked that, but he is returning (a copy of) the whole struct. — Paul Ogilvie
– Paul Ogilvie, Commented Oct 28, 2019 at 16:00
Please post a minimal reproducible example and not bits of source code that need to be stiched together so it can be compiled. You can edit your question. — Jabberwocky
– Jabberwocky, Commented Oct 28, 2019 at 16:01
@ggorlen Actually I shortened my code to post a question and '2' is just some value, not mean anything. — Stewie
– Stewie, Commented Oct 28, 2019 at 16:02
Is addGene supposed to add to the end of the list or add to the beginning? At the moment it just overwrites the next pointer of the first element in the list, which isn't what you want. — Ian Abbott
– Ian Abbott, Commented Oct 28, 2019 at 16:03

Vlad from Moscow · Accepted Answer · 2019-10-28 16:17:38Z

Within this function

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        geneList->next = toAdd;
    }
    return geneList;
}

you are always overwriting the data member next of the node initially created in the statement

genes* geneArr = createGenes(twosGene("gene1", count++));

It seems you want to add a new node to the end of the current list. In this case the function will look like

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        genes *current = geneList;

        while ( current->next != NULL ) current = current->next;
        current->next = toAdd;
    }
    return geneList;
}

However in general even this function definition is invalid because initially geneList can be equal to NULL. So using your approach the function should be rewritten the following way

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        if ( geneList == NULL )
        {
            geneList = toAdd;
        }
        else
        {
            genes *current = geneList;

            while ( current->next != NULL ) current = current->next;
            current->next = toAdd;
        }
    }

    return geneList;
}

However even this function implementation can be improved if to pass pointer to the head pointer of the list.

For example

int addGene( genes **geneList, gene newGene )
{
    genes* toAdd = createGenes(newGene);
    int success = toAdd != NULL;

    if ( success )
    {
        while ( *geneList != NULL ) geneList = &( *geneList )->next;
        *geneList = toAdd;
    }

    return success;
}

In this case the function can be called like

genes* geneArr = createGenes(twosGene("gene1", count++));

for (int i = 0; i < 4; ++i) {
    addGene( &geneArr, twosGene("geneLoop", count++));
}

Paul Ogilvie · Accepted Answer · 2019-10-28 16:10:27Z

In:

genes* geneArr = createGenes(twosGene("gene1", count++));

for (int i = 0; i < 4; ++i) {
    geneArr = addGene(geneArr, twosGene("geneLoop", count++));
}

the first allocates the head of the list. In the for-loop you next overwrite this head with every iteration. You should/could do:

genes* geneArr = createGenes(twosGene("gene1", count++));

genes *geneNext= geneArr;
for (int i = 0; i < 4; ++i) {
    geneNext = addGene(geneNext, twosGene("geneLoop", count++));
}

Also, addGene must advance the pointer for the above to work.

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        geneList->next = toAdd;
        genelist= geneList->next;  // add this statement.
    }
    return geneList;
}

Now you can print it, as you still have the head.

Ian Abbott · Accepted Answer · 2019-10-28 17:10:56Z

1

The addGene function is not adding to the end of the list. It is just linking the new gene to the first gene. Anything after the first gene in the list is "forgotten", leading to the memory leak, as reported by Valgrind.

Here is an updated version of the addGenes function that should work:

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        if (geneList == NULL){
            geneList = toAdd;
        } else {
            genes *last = geneList;
            while (last->next != NULL){
                last = last->next;
            }
            last->next = toAdd;
        }
    }
    return geneList;
}

edited Oct 28, 2019 at 17:10

answered Oct 28, 2019 at 16:13

Ian Abbott

18.1k1 gold badge22 silver badges39 bronze badges

Collectives™ on Stack Overflow

How to create nodes in a loop and insert them to a linked list

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related