Linked Lists

I told you that pointers to structs are often used in C, and we are going to look at one very common example of it. A linked list is defined by the following struct:

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

Instead of int data, you can store whatever you need. Take a look at the next pointer which points to the same struct. It allows creating chains like this:

Each rectangle here is one struct item, the left part is its data, and the right part is its next, which points to another struct item, and so on; the last one–the one I crossed out–has its next pointer set to NULL. head is the only “real” variable we have, everything else is allocated with malloc.

How do we create a chain like this in the code? Normally, we start with just one variable head:

struct item *head = NULL;

For now, let's just make head a global variable so all functions we write could see and change it. Then, look at the following function:

void add_front(int data) {
	struct item *p = malloc(sizeof(*p)); /* allocate memory */
	p->data = data;
	p->next = head;
	head = p;
}

After we call add_front(1), a new struct item will be allocated and its data field will be assigned to 1. Its next field will be assigned to NULL because head is currently NULL, but then head starts pointing to the new item, resulting in a picture like this:

Now we call add_front(2). The same sequence repeats, but now the next field is assigned to head, which points to the first struct, and head starts pointing to the new struct, giving us this:

Finally, after add_front(3), we get the final list of 3 elements:

So, the add_front function inserts an element in the front of the list, and it does this in constant time: there are no loops in the function, just a memory allocation and four assignments.

Iterating a list

How do we iterate this list, for example, to print what we have? We need to start from head and iterate until we reach its end, NULL. Our regular for loop allows to do it very naturally:

for (p = head; p; p = p->next) {
  /* do something with p->data */
}

Note that the condition of the loop, p, basically means p != NULL: NULL is zero, so of p is NULL, the condition is false. The modification expression, p = p->next, does not look like your regular ++i, but the idea is the same: p is just moved to the next element of the list.

So, to print all elements of the list, you could do this:

for (p = head; p; p = p->next) {
  printf("%d\n", p->data);
}

Deleting an element

If we used malloc to allocate some memory, we must also use free to deallocate it when we're done with it. We can write a function that deletes the first element in the list (assuming there is at least one):

void delete_front() {
	struct item *p = head->next; /* will fail if head == NULL */
  free(head);
  head = p;
}

The function will save the next pointer of the first element, free the first element, and move head to the next element (which is now first). Note that if we had just assigned head = head->next, it would've resulted in a memory leak because no one would call free for the first element. Also, if we did free(head) without preserving p = head->next first, then we couldn't have accessed head->next because head now points to a deallocated memory.

Exercise

Let's practice!

Combining all of this together, write a program that would read all numbers from the standard input and print them in the reversed order. Read while scanf("%d", &x) returns 1 (meaning it read one value), use add_front to add this value to the list, and then print the list, one element per line. Don't forget to free all memory!

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

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

struct item *head = NULL;

void add_front(int data) {
  /* TODO: implement me as above */
}

void delete_front() {
  /* TODO: implement me as above */
}

int main() {
	/* TODO:
     read all numbers from the standard input,
     add each number to the list,
     then print the list,
     then delete all elements one by one.
     Do not use arrays!
   */

  return 0;
}