What exactly does this code fragment do?
#include <stdio.h>
List *makeList(int n) {
List *l, *l1 = NULL;
for (int i = 0; i < n; i++) {
l = malloc(sizeof(List));
l->val = n-i;
l->next = l1;
l1 = l;
}
return l;
}
My notes say that "Given a number n, build a list of length n where the ith element of the list contains i"
But I don't get that...
The tricky thing here is that the list is built backwards, note that each element's value is set to n - i, and i counts from 0 to n - 1. So, the first element will get value n, the next one will get n - 1, and so on.
This is probably done in order to save on a variable (!); otherwise it would be required to have another pointer to remember the first node, in order to have something to return.
Also, it doesn't check the return value of malloc(), which is always scary.
For n = 0, it will return an undefined value (the value of l), which is really scary.
It creates a linked list of n nodes and returns the head of list. The values are : 1,2,3,...n (from head to tail).
It looks like this:
1 -> 2 -> 3 -> ...... -> n -> (NULL)
Does it help?
This is creating list in reverse order. In other words at the beginning last element of list is being created and its value is list size (n) - 0 (i) which is list element number.
It does something like this; each box is one malloc:
n n-1 n-2 1
^ ^ ^ ^
+--|---+ +--|---+ +--|---+ +--|---+
| val | | val | | val | ... | val |
NULL <-- next | <-- next | <-- next | <-- next |
+------+ +------+ +------+ +------+
^^--- this is returned
The data structure struct List looks like this (more or less):
struct List
{
int val;
struct List * next;
};
Its name is misleading, as it should really be "ListNode" or something like that. There is usually no dedicated "list" data structure in C, just a collection of nodes. You simply pass around the head node and treat that as "the list".
(A dedicated holder structure for the entire list might be useful if you want to store the list size to access it in constant time, or if you have a doubly-linked list and want to have both head and tail pointer available in constant time.)
Let's trace your code.
List *l, *l1 = NULL;
defines two pointer variables of type List.
for (int i = 0; i < n; i++) {
you are starting a loop, which will traverse n times. Which means, if you call this function with 5, this loop will execute 5 times.
l = malloc(sizeof(List));
creates a List value in the memory, and stores the location of that value in the l pointer variable. For every pass through the loop, a different List value is created in the memory.
l->val = n-i;
assigns a value n-i to the val field of the newly created List value. For the first pass through the loop, i will be 0, so the val will contain 5 - 0, which is 5. For the second pass, i is 1, so for the second List, the val will contain 5 - 1, which is 4, and so on.
l->next = l1;
there is a next field in the List type, which is a pointer of the same type. For the first pass, li contains NULL, so it will point to null. For the second pass, l1 will contain the previously created List value, so the second List's next field will point it to that, and so on.
l1 = l;
stores the memory address of the newly created created element to be used in the next pass of the loop.
At a glance:
After the first pass of the loop (i = 0) -
5->NULL
After the second pass (i = 1),
4 -> 5 -> NULL
After the third (i = 2),
3 -> 4 -> 5 -> NULL
After the fourth (i = 3),
2 -> 3 -> 4 -> 5 -> NULL
After the fifth (and last) (i = 4),
1 -> 2 -> 3 -> 4 -> 5 -> NULL
The loop builds a linked list of List objects in backwards in memory. The first element is actually the 'ith' element when the list is complete. It is created, given value 'n' and terminated with NULL.
l->val = n
l->next = NULL
The next object is effectively inserted at the front of the list (l->next = l1).
l->val = n-1
l->next ------------> l->val = n
l->next = NULL
And so on, until i=n-1.
Finally (@i=n-1), the last object created is given the value of 1, the loop terminates, and a pointer to the last created object is returned.
List *makeList(int n)line is ?