Thread: Linked lists

Hello, I went through three articles about linked lists, but I am just not getting how the whole thing works. I have written a code, but it's not working:

Code:

#include<stdio.h>

struct node
{
       int   x;
       struct node *next;
};

int main(void)
{
    int i;
    struct node *head;
    struct node *ptr;
    
    head = malloc(sizeof(struct node));
    ptr = head;
    
    for(i = 0; i < 3; i++)
    {
          scanf(" %d",ptr->x);
          ptr = ptr->next;
    }
    
    ptr = head;
    while(ptr != NULL)
    {
         printf("%d\n",ptr->x);
         ptr = ptr->next;
    }
    
    system("pause");
    return 0;
}

Please guys I need help to understand linked lists better, please help me out.

It seems you're on the right track, but your code is incomplete. You're only allocating space for one node (the head pointer), then trying to move up a list that doesn't exist.

Try implementing the following steps:

- allocate memory for the head node (which you've done)
- initialize the members ("struct node *next" should be set to NULL)

To add a second node:

- allocate memory for another node (pointer)
- initialize the members ("struct node *next" should be set to NULL)
- set the "next" pointer in "head" to point to the newly created node

To add more nodes:

- find the last valid node (starting at "head", transverse the pointers until you find the node that has the "next" pointer set to NULL)
- allocate memory for another node (pointer)
- initialize the members ("struct node *next" should be set to NULL)
- set the "next" pointer in the node found above to point to the newly created node

And don't forget to free your memory when you're finished!

Your problem is in how you build the list, your print code looks fine. You never set head->x or head->next, so your first node is useless, and you can't use head->next (or ptr->next since head and ptr point to the same place) until it points to valid memory. You need to malloc every node you create and set the next element to something useful, either the next node you create, or NULL to signify end of list. Also, when you do your loop on lines 18-22, you use ptr->next, but you only allocated the first node, so you've walked off the end of the list. It's a bit like walking off the end of an array: you have started to access memory you don't own, and thus you are experiencing undefined behavior. The last problem is that you aren't calling scanf properly. You need a pointer to where you are storing the data, i.e. use the address-of operator (ampersand) &(ptr->x). What you need to do is something like the following:

Code:

head = malloc
// read data into head->x
ptr = head
for i from 0 to 2
    ptr->next = malloc  // allocate a new node and make it the next node in the list
    ptr = ptr->next;  // make ptr point to this new node
    scanf("%d", &(ptr->x));

ptr->next = NULL;  // terminate the list

In the loop, ptr->next is allocated, then ptr is moved to the new node. When the loop is over, if you do ptr = NULL, you are making ptr point to NULL instead of the last node. You are not changing the last node that way. What you want to do is set the last node's next element to NULL, to indicate there are no more nodes after the last one. So yes, after your loop to create the list, you should do

Code:

ptr->next = NULL;

Originally Posted by anduril462

In the loop, ptr->next is allocated, then ptr is moved to the new node. When the loop is over, if you do ptr = NULL, you are making ptr point to NULL instead of the last node. You are not changing the last node that way. What you want to do is set the last node's next element to NULL, to indicate there are no more nodes after the last one. So yes, after your loop to create the list, you should do

Code:

ptr->next = NULL;

Ya, but when I am printing the values, its printing 4 values and last one is printing a garbage value.

Originally Posted by Harith

Ya, but when I am printing the values, its printing 4 values and last one is printing a garbage value.

Ahh, I see what you're saying now. Notice, you changed my code a little (which is okay), but you didn't consider all the ramifications. We initialize the x member in different places. My code fills head->x before the loop, then fills ptr->x after malloc'ing and doing ptr = ptr->next. Your code fills the x element before moving to the next node, so you don't need to fill the first element before the loop, but you do need to fill the last element after the loop.

It's because you assign data to the current node then create a new node each iteration of the loop. So the last time through the loop, the last node you've created isn't given a value.

Code:

// Before loop, "head" is created

 +-----+
 | [ ] |
 |     |
 |  *  |
 +-----+

// During loop:

// i = 0, you assign data to the current node and create a new node

 +-----+    +-----+
 | [0] |    | [ ] |
 |     |    |     |
 |  *--|--->|  *  |
 +-----+    +-----+
             (new)

// i = 1, you assign data to the current node and create a new node

 +-----+    +-----+    +-----+
 | [0] |    | [1] |    | [ ] |
 |     |    |     |    |     |
 |  *--|--->|  *--|--->|  *  |
 +-----+    +-----+    +-----+
                        (new)

// i = 2, you assign data to the current node and create a new node

 +-----+    +-----+    +-----+    +-----+
 | [0] |    | [1] |    | [2] |    | [ ] |
 |     |    |     |    |     |    |     |
 |  *--|--->|  *--|--->|  *--|--->|  *  |
 +-----+    +-----+    +-----+    +-----+
                                   (new)

// you break out of the loop, and assign NULL to the last node, which was never given data

 +-----+    +-----+    +-----+    +-----+
 | [0] |    | [1] |    | [2] |    | [ ] |
 |     |    |     |    |     |    |     |
 |  *--|--->|  *--|--->|  *--|--->|  *--|--->NULL
 +-----+    +-----+    +-----+    +-----+

Originally Posted by Matticus

It's because you assign data to the current node then create a new node each iteration of the loop. So the last time through the loop, the last node you've created isn't given a value.

Code:

// Before loop, "head" is created

 +-----+
 | [ ] |
 |     |
 |  *  |
 +-----+

// During loop:

// i = 0, you assign data to the current node and create a new node

 +-----+    +-----+
 | [0] |    | [ ] |
 |     |    |     |
 |  *--|--->|  *  |
 +-----+    +-----+
             (new)

// i = 1, you assign data to the current node and create a new node

 +-----+    +-----+    +-----+
 | [0] |    | [1] |    | [ ] |
 |     |    |     |    |     |
 |  *--|--->|  *--|--->|  *  |
 +-----+    +-----+    +-----+
                        (new)

// i = 2, you assign data to the current node and create a new node

 +-----+    +-----+    +-----+    +-----+
 | [0] |    | [1] |    | [2] |    | [ ] |
 |     |    |     |    |     |    |     |
 |  *--|--->|  *--|--->|  *--|--->|  *  |
 +-----+    +-----+    +-----+    +-----+
                                   (new)

// you break out of the loop, and assign NULL to the last node, which was never given data

 +-----+    +-----+    +-----+    +-----+
 | [0] |    | [1] |    | [2] |    | [ ] |
 |     |    |     |    |     |    |     |
 |  *--|--->|  *--|--->|  *--|--->|  *--|--->NULL
 +-----+    +-----+    +-----+    +-----+

So how do I assign null to 2nd node?

Originally Posted by Harith

So how do I assign null to 2nd node?

See post #10, for an alternative way to initialize the list that eliminates having to special case the initialization of head and the first node.

So how do I assign null to 2nd node?

Try restructuring your logic - it seems backwards. In the loop, you (1) assign data to current node, then (2) create a new node. Instead, consider (1) creating a new node, then (2) assigning data to it.

Right now, your code does this:

Code:

 - Create head node
 - In loop:
   - Assign data to the current node
   - Create a new node

It would be better to do something like:

Code:

 - Create and initialize head node
 - In loop:
   - Create a new node
   - Assign data to the current node (this is where the "next" pointer of the last valid node is set to NULL, before breaking out of the loop)

rcgldr has some good advice you should consider. My suggestion might be easier for you to implement with what you have so far, for the purposes of understanding.

Oh, and if you haven't already, grab a pencil and paper draw out the linked list based on your code, line by line (which I sort of did in post #9). I personally prefer the representation I illustrated. For me, the understanding of linked lists did not come from code, but from the illustrations of how a linked list was supposed to work. Any code I wrote was simply a result of that understanding.

Thanks guys for the help.