Iterators

Following the principle of starting out with something simple that seems to be able to do most of what we want, let us define an iterator as simply a pointer to a link².

typedef link_t iter_t; 

typedef%20link_t%20iter_t%3B%20%0A

We note that this adds link_t to the public interface of the list, which is something we do not want³. We remember to fix that later.

We can now add a public function to the list that creates an iterator. Remember that list->first points to a sentinel link.

iter_t *list_iterator(list_t *list)
{
  return list->first; 
}

iter_t%20%2Alist_iterator%28list_t%20%2Alist%29%0A%7B%0A%20%20return%20list-%3Efirst%3B%20%0A%7D%0A

A function that tests whether the iterator is at the end of the list is simple to implement. Because an iterator is really a pointer to a link, we can simply check whether the link has a next field that is not NULL. Because of the sentinel link, an iterator to an empty list is not a NULL pointer, but a pointer to a link whose next is NULL.

bool iterator_has_next(iter_t *iter)
{
  return iter->next != NULL; 
}

bool%20iterator_has_next%28iter_t%20%2Aiter%29%0A%7B%0A%20%20return%20iter-%3Enext%20%21%3D%20NULL%3B%20%0A%7D%0A

As a new iterator points to the sentinel, in order to get an element, we need to return the element of the next link. If you have the linked list fresh in mind, you have probably already realised why we point to the preceding link rather than the “current link”⁴.

elem_t iterator_get_current(iter_t *iter)
{
  return iter->next->element; 
}

elem_t%20iterator_get_current%28iter_t%20%2Aiter%29%0A%7B%0A%20%20return%20iter-%3Enext-%3Eelement%3B%20%0A%7D%0A

So far, things look simple enough – but we have now reached the limits for how far our definition of iter_t will get us.

As we move attempt to implement a function that moves the iterator forward through the list, we run into a problem. Consider the broken implementation in Figure 1.

void iterator_next(iter_t *iter)
{
  iter = iter->next;
}

void%20iterator_next%28iter_t%20%2Aiter%29%0A%7B%0A%20%20iter%20%3D%20iter-%3Enext%3B%0A%7D%0A

Hopefully it is obvious to you why this is not working! The iter variable is a local variable inside iterator_next(), meaning that the change to iter is visible only inside iterator_next().

One solution is to change the function to take a pointer to the pointer to the iterator. This makes the change inside iterator_next() visible to the caller.

void iterator_next(iter_t **iter)
{
  *iter = (*iter)->next;
}

void%20iterator_next%28iter_t%20%2A%2Aiter%29%0A%7B%0A%20%20%2Aiter%20%3D%20%28%2Aiter%29-%3Enext%3B%0A%7D%0A

Another solution is to add an extra level of indirection – rather than make an iterator a pointer to a link, make an iterator an object that holds a pointer to a link. We will stick with the latter design rather than the pointer-to-pointer, because having an actual iterator object is much more future proof. For one, it will allow us to extend the iterator with new fields if the need should arise.

/// Goes into list.h
typedef struct iter iter_t;

/// Goes into list.c
struct iter 
{
  link_t *current;
};

%2F%2F%2F%20Goes%20into%20list.h%0Atypedef%20struct%20iter%20iter_t%3B%0A%0A%2F%2F%2F%20Goes%20into%20list.c%0Astruct%20iter%20%0A%7B%0A%20%20link_t%20%2Acurrent%3B%0A%7D%3B%0A

This requires us to update the functions we have implemented until now, but the changes are simple – simply follow the current pointer.

Creating an iterator now requires a malloc() call to create a new struct and writing the field in the struct.

iter_t *list_iterator(list_t *list)
{
  iter_t *result = malloc(sizeof(struct iter));

  result->current = list->first;

  return result; 
}

iter_t%20%2Alist_iterator%28list_t%20%2Alist%29%0A%7B%0A%20%20iter_t%20%2Aresult%20%3D%20malloc%28sizeof%28struct%20iter%29%29%3B%0A%0A%20%20result-%3Ecurrent%20%3D%20list-%3Efirst%3B%0A%0A%20%20return%20result%3B%20%0A%7D%0A

Checking whether the iterator has reached the end of the list requires following the current pointer.

bool iterator_has_next(iter_t *iter)
{
  return iter->current->next != NULL; 
}

bool%20iterator_has_next%28iter_t%20%2Aiter%29%0A%7B%0A%20%20return%20iter-%3Ecurrent-%3Enext%20%21%3D%20NULL%3B%20%0A%7D%0A

The code for getting the current element changes in a similar way, and turns a bit unwieldy. Following the current pointer takes us to a link in the list. We must then read that pointer’s next field to get to the actual current link. We are then ready to read the element field.

elem_t iterator_get_current(iter_t *iter)
{
  return iter->current->next->element; 
}

elem_t%20iterator_get_current%28iter_t%20%2Aiter%29%0A%7B%0A%20%20return%20iter-%3Ecurrent-%3Enext-%3Eelement%3B%20%0A%7D%0A

Moving the iterator forward through the list now involves updating its current field.

void iterator_next(iter_t *iter)
{
  iter->current = iter->current->next;
}

void%20iterator_next%28iter_t%20%2Aiter%29%0A%7B%0A%20%20iter-%3Ecurrent%20%3D%20iter-%3Ecurrent-%3Enext%3B%0A%7D%0A

Finally, because an iterator is allocated on the heap, we need a destructor that can return its resources back to the system.

void iterator_delete(iter_t *iter)
{
  free(iter);
}

void%20iterator_delete%28iter_t%20%2Aiter%29%0A%7B%0A%20%20free%28iter%29%3B%0A%7D%0A

One reason for adding an iterator struct is because resetting the iterator requires us to keep extra data around in the iterator. Either we store a pointer to the first element when we create the iterator or we store a pointer to the list from which the iterator was created. We choose the latter solution because it is more resilient to change – if the first element has been removed before resetting, asking the list for the current first element will simply return the new first element.

struct iter 
{
  link_t *current;
  list_t *list; /// New field
};

iter_t *list_iterator(list_t *list)
{
  iter_t *result = malloc(sizeof(struct iter));

  result->current = list->first;
  result->list = list; /// Iterator remembers where it came from

  return result; 
}

struct%20iter%20%0A%7B%0A%20%20link_t%20%2Acurrent%3B%0A%20%20list_t%20%2Alist%3B%20%2F%2F%2F%20New%20field%0A%7D%3B%0A%0Aiter_t%20%2Alist_iterator%28list_t%20%2Alist%29%0A%7B%0A%20%20iter_t%20%2Aresult%20%3D%20malloc%28sizeof%28struct%20iter%29%29%3B%0A%0A%20%20result-%3Ecurrent%20%3D%20list-%3Efirst%3B%0A%20%20result-%3Elist%20%3D%20list%3B%20%2F%2F%2F%20Iterator%20remembers%20where%20it%20came%20from%0A%0A%20%20return%20result%3B%20%0A%7D%0A

With this in place, we can now write the iterator_reset() function.

void iterator_reset(iter_t *iter)
{
  iter->current = iter->list->first;
}

void%20iterator_reset%28iter_t%20%2Aiter%29%0A%7B%0A%20%20iter-%3Ecurrent%20%3D%20iter-%3Elist-%3Efirst%3B%0A%7D%0A

Note that we do not need to update iterator_delete() to also call list_delete() on its list field, because iterators are normally much more short-lived than the list they are iterating over, meaning it makes sense to be able to destroy an iterator without also destroying the list.

Because our iterator is positioned on the link “before” (it starts by pointing to the sentinel), removing an element is simple – otherwise, it would have required us to find the preceding element from the start of the list.

void iterator_remove(iter_t *iter)
{
  iter->current->next = iter->current->next->next; 
}

void%20iterator_remove%28iter_t%20%2Aiter%29%0A%7B%0A%20%20iter-%3Ecurrent-%3Enext%20%3D%20iter-%3Ecurrent-%3Enext-%3Enext%3B%20%0A%7D%0A

Note that while the implementation above captures the essence of unlinking, it does not free the memory of the unlinked link. This is an easy fix.

void iterator_remove(iter_t *iter)
{
  link_t *to_remove = iter->current->next; /// Cache result

  iter->current->next = to_remove->next;  /// Move forward

  free(to_remove); /// Remove link
}

void%20iterator_remove%28iter_t%20%2Aiter%29%0A%7B%0A%20%20link_t%20%2Ato_remove%20%3D%20iter-%3Ecurrent-%3Enext%3B%20%2F%2F%2F%20Cache%20result%0A%0A%20%20iter-%3Ecurrent-%3Enext%20%3D%20to_remove-%3Enext%3B%20%20%2F%2F%2F%20Move%20forward%0A%0A%20%20free%28to_remove%29%3B%20%2F%2F%2F%20Remove%20link%0A%7D%0A