C6

C Tutorial

Back to Tutorials

Next Lesson

Lesson 6: Introduction to Linked Lists

Lesson Requirements
A C compiler.

Instructions on using the LCCWin32 Compiler.

Lesson Summary
This Lesson covers pointers, structures, and memory allocation in more detail and applies them to one of their most common uses.

What is a Linked List?
Going for the obvious: "it's a list that is linked". Occasionally, you may want to store a list of data, such as the player list we had in the 5th C Lesson on Structures. You might wonder why we would want to use linked lists instead of the simpler array.

Basically, an array is a fixed size, meaning that when we write the program we decide how many entries there will be. In the case of a list of Quake players, an array is fine as Quake only allows up to 16 players. So we would declare an array of size 16. However, we might wish to have a list that we don't already know the length of.

The beauty of linked lists is that they are dynamic -- we can let them grow or shrink as much as we like (provided our computer has enough memory), whereas an array has a static size and always uses up the same size of memory. For example, let's consider a list of players represented as an array and as a linked list, with the array defined as:

/* player struct is declared in 5th C Lesson */
struct player players[15];

We have allocated sixteen blocks of memory (each block being the size of our player structure). If there are only four players in the game, we would end up wasting eight blocks of memory. But if we used a linked list we would only use what we require. In addition, we do not limit the size of the linked list whilst we are programming -- it can dynamically grow and shrink as players join or leave the game.

Building a Linked List
First of all, we need a data structure to store the list information in. You might recall the structure player from the 5th C Lesson:

struct player
{
  char name[40];
  int health;
  int location;
};

In order to use this structure for a linked list we need to add a new field to provide the "link" between objects in the list:

struct player
{
  char name[40];
  int health;
  int location;

  /* new field */
  struct player *next;
};

This new field "struct player *next;" is a pointer to a struct of type player. Next, we require a "head" for the list as a reference to where the list begins. Typically, this might be a variable such as:

struct player *head;

Now we have the tools, so let's look at what we want to build. Our list will start from it's "head" and consist of a series of structures, each linked to the next structure by a field called "next". For example:

head -> structure_1 :

name
health
location
next -> structure_2 :

name
health
location
next -> structure_3 ...

In the table above the ':' represents an indication of the fields in the structure, and the '->' symbol show the links between structures (which gives the linked list its name!).

Quite a lot has been covered in this Lesson, but hopefully you'll have grasped enough (or everything) to attempt to build your own linked lists. As an exercise, try to write the code to build a list of 10 items, each with 2 fields (remember the third for the link!).

A possible answer will be provided in the next Lesson, along with further explanation of linked lists -- there's more to come! Remember these two things:

a. Most people find it incredibly hard to understand linked lists, so dont give up if you feel dazed by it all!

b. You'll need to build on the knowledge gained from all the Lessons so far to complete this exercise.

Till next time!

Back to Tutorials

Next Lesson