Originally published by Robert Beisert at fortcollinsprogram.robert-beisert.com

Linux + C – Linked Lists are Applied Pointers

We now understand (at least a little bit) how we can work with pointers. We’re now going to look at one of the simplest, but most useful, data storage structures – the Linked List

Referencing a Pointer

Before we go any further, we need to look at a bit of syntax. We know that when we have an object, we can reference an data member of that object with the format:

OBJECT.MEMBER

However, when we have a pointer to an object, we have to use an arrow created by a minus sign and a right bracket (->). That looks like this:

OBJECT->MEMBER

The basic idea behind this is that, when we have an object, we can go directly into the object. However, when we have a pointer, we have to point into that object. It doesn’t seem like it should make a difference, but it does.

Linked List

So far, almost everything we’ve done has revolved around single objects, but we usually have to deal with a bunch of data. We could try to put all of it into an array, but we run into an interesting problem: we don’t usually know exactly how many objects we’re going to deal with.

This is where a list comes in handy.

A linked list is a structure with a minimum of two fields: a value, and a pointer to the next object in the list. For example, we could have a list of integers (say, temperature measurements) that looks like this:

struct temperature_list
{
int fahr_temp;
struct temperature_list *next;
};

There are a few basic operations we perform on linked lists:

  •     Get_Next() – retrieve the next object in the list
  •     Find() – look for an object with a particular value
  •     Get_Last() – Go to the end of the list and give us that value
  •     Add_to_end() – Go to the end of list, create a new object, and stick it in there

The algorithms for each operation are fairly simple. For Get_Next(), we just return the object at *next.

For Find(), we usually use either a recursive algorithm or a while() loop to select between:

  •     Wrong object – go to next
  •     Right object – return pointer to object
  •     End of List (and wrong) – return NULL pointer or do some other error handling operation

For Get_Last(), we look for some marker that defines the last object in the list. There are two easy ways to do this:

  •     If the Last object has the value next == NULL, we just check whether next == NULL
  •     If the Last object has the value next == first, we check whether next == first

For Add_to_end(), things get a little bit trickier. In order, we have to

  •     Go to the end of the list
  •     Create a new object
  •     Make the end of the list point to the new object
  •     Fill in the new object
  •     Make the new object the end of the list (using whatever method you set)

We also will often try to take things out of the list, but that’s a lot of content for one section. We’ll talk about the creation and deletion cycle later (specifically, malloc() and free()).

In the example code, we’ll show an example of each of these operations.

linked_list.c

For this example, we’re going to create a linked list where the end of the list points to NULL.

Also, there is one MAJOR bug in this code. I’ve hinted at it above, but see if you can figure it out what it is. Don’t worry – most modern operating systems will keep this bug from affecting the rest of your system…

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

//We'll create this structure with a unique ID value called measurement_number
//We often want to create a unique ID for our list objects
struct temperature_list
{
int measurement_number;
int fahr_temp;
struct temperature_list *next;
};

//Look at how easy it is to find the next object in the list
/**
Retrieve the next item in the list
@param current    The current item in the list
@return        A pointer to the next item in the list
**/
struct temperature_list * get_next(struct temperature_list *current)
{
if(current ==NULL)
return NULL;

return current->next;
}

//It's not hard to use a while() loop to get to the last object.
//However, on a large list, this can take a little while.
/**
Retrieve the last item in our list
@param first    A pointer to the first element in the list
@return        A pointer to the last object in the list
**/
struct temperature_list * get_last(struct temperature_list *first)
{
if(first ==NULL)
return NULL;

struct temperature_list *navi = first;
while(navi->next != NULL)
navi = navi->next;
return navi;
}

//Meh. Couldn't find a good reason to use this function this time. Still, this is what it could look like.
/**
Find an item in the list by its unique value, measurement_number
@param first    A pointer to the start of the list
@param measurement    The ID value we're looking for
@return The next object on success,
**/
struct temperature_list * find(struct temperature_list * first, int measurement)
{
if(first ==NULL || measurement &lt; 0)
return NULL;

struct temperature_list *navi = first;

while(navi->measurement_number != measurement && navi->next != NULL)
navi = navi->next;
if(navi->measurement_number != measurement)
return NULL;
else return navi;
}

/**
Add a new measurement to the list
@param first    A pointer to the first item (or an empty list)
@param temp    The temperature value to store
@return        0 on success
**/
int new_measurement(struct temperature_list *first, int temp)
{
struct temperature_list * new_temp;
struct temperature_list *navi = first;

if(navi == NULL)
return 1;

navi = get_last(navi);
//malloc() can be tricky. We'll talk about it in detail later.
//More importantly, we'll talk about destroying things we've created with malloc() later.
new_temp = (struct temperature_list *) malloc(sizeof( struct temperature_list));
navi->next = new_temp;
new_temp->measurement_number = navi->measurement_number + 1;
new_temp->fahr_temp = temp;
new_temp->next = NULL;

return 0;
}

int main(int argc, char *argv[])
{
int ops;
int i;
if(argc < 2)
{
ops = 10;
printf("Default 10 elements/n");
printf("Next time, use/n/t./linked-list number_of_elements");
}
else ops = atoi(argv[1]);

//We'll put a bunch of random values into the temperature list
srand(time(0));

//The first item in the list requires special work - we'll put it here, instead of creating a new function
struct temperature_list *list;
list = (struct temperature_list *) malloc(sizeof(struct temperature_list));
list->next = NULL;
list->measurement_number = 1;
list->fahr_temp = rand() %150;

//When I was working on this, I needed to make sure it worked fine.
//This is an example of debugging/error-handling code
if(list == NULL)
{
printf("ERROR - NO LIST!n&quot;);
return 1;
}

//Time to populate the list. See how easy it is?
//Note that, because we already have an item #1, we'll get a total of ops+1 measurements.
//How would you fix this so that you only get ops measurements?
//    Answer at bottom of code
for(i = 0; i < ops; i++)
{
printf("Creating item #%d/n", i);
new_measurement(list, rand() % 150);
}

//We don't want to accidentally lost the start of the list. That means we have to create a new pointer.
struct temperature_list *navigator = list;
if(navigator == NULL)
printf("ERROR!/n");

//This works basically the same way as get_last(), only we print the values out as we go!
//Note that the pointers are not necessarily consecutive, like they were in our array earlier.
//...but they may be, in this case. After all, we're creating them one after another.
while(navigator != NULL)
{
printf("%ptMeasurement #%d:    %d/n", navigator, navigator->measurement_number, navigator->fahr_temp);
navigator = get_next(navigator);
}

return 0;
}

//Answer: you replace i=0 with i=1, because you already have one value.