CODEWITHSUNDEEP
carrayslinked-listsingly-linked-list
zuzu
zuzu

Reputation: 411

Array of Linked Lists in C: initializing and inserting?

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

enter image description here

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!

Upvotes: 7

Views: 23798

Answers (4)

previ
previ

Reputation: 81

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.

Upvotes: 3

Vlad from Moscow
Vlad from Moscow

Reputation: 310930

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

Upvotes: 5

Bizzu
Bizzu

Reputation: 459

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:

  1. To allocate link and then initialize it with defualt fields for example - data =-1
  2. 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.

Upvotes: 1

unwind
unwind

Reputation: 399753

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.

Upvotes: 2

Related Questions