Linked Lists

Structs and arrays are allocated in consecutive memory – the array int[16] occupies 16 * sizeof(int) bytes of memory. Arrays are efficient because lookup can be performed in constant time for any given element, but the cost to insert or remove is much higher, as it involves shifting elements “left” or “right” in memory to make space for a new element or to remove the space occupied by an element.

In contrast to arrays, linked structures are constructed by many smaller elements connected by pointers, very much like a graph. Construction of a linked structure therefore (typically) requires several discrete memory allocations and pointer manipulations.

In this text, we are going to construct one of the simplest linked structures – a linked list. We will approach this task incrementally, first solving simple problems (sometimes under assumptions that simplify the current task), and slowly arrive at something solid. There is no single listing that you can copy-paste and run with – instead you should follow along with the design, and make some contributions of your own.

Inserting an element into an array (typically) means calculating where to store the element in a preallocated space. In contrast, inserting an element into a linked list (typically) means creating a new place (a new link) where the element can be stored and searching for the right place in the linked structure where the new place (link) should be added.

Here are the public functions from the header file list.h. We will add more further down in this document.

/// Creates a new list
list_t *list_new(); 
/// Deletes a list. 
void list_delete(list_t *list); 

/// Inserts a new element at the beginning of the list
void list_prepend(list_t *list, elem_t element);
/// Inserts a new element at the end of the list
void list_append(list_t *list, elem_t element); 
/// Inserts a new element at a given index. 
void list_insert(list_t *list, int index, elem_t element); 

/// Returns the element at a given index
elem_t list_get(list_t *list, int index); 

/// Removes an element from a list.
bool list_remove(list_t *list, int index); 

/// Returns the length of the list. 
int list_length(list_t *list); 

A first stab at a linked list could look like this. For good reasons, we define a type elem_t to be the element type, and for now, make the element type an int.

/// An element
typedef int elem_t;
/// A link in the linked structure 
typedef struct link link_t;

struct link 
{
  elem_t element;
  link_t *next;
};

Note that link_t is a recursive data type. A link_t may hold a pointer to another link_t in next, or next may point to NULL.

Creating a linked structure with the above definitions is as simple as allocating several link_t’s and linking them together, meaning having them point to each other through their next fields¹.

link_t *link1 = malloc(sizeof(struct link));
link_t *link2 = malloc(sizeof(struct link));
link_t *link3 = malloc(sizeof(struct link));
link1->next = link2;
link2->next = link3;
link3->next = NULL;

This creates the structure shown in Figure 1.

The auxiliary variables link2 and link3 are not strictly necessary – we could create the same structure like this:²

link_t *link1 = malloc(sizeof(struct link));
link1->next = malloc(sizeof(struct link));
link1->next->next = malloc(sizeof(struct link));
link1->next->next->next = NULL;

However, as is clearly visible above, this gives us no direct way to get to the last next field, forcing us to build chains of next->next->....

A link_t currently holds an element field and a next field. The above code examples left the element fields undefined, which is (almost) never a good idea. Let’s define a constructor for links to make sure that links are fully initialised.

link_t *link_new(elem_t element, link_t *next)
{
  link_t *result = malloc(sizeof(struct link));

  if (result)
    {
      result->element = element;
      result->next = next;
    }

  return result;
}

By using link_new() instead of simply using malloc() like before, the C compiler will force us to supply values for element and next. This means that we can rely on these fields having reasonable values³.

Inserting elements at the head of a list is simple, as can be illustrated by the following code:

link_t *my_list = ...; /// Some list
my_list = link_new(42, my_list); /// Prepend 42 to the list

What is scary about this code is that the identity⁵ of the list gets lost in the process, forcing us to update my_list with the result. If we forget to store the result in my_list, the update to the list is lost, and the compiler will not warn us. Programming like this in an imperative language often leads to aliasing problems and forces propagating changes in the system. For example, imagine a function that takes a list and wants to prepend to it:

bool some_function(list_t *list)
{
  list = link_new(42, list); /// Prepend 42 to the list
  return ...; /// return something
}

link_t *my_list = ...; /// Some list
some_function(my_list); 

The code above suffers from the same problem as before! Inside some_function() the list gets updated through the list variable, but the change is not visible through my_list which still points to the same link, which is the second link in the list according to list but first according to my_list.

This can be solved by returning list:

list_t *some_function(list_t *list)
{
  list = link_new(42, list); /// Prepend 42 to the list
  return list; 
}

link_t *my_list = ...; /// Some list
my_list = some_function(my_list); 

Sadly, this forces us to remove the bool return value from before. What is even more sad – if we forget to store the result of some_function() to my_list, we have a bug which might prove tricky to find.

Another solution to the problem is to share the variable at the call-site, instead of its contents:

/// Take a pointer to the variable holding the list
bool  some_function(list_t **list) 
{
  *list = link_new(42, *list); /// Prepend 42 to the list
  return ...; /// return something
}

link_t *my_list = ...; /// Some list
some_function(&my_list); /// Note -- value of my_list 
                         /// changes as a side-effect

Now, my_list is updated as a side-effect of calling some_function(), but if we had two variables pointing to the same list, we are back with the same problem again.

The solution lies is changing how we represent lists, and will introduce another type in the list data structure, which we will call “the list head” – list_t:

typedef struct list list_t;

struct list
{
  link_t *first;
};

For now, the list head contains a pointer to the first link in the list. This pointer may change, but there is never a need to create more than one list head for the same list. The resulting structure is shown in Figure 2.

We are now ready to write a first working list_prepend():

void list_prepend(list_t *list, elem_t element)
{
  list->first = link_new(element, list->first);
}

The beauty of this function is that it operates on the list head – and the list head is always the same, regardless of how the list changes. As is visible from the above, prepending to a list list changes the value of list->first, but list stays the same. We can now write the code for creating a list much nicer than before, using a combination of functions whose names give us a good idea of what they do, but hide how they do it.

list_t *list = list_new(); /// Constructor for the list
list_prepend(list, 3);
list_prepend(list, 2);
list_prepend(list, 1);

To highlight that the identity of the list is preserved, let us create an alias⁶ to list and use both to call list_prepend(). This code creates the equivalent list as in the code block just above.

list_t *list = list_new(); /// Constructor for the list
list_t *same_list = list; /// Create an alias for list called same_list
list_prepend(list, 3);
list_prepend(same_list, 2);
list_prepend(list, 1);

Since prepend always inserts elements first in the list, we must add the elements in reverse order. Note how this matches the evaluation order of the calls to link_new() in Listing 2.

Prepending, as we have seen, is simple and straightforward – especially after introducing a new list_t struct to act as a front-end to the chain of links. Appending – insertion at the back of a list – is a tiny bit more complicated in the current setup, because we must first search for the last element before we can update its next field to point to a new link.

Here is a first attempt⁸ at writing an append function for lists. We introduce a local variable cursor that points to a link_t and “swing this pointer forward” through the chain of links until it reaches a link whose next field is NULL. Once we have a pointer to this, last, link, we can simply update its next field to point to a new link whose next field is NULL.

void list_append(list_t *list, elem_t element)
{
  link_t *cursor = list->first; 

  while (cursor->next != NULL)
    {
      cursor = cursor->next;
    }

  cursor->next = link_new(element, NULL);
}

SPOILER The reason why this code is faulty is because it does not handle the case when the list is empty. When the list is empty, cursor will be NULL, and testing cursor->next != NULL will SEGFAULT. A straightforward way to handle this case is to test for this condition specially and, for example, call prepend which handles this perfectly.

A perhaps less obvious aspect of the code above is the linear time complexity. In order to find the last link, we must follow all but the last next pointers in the list.

Luckily, aliasing – the same concept that brought us trouble when we took an initial stab at writing list_prepend() – can help us here. To allow constant time append operations, we extend list_t with a last pointer in addition to the first pointer. Here is the new list_append() which also deals with appending to an empty list.

void list_append(list_t *list, elem_t element)
{
  /// Check if the list is empty
  if (list->last == NULL)
    { 
      /// Append on an empty list is same as prepend
      list_prepend(list, element);
    }
  else
    {
      /// Insert element at the end of the list
      link_t *link = link_new(element, NULL);
      list->last->next = link;
      /// Update the last pointer to point to the new last element
      list->last = link;
    }
}

Note that list_prepend() must change to update the last pointer when inserting into an empty list.

void list_prepend(list_t *list, elem_t element)
{
  link_t *link = link_new(element, list->first);

  /// If list is empty, make the new element the last element
  if (list->first == NULL)
    { 
      list->last = link;
    }

  list->first = link;
}

Getting rid of the loop not only makes the code faster, it also made the code much simpler.

Removing elements from a list requires unlinking them from the chain. Consider unlinking the second element from the list in Figure 3.

After unlinking, link1->next points to link3, as shown in Figure 4.

As is visible above, unless we explicitly nullify link2->next, it too will point to link3, making link1->next and link2->next aliases. However, since our plan is to get rid of link2, we do not really care about the value of link2->next.

Subsequent to the unlinking we will return the memory for link2 to be reused, as indicated by the gree tag in Figure 5.

Consider a function void list_remove(list_t *list, int index), which, given a valid⁹ index into a list, will remove the element associated with that index from the list. As per usual with C, the first element’s index will be 0. Thus, list_remove(list, 1) would unlink the second element, like in the sketches above.

The implementation of list_remove() will resemble the first sketch of list_append() – as usual in a linked structure, we must search for the n:th link to be deleted. As we noted above, unlinking a link means changing the preceeding link’s next. Thus, as we search for the link to remove, we want to stop on the link just before.

Simplifying a little further, let us assume that the function is never called with index == 0. In that case, the following will do the trick:

void list_remove(list_t *list, int index)
{
  link_t *cursor = list->first; 

  /// Note index - 1 to stop on the preceeding node
  for (int i = 0; i < index - 1; ++i)
    {
      cursor = cursor->next;
    }

  link_t *to_remove = cursor->next;  /// Save pointer to link
  cursor->next = to_remove->next;    /// unlink link
  free(to_remove);                   /// return memory for link
}

The reason why the function above does not handle index == 0 is similar to why our first list_append() did not work on an empty list. Concretely, there is no way to get a pointer to the link preceeding the first link. Thus, the algorithm above is not general enough to cover all cases.

Instead of solving this by adding a special case for when index is 0, let’s consider another way of solving the problem – by adapting the data structure to match the algorithm. This is a time-honoured tradition, and serves to make code cleaner and simpler at the cost of some memory overhead¹⁰. Instead of defining an empty list like a list whose first and last are both NULL, we can add a special “sentinel object” (aka “dummy link”) and define an empty list as one whose first and last both point to this object. Figure 6 shows an empty list with a sentinel.

With this definition of the empty list, the list_remove() that we wrote above, works perfectly also when index == 0!

Figure 7 shows what a list with two elements look like when using a sentinel.

Of course, this change also requires us to update the other functions that we have written:

1. list_new() must create the sentinel object
2. list_prepend() must skip over the sentinel object
3. list_append() can be simplified thanks to the sentinel object

We now perform those changes in order and list the resulting code.

list_t *list_new()
{
  list_t *result = malloc(sizeof(struct list));

  if (result)
    {
      /// Use of calloc will ensure result->first->next == NULL
      result->first = result->last = calloc(1, sizeof(struct link));
    }

  return result;
}

void list_prepend(list_t *list, elem_t element)
{
  link_t *link = link_new(element, NULL);

  /// If list is empty, make the new element the last element
  if (list->first == list->last) /// CHANGE: new way to check for empty list
    { 
      list->last = link;
    }

  list->first->next = link; /// CHANGE: skip over sentinel
}

void list_append(list_t *list, elem_t element)
{
  list->last->next = link_new(element, NULL);
}

Note that the last three changes do not constitute a refactoring step – they are not improving how already correct code performs a task. Without these changes, the code would not be correct. If we had started with a working list remove, we could consider the addition of the sentinel (and the corresponding changes to remove, append, prepend and new) a refactoring step.

As a last exercise in dealing with sentinels, we can build list_size(), which calculates the size of the list by counting the number of links skipping the sentinel:

int list_size(list_t *list)
{
  int size = 0;

  for (link_t *cursor = list->first->next; cursor; cursor = cursor->next)
    {
      ++size;
    }

  return size;
}

Later, we shall revisit this function to see how it can be written in a way that amortises the cost of checking size over several functions.

So far, we have functions for creating a new list, inserting elements at the end and at the back, and removing elements at a given index. Now it is time to add functions for accessing elements with list_get().

Getting the elements at index i is similar to removing elements – we must get a pointer to the i:th link (not counting the sentinel) and use this pointer to read the element field. As a first stab, we can write a function that assumes the index argument is valid.

elem_t list_get(list_t *list, int index)
{
  link_t *cursor = list->first->next; /// Skipping over the sentinel

  for (int i = 0; i < index; ++i)
    {
      cursor = cursor->next; 
    }

  return cursor->element;
}

Note that index logic is non-trivial – we allow negative indexing, and reinterpret indexes which are too small or too big. Furthermore, index adjustment comes up in several places in the code. These two reasons suggest that it is sensible to build a single function to handle this logic that can be called from many places. It also serves to make the code easier to read. For now, let us cheat and assume the existance of a function list_inner_adjust_index(a, b) that is able to (somehow) translate an index a to a valid index in the range [0-b).

To adhere to the principle of always having a running program, we define a stub which simply echoes back the given index, but with a /// TODO marker in the source, which will prompt us to go back and fix it later.

int list_inner_adjust_index(int index, int upper_bound)
{
  return index; /// TODO!
}

With this function in place, list_get() no longer needs to dodge index handling:

elem_t list_get(list_t *list, int index)
{
  link_t *cursor = list->first->next; /// Skipping over the sentinel

  int valid_index = list_inner_adjust_index(index, list_size(list));

  for (int i = 0; i < valid_index; ++i)
    {
      cursor = cursor->next; 
    }

  return cursor->element;
}

Appending and prepending elements is useful, but given that lists are ordered sequences, it makes sense to support insertion of elements at any valid index. For this purpose, list’s interface contains the function list_insert(list_t *list, int index, elem_t element). Notably, prepending is inserting at index 0. Likewise, appending to a list of size n is insertion at index n. Thus, with list_insert() in place, we should be able to rewrite list_prepend() and list_append() thus:

void list_prepend(list_t *list, elem_t element)
{
  list_insert(list, 0, element);
}

void list_append(list_t *list, elem_t element)
{
  list_insert(list, list_size(list), element);
}

This list_append(), while simple, suffers from a regression – the cost of appending suddenly went from O(1) to O(elements). We mark this with a /// TODO <appropriate explanation> and keep going for now. After all, the list still works.

Implementing list_insert() is reminiscent of list_remove() and list_get() – we must iterate over the list to find the place of insertion. Given that we are coming up on the third time of implementing this logic, surely there must be some way to extract it into a function of its own?

Let us define the function list_inner_find_previous() that, given a pointer to the first link in a chain of links and an index i, traverses the chain to get to link i-1. A function that finds the previous link is more generally useful as it supports both unlinking and getting the i:th link by simply taking one more step in the chain. Note that this function is possible to write because of the sentinel. Without it, we would not have been able to get a pointer to the link preceeding the first link¹¹.

link_t *list_inner_find_previous(link_t *link, int index)
{
  link_t *cursor = link;

  for (int i = 0; i < index; ++i)
    {
      cursor = cursor->next;
    }

  return cursor;
}

With this function in place, it is possible to define list_insert() in a straightforward manner. Again, we make use of list_inner_adjust_index(), but note how we add 1 to the upper bound, so that we are able to position ourselves on the last link, so that the result of writing the next field is an append.

void list_insert(list_t *list, int index, elem_t element)
{
  int valid_index = list_inner_adjust_index(index, list_size(list) + 1);

  link_t *prev = list_inner_find_previous(list->first, valid_index);

  prev->next = link_new(element, prev->next); 
}

This code is wondefully straightline and operates at a high-level, making it almost as readable as natural language. From the index supplied as argument, create a valid index upper-bounded by the list’s size plus one. Then, find the node before this new index, and replace its next node with a new node, whose next field points to the old next.

Let us now back up and update list_remove() and list_get() to use the helper function list_inner_find_previous(). Like insert, they will be simplified by removing the iteration step.

void list_remove(list_t *list, int index)
{
  int valid_index = list_inner_adjust_index(index, list_size(list));

  link_t *prev = list_inner_find_previous(list->first, valid_index);
  link_t *to_remove = prev->next;

  prev->next = to_remove->next;
  free(to_remove);
}

elem_t list_get(list_t *list, int index)
{
  int valid_index = list_inner_adjust_index(index, list_size(list));

  link_t *prev = list_inner_find_previous(list->first, valid_index);

  return prev->next->element;
}

Even though the refactoring step was prompted by the realisation that some functions could/should be rewritten to take advantage of some new functionality, we should search the code for /// TODO markers to see if anything warrants fixing. Since we are not in the middle of implementing some functionality, we might as well spend a few minutes on backlog and get list_inner_adjust_index() up and running. This is left as an exercise for the reader.

We also have a /// TODO regarding list_append(). There are (at least) two ways to fix this:

1. Revert to the previous implementation that used list->last.
2. Add a special case to list_inner_find_previous() that jumps directly to list->last when index == upper_bound.

Arguments can be made as to what solution is preferable. Make up your own mind, and apply the fix!

So far we are missing the dual function of list_new() – list_delete(). Just as we use a standard naming convention for constructors, we name destructors for objects of type t t_delete(). Destructors are very tricky to get right in languages like C that use manual memory management because we must answer the question “what to delete”. For example, if elem_t was not an int but char * – should deleting a list of strings delete all the strings in the list as well? There is no one true answer to this question as it wíll vary on a case by case basis¹².

Since elem_t is defined as int, we get to dodge this issue (for now). However, we still need to be able to delete an entire list.

The right way to implement list_delete() is by reusing the logic we already implemented in list_remove(). This function removes a link for a given index, and frees up memory. Intuitively, to delete a list with n entries, we need to make n calls to list_remove(), and then free the list head itself.

Here is a first stab¹³

void list_delete(list_t *list)
{
  while (list_size(list) > 0)
    {
      list_remove(list, 0);
    }

  free(list);
}

At a first glance, this seems like perfectly valid code but if we compile our program and run it through valgrind, the tool will report a leak of calloc’d memory in list_new().

Both list_size() and list_remove() are public functions that (for good reasons) do not expose the existance of the sentinel. The fix is simple, simply add free(list->first) on the 2nd-last line of the function above to delete the sentinel before deleting the list head.

void list_delete(list_t *list)
{
  while (list_size(list) > 0)
    {
      list_remove(list, 0);
    }

  free(list->first); /// Free the sentinel
  free(list);
}

Because C is such a low-level language, writing generic data structures in C is a lot of work. We will now change the list so that it is able to store arbitrary values.

The first step is to redefine elem_t. If we wanted lists to only hold pointers of some kind, we could define elem_t as void *, but to allow lists with primitive data, we will make elem_t a union:

typedef union elem elem_t;

union elem
{
  /// TODO: update the names of the fields to something better? 
  int i;
  unsigned int u;
  bool b;
  float f;
  void *p;
  /// other choices certainly possible
};

Now, a list knows that it is reading and writing elements of type elem_t, but the client for each list must keep track of what is actually stored inside the elem_t’s.

To allow the list to operate on its elements, we will rely on function pointers supplied by the programmer. Consider for example the function list_contains() which checks if an element is a member of a list. If the list does not know the type of its elements – how can it compare them?

Let us now define a function to do so, in the same style as strcmp() – the string comparison function. strcmp(a,b) returns 0 when a and b are equal, a number <0 if a comes before b in lexicographic order, and >0 if b comes before a in lexicographic order. For integers, this is easy to implement by simply returning b - a¹⁴.

int compare_int_elements(elem_t a, elem_t b)
{
  return b.i - a.i;
}

To simplify passing this function in as argument to list_contains(), we define a type, cmp_fun_t. The syntax for doing so is arguably one of the darkest corners of C:

typedef int(*cmp_fun_t)(elem_t a, elem_t b);

We are now ready to write list_contains(). This function is relatively straightforward – iterate over the links and apply the function to all elements until the result is 0, which means the element is found, and return true. If we manage to reach the end of the list without finding the element, we return false.

bool list_contains(list_t *list, elem_t element, cmp_fun_t cmp)
{
  for (link_t *cursor = list->first->next; cursor; cursor = cursor->next)
    {
      if (cmp(cursor->element, element) == 0) return true;
    }

  return false;
}

Let us now go back and change the list so that list_size() becomes a constant time operation. We do this by amortising the cost of keeping track of the number of elements in the list across all calls to functions that add or remove elements.

First, we add a size field to struct list. Because we used malloc() and not calloc() to create a new list, we need to update list_new() to intialise size with 0. We really should have been using calloc() in list_new() in the first place. This way, any addition to the struct would become initialised to zero automatically, which feels a lot more future proof. Thus, the new list_new() becomes:

list_t *list_new()
{
  list_t *result = calloc(1, sizeof(struct list)); /// CHANGE: malloc => calloc

  if (result)
    {
      result->first = result->last = calloc(1, sizeof(struct link));
    }

  return result;
}

Next, we add list->size += 1 to all functions that insert elements and list->size -= 1 to all functions that delete elements.

Because of our previous refactorings, any insertion falls back on list_insert(). That means that if suffices to put list->size += 1 there and only there¹⁵. There is only a single function that removes elements, so the only list->size -= 1 goes in list_remove().

Now, the size field will change as a side-effect of inserting or removing elements. This allows us to implement list_size() like so:

int list_size(list_t *list)
{
  return list->size;
}

Seeing as list_size() is a function called by many other functions in the list implementation, the performance of this function is really crucial for the overall performance of the list.

In the end, we have arrived at a solid implementation of a linked list.