Explanation of code (linked list C)

Question

This is not my code. I took this code off this website:

http://www.macs.hw.ac.uk/~rjp/Coursewww/Cwww/linklist.html

I am using for reference material on how to build a linked list. I'm a little confused on what is going on. Can someone please explain to me what is going on. I'll mark what is confusing me with 1-5.

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

struct list_el {
   int val;
   struct list_el * next;
};

typedef struct list_el item;

void main() {
   item * curr, * head;
   int i;

   head = NULL;   //1

   for(i=1;i<=10;i++) {
      curr = (item *)malloc(sizeof(item));
      curr->val = i;
      curr->next  = head; //2
      head = curr; //3
   }

   curr = head; // 4

   while(curr) {  //5
      printf("%d\n", curr->val);
      curr = curr->next ;
   }

1. head = NULL → why is head being set to NULL? I know that you are supposed to (I do it out of habit) but I don't really know why.

2. curr->next = head → I never really understood this as well. Maybe I have my definition of "head" wrong but in a regular linked list, is it the starting node or the last node on the list? I've always assumed it was the starting node but in this line it looks like it's the last node.

3. head = curr → Why are we setting it equal to curr?

4. curr = head → and then setting curr = head after the loop is done.

5. while(curr) → Just to make sure, this is traversing through the list and it is equivalent to while(curr != NULL) right?

Answer 1

#1: head = NULL

Initializing the pointer. It's generally recommended to initialize the pointer to NULL either (1) at declaration or (2) immediately after declaration. If programmers mistakenly dereference uninitialized pointers, garbage values are returned. Often times, this is extremely hard to debug if your static analyzer and compiler don't display warning or error messages for uninitialized pointers.

For more information, please refer to Steve McConnell's Code Complete: A Practical Handbook of Software Construction or Wikipedia page on Defensive Programming.

#2: curr->next = head

Building the linked list. The curr node is being "linked" to previously created node in the sequence.

#3: head = curr

Updating the head pointer. The head pointer is being updated to point to the most recently malloced node.

Below illustrations visualize Steps #2 and #3:

#4: curr = head

Re-initializing the pointer. This step is similar to step #2:curr->next = head. By setting curr node to head, curr gets "ready" for linked-list traversal in the while loop. Analogically speaking, it's like initializing the iterating variable to 0 in the beginning of the loop (i.e. i = 0). To visualize this step, please refer to the below illustrations showing before/after this statement is executed:

#5: while(curr)

Traversing the list. Given that curr is pointing to the first node (from step #4), this while loop traverses the list until curr->next returns NULL. In a less abstract form, we can rewrite this statement as while(curr != NULL).

Answer 2

1. head is pointing to the head of the list. Since the list is currently empty, it's set to null
2. When you add a node to the list, you set the "next" pointer to the current head of the list. The puts the new node at the head of the list.
3. You set "head" to "curr" to make the new node the head of the list.
4. After the loop is over, you're re-using the "curr" variable to traverse the list.
5. You're going through the list setting "curr" to each node in turn until you go off the bottom of the list (where curr->next is null)

Answer 3

(1). You need to set it to something and using NULL is a way to say it's not pointing to anything. Usually NULL is the same as 0. In some languages, you don't need to initialize the variable because it'll automatically set it to nil. But C doesn't do that so you have to do it yourself.

(2). head is pointing to the first node of the list. At first, it is NULL, which means the list is empty and thus head not pointing to anything. cur is a new node that wants to be inserted into the list. curr->next wants to point to the first node of the existing list, so that's why curr->next is set to head.

(3). At this point head is no longer pointing to the first node. The first time through the loop, it looks like this:

curr-->node1-->NULL
         head--^

But in general it would look like this

curr-->node3-->node2-->node1-->NULL
          head--^

So we need to update head to point to the first node. Since curr is pointing to the newly created node, which is placed at the front, we just set head to point to the same node as curr.

(4). The first part of the program is done. curr is no longer needed because it was used to keep track of the new node we created. It was a temporary variable. This line curr = head means we're going to initialize curr to the beginning of the list. We could've used another variable to make it more readable, but you typically see reuse of temporary variables.

(5). Right. You'll probably see NULL defined as (void*)0, so it's the same as 0. You'll probably never see another value other than 0 except for really old machines from the 60s or 70s. So logically, it's equivalent to: while (curr != 0) which is the same as while (curr).

Answer 4

1. head = NULL → why is head being set to NULL?
It's good practice to initialize your variables. On some systems declared variables have whatever happened to be in memory when the address space is grabbed.

2. curr->next = head → I never really understood this as well. Maybe I have my definition of "head" wrong but in a regular linked list, is it the starting node or the last node on the list? I've always assumed it was the starting node but in this line it looks like it's the last node.
Yes, the head is the starting node.

3. head = curr → Why are we setting it equal to curr?
This loop here adds new nodes as the head. Like a stack. Other ways of doing it add new nodes on the tail. Both ways are still "linked lists".

4. curr = head → and then setting curr = head after the loop is done.
curr is acting like an index, a working variable so you don't distrupt the data structure. He's resetting it after he's done. "Rewinding the tape" if you will.

5. while(curr) → Just to make sure, this is traversing through the list and it is equivalent to while(curr != NULL) right?
Yes, that's one of those implied things you find in C. Anything all by itself in a while loop is implicitly while(whatnot != 0) and null == 0.