I need clarification on the following C code which is used to create Linked-List in Heap memory using Dynamic Memory Allocation. The code creates a Linked-List by copying the elements of the array A. I am confused as to what values are stored in data or next as we progress downwards.
struct Node
{
int data;
struct Node *next;
}*First = NULL;
int A[] = {2, 3, 5, 7, 10};
int main()
{
struct Node *t, *last;
First = (struct Node *)malloc(sizeof(struct Node));
First->data = A[0];
First->next = NULL;
Last = First;
for(int i = 1; i < 5; i++)
{
t = (struct Node*)malloc(sizeof(struct Node));
t->data=A[i];
t->next=NULL;
Last->next=t;
Last=t;
}
}
Now, I am trying to visualize how First is created in the memory. Since Node contains two sections, data and next, when First pointer is initialized to NULL as in this statement *First = NULL, where is the 0 stored? Both of the sections? i.e.
First->data = 0;
First->next = 0;
As we continue downwards, we find the line Last = First, meaning Last->data contains 2 &
Last->next contains 0? i.e.
Last->data = First->data;
Last->next = First->next;
In the for loop, the statement Last->next=t is the most confusing. Does t->data holds 3 during the first iteration of the loop & t->next holds NULL. What exactly does this statement do?
Thank you.
Now, I am trying to visualize how First is created in the memory. Since Node contains two sections, data and next, when First pointer is initialized to NULL as in this statement
*First = NULL, where is the 0 stored?
There is no such statement in your code, for at least two reasons:
that snippet is excerpted from a declaration (of variable First), not from any statement. This is relevant in part because
excerpting it from its larger context obscures its meaning. If it were a complete assignment statement then it would express an (invalid) assignment to a structure object of type struct Node designated by the expression *First, but as it actually stands, the = NULL is an initializer for the object designated by variable First, a pointer of type struct Node *.
The pointer object designated by First is completely different from the structure object, if any, to which its pointer value points. It is crucial to understand differences such as this, between pointers and the objects to which they point.
So, "where is the 0 stored"? In the sense you mean, nowhere. No struct Node has been declared at that point. There is neither a First->data nor a First->next at that point. Initializing First to NULL expressly ensures that.
As we continue downwards, we find the line
Last = First, meaningLast->datacontains 2 &Last->nextcontains 0?
Yes and no. Last is another pointer of type struct Node *, again distinct from the object to which it points. Last = First is a pointer assignment, immediately after which, Last points to the same object, if any, that First does, which at that point is a recently mallocated object. No members of such an object are accessed or set to achieve that, but as a result, Last->data does evaluate to 2, and Last->next to a null pointer. And note well that a null pointer is not the same thing as the integer 0.
In the for loop, the statement
Last->next=tis the most confusing.
It is completely analogous to the Last = First statement you asked about previously. Pointer Last is assigned to point to the same object to which pointer t points, which is again a recently mallocated object. On the i == 1 iteration of the loop, t->data will have just been set to A[1], which is 3.
Perhaps an analogy will help drive home the key distinctions here.
Suppose I give you a card on which the street address of my house is printed. Do you then hold my house itself in your hand? No, of course not, but you could use the information on the card to go to my house to take a photo of it or make a delivery.
If you make a copy of the card and give it to a friend, then have you changed anything about my house? Or are there now two houses where once there was one? Of course not. There are now two cards both describing how to find the same house.
If your friend uses the information on their card to go to my house and paint it, then does the color of either card change? No. The cards are not the house itself. But if you afterward use the information on your card to go to my house then will you see its new color? Yes, you will, because the information on your card leads you to the same house.
If someone gives you another card with an address on it, how can you tell whether is refers to the same house? Easy: you need only compare the information printed on the card. In particular, you don't need to go to the address printed on either card.
If you burn your card, is my house damaged? Can your friend still find it using their copy of the card? Can you still find it if you happen to remember the address that was printed on it? No, yes, and yes.
If you white-out the address printed on your card, so that it is blank, does the information on it still tell you how to locate my house? Or any house? No.
My house represents an object of interest, such as a struct Node. It has parts such as doors, windows, and walls that can be examined or manipulated, somewhat like the members of a structure.
The cards represent pointer objects. In our analogy, they are all one part, which can be manipulated to record the address of a house.
The data on the cards represent pointer values, which happen to be called "addresses" in C terminology, too.
Addresses are each a uniquely identifying characteristic of a particular house / object. Addresses can be recorded on cards / in pointer objects, which are completely different things than the houses or objects the addresses on them identify. Multiple cards / pointer objects or none can contain the address of the same house / object. The fact that there is a card / pointer object does not imply that whatever is printed on it, if anything, is the address of a house / object that actually exists.