C linked Lists/-> Operator

Question

So I've been trying to understand the concepts of linked lists (Been looking at some example code, I found this one on the internet. Now if I could kindly have someone confirm if I have grasped some of the concepts correctly. I will draw diagrams of what I think each linke of code does.

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

   struct ListItem {
   int data;
   struct ListItem *next;
};

int main (int argc, char *argv[]){

   struct ListItem a;  
   a.data = 0;
   a.next = NULL;
   struct ListItem b;
   b.data = 1;
   b.next = NULL;
   struct ListItem c;
   c.data = 2;
   c.next = NULL;

   a.next = &b;
   b.next = &c;

   int counter = 0;
   struct ListItem *i;
   for (i = &a; i != NULL; i = i->next){

      printf("Item %d value is %d\n\r", counter, i->data);
      counter++;
   }


   return 0;
}

---

Snippet of code 1:

struct ListItem {
    int data;
    struct ListItem *next;
};

This creates a structure called ListItems. There are two components to the structure, a component to store the data and a pointer to another structure of type struct ListItem. I visualise the linked list like this:

Is this a correct way of visualising it?

---

Code snippet 2:

struct ListItem a;  
a.data = 0;
a.next = NULL;
struct ListItem b;
b.data = 1;
b.next = NULL;
struct ListItem c;
c.data = 2;
c.next = NULL;

Yup, I know it can be cut shorter but I just did it this way to see if I can understand the concept. Now this snippet creates a variable "a", "b" and "c" of type struct ListItem. Then it sets the first member (data) of each structure to 0, 1, 2 respectively and the second member (next) to point to NULL. So my visualisation now is like this:

Now MORE QUESTIONS:

Question 1: When we are initially the pointer to NULL, it points to nothing correct? Why do we do this? Wasn't it originally pointed to nothing?

---

Snippet 3:

   a.next = &b;
   b.next = &c;

This let's next in each variable a, b (which is a structure) point to the address memory location of b and c respectively.

My visualisation:

Question: How can it do this? Isn't the structure itself stored over multiple memory address (4 for int, etc)

---

Snippet 4:

   int counter = 0;
   struct ListItem *i;
   for (i = &a; i != NULL; i = i->next){

      printf("Item %d value is %d\n\r", counter, i->data);
      counter++;
   }

Here is the snippet I've been a bit confused with. Now, we set aside an integer called counter and initailise this to zero. Also, we create a variable called i that points to the type struct ListItem. Now could someone explain to me the for loop? I am a bit confused on what it's doing. In particular, i=i->next, I'm not familiar with this. I know it's equivalent to i=(*i).next but not sure what it really does. Could someone create a quick diagram?

ALSO: If anyone has any good resources/links (no pun intended) to some useful websites to help me understand linked lists a bit better feel free to post them.

Answer 1

Question 1: When we are initially the pointer to NULL, it points to nothing correct? Why do we do this? Wasn't it originally pointed to nothing?

Yes. NULL can't be the address of any node, so it doesn't point to any thing. We initialize to NULL to avoid bugs in program. its also assume good practice to initialize variables with some default value.

Suppose if you don't initialize next with NULL then next will point to some garbage node and if your code is buggy, then access unallocated memory is Undefined behavior. And uninitialized value of next is garbage and different run will behave different way. But If you initialize to NULL it will produce constant result and hence easy to trace error. Read: Initialize a variable.

Question-2: In particular, i = i->next, I'm not familiar with this. I know it's equivalent to i = (*i) .next but not sure what it really does. Could someone create a quick diagram?

In expression i = i->next;, you are assigning next node's address to i pointer. Your linked-list in memory can be assume like:

 a         b        c 
+---+    +---+    +---+                               
| a |--->| 1 |--->| 2 |---+
+---+    +---+    +---+   |                                
                         null  

initially you assign address of node a to i in expression i = &a in for loop, and it becomes like this:

 a         b        c 
+---+    +---+    +---+                               
| a |--->| 1 |--->| 2 |---+
+---+    +---+    +---+   |                                
  ▲        ▲             null  
  i        i->next    


  i = i->next; 
  ^      ^
  |      next to `i` in linked list
   current node 

operator -> called Member selection via pointer, Note here i is pointer of type struct ListItem*.
You can also do same by using . operator called Member selection via object name as follows:

  i = (*i).next;       

Both operators -> and . can be use to access members of object. Operator -> is useful with address and . with value variable.

Question-3: we set aside an integer called counter and initialize this to zero. Also, we create a variable called i that points to the type struct ListItem. Now could someone explain to me the for loop?

In your code, i is used as I explained above to keep address of current node while traveling through the linked-list, while counter just use to count nodes in linked list.

   int counter = 0;  <-----" count value is 0, not Garbage"
   struct ListItem *i;

   for (i = &a; i != NULL; i = i->next){ 
                   ^
                   |<------ "loop will run till `i` not point to NULL"
                   |        "this means loop will run once for all nodes"
      printf("Item %d value is %d\n\r", counter, i->data);
      counter++;  <---"each time `counter` incremented by `1` (one for each node)"
   }
   "after the loop counter value is = number of nodes in list"

ALSO: If anyone has any good resources/links (no pun intended) to some useful websites to help me understand linked lists a bit better feel free to post them.

Read from a source where concept is explained with diagram and code. You can refer: How to create Linked list using C?

Answer 2

Q1: an uninitialized pointer does not point to "nothing". If you don't set its value, it can (and will) point to just about anything, including (but not limited to) a nul value, out-of-bounds memory, or the last password you entered on a website.

It's really no different than asking what the value of your counter is when you do

int counter;
...
printf ("counter is %d\n", counter);

Setting the next pointer to NULL, therefore, serves two distinct purposes. First, you are sure it is a "known" value, not any random one. Second, by convention a NULL value means that it does not point to any valid location.

(It is a 'convention' because NULL effectively stores the numerical value '0'. This, as a memory address -- since you are talking about pointers -- is perfectly valid. There are just not many daily uses for it.)

Answer 3

Answer to question 1: no, initially the struct is uninitialized, and its next field most probably points to nothing correct, but chances are that it's doesn't contain NULL.

To question 2: each structure variable has its address in memory. Of course its fields (components) have their addresses too. An address of the whole structure is the address of its first field.

As for i = i->next in the Snippet 4: i is a pointer to a current list item (and it is initially set to the address of a). The assignment takes value of field next of the current list item and moves this value into i. So i now points to the next list item. This just moves i one item right (it's iterating over the list). when i points to the last item of the list, then i->next is NULL, so after processing the last item i becomes NULL and the loop terminates.