Exercise: Add to the End of the List

On the previous page you learned how to add an element to the beginning of a linked list. Let's learn how to add an element to the end of the list.

The naive way of doing it would be to start from head and find an element that has its next pointer set to NULL, that would be the last element of the list, and we can make it point to our new element instead. This approach will work, but if we iterate the whole list every time we want to add an element to its end, the resulting algorithm will have a time complexity of O(N²), which is not good for such a trivial thing as adding an element.

To make it more efficient, we can store the pointer to the last element of the list. Let's call it tail. We want to create the following layout in the memory:

When we start, both head and tail are NULL. When we add an element, we check if it's the very first element being added: if so, both head and tail will point to the new element. But if it's not the first element, we don't really care about all the elements before the last one: we just assign the next pointer of the last element (the one that tail points to), and move tail to point to the newly added element.

Sounds easy enough, want to try? Keep reading numbers from the standard input while scanf("%d", &x) returns 1, and add each element to the end of the list. Then print the list twice, and then delete all elements.

Remember that when we create an element, we use malloc, and when we delete an element, we use free.

Note: in this setup with head, tail, and next pointers, we can add elements both to the beginning and to the end of the list, but we can only delete elements from the beginning of the list; deleting the last element still requires iterating over the whole list. We'll talk about this problem later; for now, just delete them one by one as you did on the previous page.

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

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

struct item *head = NULL;
struct item *tail = NULL;

void add_back(int data) {
  /* TODO: implement me */
}

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

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

  return 0;
}

The tests cannot check if you actually deleted all elements, so this part is on you!