How to create a linked list in C

In the previous post we saw, in a very basic way, how linked lists use memory to store data differently from arrays. In this post we go through a very minimalistic implementation of a linked list.

First thing first, we need to define what we want to store inside the list, thus we need a structure wrapping up our data:

typedef struct list
{ 
    int data;
    struct list * next;
}list;

if you have read the previous post, this is self explanatory. By the way, the above code is just a simple C structure, defining the 'data model' ( or type, or object or whatever you like to call it ) that we will use to implement the linked list. As you can see, inside the structure, we have an integer representing the data we need to store in every node of the list. Also we have a pointer to a structure of the same type, which will be used to link the next node in the list to the current one. Before someone gets scandalized, I must say that the code I show here, is not written by following any 'good code practice', but to best represent and explain the arguments treated. Also, if you look for a 'ready to use' linked list implementation, this is not the place to look for it. My intentions are to make more clear for the reader how this type of data structure works. So the code tries to be easy to be understood, not clever or safe. Comments and corrections are very welcome.

As start, we write a function that will be used to initialize the first node of our linked list. The code is basic and the function has only one parameter, representing the integer data stored into the element created. The function returns a pointer to some memory allocated with malloc(), in which we store this element. To notice how the pointer first->next is nullified. This will be done for every node added on the tail of the list, as we go ahead by building it. The null pointer is needed as reference to know where the list terminates.

list * create(int data)
{
  list * first = malloc(sizeof(list));
  first->data = data;
  first->next = NULL;

  return first;
}

next, we write a function that will give us the possibility to add a node to the list. We can choose the side where we want to add the new node. Our function adds it to the tail side of the current node. Refer to the next picture to better understand what's happening inside the code:

the function declaration:

void append( list * llist, int data )
{
  list * curr = llist;
  while( curr->next != NULL )
    {
      curr = curr->next;
    }

    curr->next = malloc( sizeof( list ));
    curr->next->data = data;
    curr->next->next = NULL;
}

the two parameters represent a pointer to the linked list and the data inserted for storage into the element added. The pointer is copied inside curr, then curr is used to traverse the list with a while loop, from head to tail, until last element, the null pointer, is reached. Once there, the null pointer is set to point to the new element's memory, allocated with malloc(), and the next pointer of this new created element is set to null, to mark the list's end. When curr goes out of scope, the memory allocated on it with malloc() will be always available by using the caller's pointer to the list. This will be available to the program until free() is called by passing this particular pointer as argument.

Our next step will be writing a function which removes an element from the list and returns the integer data stored in that element. The operation is performed again on the tail side of the list, where last list's element containing data is removed.

int pop_tail( list ** llist )
{
  list * curr = *llist;

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

  int retval = curr->next->data;
  free( curr->next );
  curr->next = NULL;

  return retval;
}

while in the append() function we just allocate some memory block, linking it to the caller's existing memory, we need pop_tail() to be able to change some of the caller's memory ( namely the llist variable ). The traditional method to allow a function to change its caller's memory is to pass a pointer to the caller's memory instead of a copy. So in C, to change an int in the caller, we pass a int* instead. To change a struct fraction, we pass a struct fraction* instead. To change an X, pass an X*. So in this case, the value we want to change is struct list*, so we pass a struct list** instead.
The first line of code, saves the address of the list in curr, which in turn is used to iterate with a while loop on each element in it. When curr->next->next points to the last element ( null ), curr->next points to the last list's element containing data. At this point, the while loop's test condition becomes false and the loop exits. The integer data in the element pointed by curr->next, is saved in retval, to be returned by the function, and the element is destroyed by passing its effective address ( curr->next ) to free(). Then, curr->next is set to null to mark the new end element of the list.

We are set to test our code, but we need a way to display the linked list's content, after we have started adding or removing data. Nothing more simple than that as the code - in a way - is already embedded in the function append(). In fact, all we need to do, is to iterate on the list, printing out each element's data.

void print( list * llist )
{
  list * curr = llist;
  printf("print:");
  
  while( curr != NULL )
    {
      printf("%d ", curr->data);
      curr = curr->next;
    }
  puts(" ");
}

as I said before, the code was written to illustrate a simple technique for the implementation of a linked list, without taking care of operational safety, nor error recovery techniques for avoiding errors such as segmentation faults. For example the print() function will throw this type of error, if it is called by passing an empty list ( null pointer ), so you need to take care to initialize with create() any list you intend to use, or re-initialize the current one , if all elements have been popped out. The same behaviour it's expected from pop_tail().
The following is the code testing the linked list implementation:

int main()
{
  /* Initializes the linked list with 10. mylist = { 10 }   */
  list * mylist = create(10);

  /* Appends 4 elements. mylist = { 10, 20, 30, 40, 50 }    */
  append(mylist, 20);
  append(mylist, 30);
  append(mylist, 40);
  append(mylist, 50);

  print(mylist);

  /* Pops 3 elements from tail side. mylist = { 10, 20 }  */
  int data = pop_tail(&mylist);
  printf("pop_tail:%d\n", data);
  data = pop_tail(&mylist);
  printf("pop_tail:%d\n", data);  
  data = pop_tail(&mylist);
  printf("pop_tail:%d\n", data);  
  print(mylist);

  return 0;
}

in the next post we will complete this implementation by adding more functionality, illustrating also how a dynamic stack may be built with linked lists.