Array of Linked Lists in C: initializing and inserting?

Question

I need to create an array of linked lists (as pictured) and this is what I've made so far:

typedef struct Node {
    int data;
    struct Node *next;
} Node;

int main(void) {
    Node* link[5];
    for(int q = 0; q < 5; q++) {
        link[q] = malloc(sizeof(struct Node));
        link[q] = NULL;
    }
}

It's been awhile since I've used linked lists in C, so I've forgotten a lot of the syntax and I'm having trouble visualizing what exactly happens when I code linked lists. If I'm not mistaken, when I call malloc in my code, I'm creating a Node with nothing in it yet?

I want to initialize it to point to NULL. And I did this with

link[q] = NULL;

Am I right in saying this is what it looks like in memory?

|1| -> NULL

|2| -> NULL

|3| -> NULL

My next problem would be inserting data into the linked list.

(Referring to the picture): If I want to insert another element into say the 3rd index of the array ([3]-> d -> NULL)

Would this be correct?

Node* newNode = link[3];
newNode->data = 1;
link[3] = newNode;

Thank you for the help!

The insertion is invalid. There is again a memory leak. See my answer. — Vlad from Moscow
– Vlad from Moscow, Commented Sep 20, 2017 at 12:18
After calling malloc instead of newNode = link[3]; as it was written you have to write newNode->next = link[3]; — Vlad from Moscow
– Vlad from Moscow, Commented Sep 20, 2017 at 12:44

Vlad from Moscow · Accepted Answer · 2017-09-20 11:37:37Z

5

This loop

Node* link[5];
for(int q = 0; q < 5; q++) {
    link[q] = malloc(sizeof(struct Node));
    link[q] = NULL;
}

results in memory leaks because at first memory is allocated and then the pointers are overwritten with NULL. So the addresses of the allocated memory are lost.

You could just write

Node* link[5] = { 0 };

Here is a demonstrative program that shows how nodes can be added to elements of the array of lists. Insetad of the data member data of the type int I am using the data member data of the type char for visibility.

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

typedef struct Node 
{
    char data;
    struct Node *next;
} Node;


int push_front( Node **head, char data )
{
    Node *new_node = malloc( sizeof( Node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->data = data;
        new_node->next = *head;
        *head = new_node;
    }

    return success;
}

void output( Node **head )
{
    for( Node *current =*head; current != NULL; current = current->next )
    {
        printf( "%c ", current->data );
    }
    printf( "%s", "NULL" );
}

void display( Node **set, size_t n )
{
    for ( size_t i = 0; i < n; i++ )
    {
        output( set++ );
        putchar( '\n' );
    }
}

#define N   5

int main(void) 
{
    Node * link[N] = { 0 };

    push_front( &link[0], 'b' );
    push_front( &link[0], 'a' );
    push_front( &link[1], 'c' );
    push_front( &link[2], 'd' );

    display( link, sizeof( link ) / sizeof( *link ) );

    return 0;
}

The program output is

a b NULL
c NULL
d NULL
NULL
NULL

answered Sep 20, 2017 at 11:37

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

15 Comments

zuzu Over a year ago

In your function push_front, why do you do this? [int success = new_node != NULL; ] Would there be an occasion that the new_node would point to NULL (after just allocating space for it? Especially with the purpose of the function being collecting data for it anyway?). And why do we return the value of success? Is a return value required? Wouldn't it be the same to just declare the function as "void"?

Vlad from Moscow Over a year ago

@Katrina The function malloc can fail. You need a way to determine whether a node was successfully added to the list.

zuzu Over a year ago

Thank you again! :)

lambduh Over a year ago

In his case, he knew the size of link which is 5. How would you do it if you do not know the size of the array?

Vlad from Moscow Over a year ago

@wajaap Ask a new question at SO.

|

previ · Accepted Answer · 2017-09-20 13:10:31Z

3

As far as I understood your program, the following statement is not necessary:

link[q] = malloc(sizeof(struct Node));

since you need to start from NULL pointers, link[q] = NULL; is just fine.

To insert items in the list you should allocate memory for each item, so it should become something like that:

Node* newNode = malloc(sizeof(struct Node));
newNode->data = 1;
newNode->next = link[3];
link[3] = newNode;

It should work, although I did not test it.

edited Sep 20, 2017 at 13:10

answered Sep 20, 2017 at 11:26

previ

814 bronze badges

3 Comments

zuzu Over a year ago

Thank you! I drew out your insert code and I think after allocating space for newNode, you have to point it to what link[3] was pointing to with newNode = link[3]

previ Over a year ago

well, if you save the pointer of the allocated memory in newNode, than you need to assign the pointer to link[3] too, but not vice versa. So it should be link[3] = newNode.

zuzu Over a year ago

My mistake. I was actually referring to newNode->next = link[3], which I thought was newNode = link[3], at first. Thank you anyway :)

unwind · Accepted Answer · 2017-09-20 11:18:28Z

2

You already have an array of 5 pointers to nodes, that's link. You can set those to point to nothing by just doing:

for (size_t i = 0; i < sizeof link / sizeof *link; ++i)
 link[i] = NULL;

here you should not allocate any new storage since you don't want actual nodes, you just want pointers to nodes and you already have them.

Your code first allocates, then immediately overwrites the pointer returned by malloc() with NULL, effectively losing that memory forever. Not good.

When you want to actually create a node, that's when you need to allocate it and link it into the proper list.

answered Sep 20, 2017 at 11:18

unwind

402k64 gold badges492 silver badges620 bronze badges

1 Comment

zuzu Over a year ago

Good point! Thanks for the insight. That means my code to insert should be more like... Node *newNode = malloc(sizeof(struct Node)) ?

Bizzu · Accepted Answer · 2017-09-20 11:27:12Z

1

First of all the best thing to do for check something if you didn't sure is to see it - print it.

Second, there is mistake in your code -

    link[q] = malloc(sizeof(struct Node));
    link[q] = NULL;

here you make a new pointer void* in size of struct Node and then you lose him when you save NULL in the variable Link[i] you have 2 options:

To allocate link and then initialize it with defualt fields for example - data =-1
dont allocate and put NULL in everty Node before you initialize

my advise, go with 2, and only when you need to add new node allocate.

answered Sep 20, 2017 at 11:27

Bizzu

4593 silver badges17 bronze badges

Collectives™ on Stack Overflow

Array of Linked Lists in C: initializing and inserting?

4 Answers 4

15 Comments

3 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

15 Comments

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related