CODEWITHSUNDEEP
c
Kudayar Pirimbaev
Kudayar Pirimbaev

Reputation: 1320

Linked list implementations difference

For the following linked list declaration,

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

typedef struct list
{
   int val;
   struct list *next;
} list;


void destroy (list *l)
{
    if (l)
    {
        destroy (l->next);
        free (l);
    }
}

why does the following main work

int main()
{
    list *test;
    list *ptr1, *ptr2;
    int i;
    test = malloc (sizeof (list));
    test->val = 0;
    ptr2 = test;
    for (i = 1; i <= 10; i++)
    {
        ptr1 = (list *) malloc (sizeof (list));
        ptr1->val = i;
        ptr2->next = ptr1;
        ptr2 = ptr1;
    }
    ptr1 = test;
    while (ptr1)
    {
        printf ("%d\n", ptr1->val);
        ptr1 = ptr1->next ;
    }
    destroy (test);
    return 0;
}

while this one doesn't even create a list (it only makes one node)?

int main()
{
    list *test;
    list *ptr;
    int i;
    test = malloc (sizeof (list));
    test->val = 0;
    ptr = test->next;
    for (i = 1; i <= 10; i++)
    {
        ptr = (list *) malloc (sizeof (list));
        ptr->val = i;
        ptr = ptr->next;
    }
    ptr = test;
    while (ptr)
    {
        printf ("%d\n", ptr->val);
        ptr = ptr->next ;
    }
    destroy (test);
    return 0;
}

Don't they use the same logic?

Upvotes: 1

Views: 131

Answers (3)

simonc
simonc

Reputation: 42165

The code

ptr = test->next;
for (i = 1; i <= 10; i++)
{
    ptr = (list *) malloc (sizeof (list));
    ptr->val = i;
    ptr = ptr->next;
}

starts by taking a copy of test->next but never assigns anything to test->next itself. A list starting from test therefore only has a single item. Worse, that item has an uninitialised next pointer so code that tries to iterate over the list will almost certainly crash.

As hinted at in the other answers, this pattern is repeated for each newly allocated node.

In answer to your comment, the best way to make the second function work is to make it more like the first (working) version. I've renamed the variables in it to try to make it clearer

list *head;
list *next, *curr;
int i;
head = malloc (sizeof(*head));
head->val = 0;
curr= head;
for (i = 1; i <= 10; i++)
{
    next = malloc (sizeof(*next));
    next->val = i;
    curr->next = next;
    curr= next;
}
curr= head;

Upvotes: 3

Dayal rai
Dayal rai

Reputation: 6606

In the second main during 

ptr = test->next;

you are trying to acces test->next withouth allocating memory for it.You can try changing your code as following to get second main working

test = malloc (sizeof (list));
    test->val = 0;
    test->next = (list *) malloc (sizeof (list));
    ptr = test->next;
    for (i = 1; i <= 10; i++)
    {
        ptr->val = i;
    ptr->next = (list *) malloc (sizeof (list));
        ptr = ptr->next;
    }

Upvotes: 1

TooTone
TooTone

Reputation: 8116

It looks like in the first example, which works, ptr2 is holding the previously created node in the list, so that this can be rewritten

last_created_node = test;
for (i = 1; i <= 10; i++)
{
    // create new node
    new_node = (list *) malloc (sizeof (list));
    new_node ->val = i;
    // chain newly created node onto list so far
    // make last created node point to new node
    last_created_node->next = new_node ;
    // last created node is now new node
    last_created_node = new_node ;
}
// terminate the list
last_created_node->next = 0;

There is no equivalent of linking a new node onto the chain in the second code sample you give. Also there are problems with unitialised memory as others have commented. Would be good to add the termination condition as shown in the last line of my sample above.

Upvotes: 1

Related Questions