Link List Tutorial                                   

by - Andrew Feller

If you are at this point, then that means you have used and know the following which I will refer to:

1.) Variables
2.) Function protocols
3.) Arrays

These are the basic 3 ideas I will try to explain the logic behind link lists, how they are implemented and how they are used.

Variables and Function Protocols

In C,if you wanted to store some kind of data, you would do so to a variable.  When you read data in C, you would almost always use the function "fscanf (" ",& );"  Didn't you ever wonder why we had to put that little ampersand there?  To unravel the mystery for you, when you call fscanf, it doesn't care what variable type you are trying to save; it just needs the variable's place in memory (address).  Basically, the ampersand gets the variable's address.  You might have heard an address being referred to as a pointer (the most dreaded idea in programming).

You are probably wondering "Ok Andy, but what in the heck do I want to do with this thing?"  That is a fair question, which I had long ago.  What is this needed for:

1.) Passing a variable to a function and letting the function change it
2.) More efficient way of passing variables in general

Do remember how in your beginning Computer Science courses, they would get you to write functions and have values returned through the parameters?  This is where the use of pointers/addresses is needed.  There are many times when more than one variable is changed by a function and needs to be returned.

Arrays

In almost every language written for a compiler, there have always been the programmer's best fried: the array.  They are wonderful, useful helpers compared to the old days of learning a new language.  The only problem with arrays is when you create them, you cannot make them smaller or larger.  You are now probably saying, "So what.  I can deal with it and so could the person using my program."  There you are wrong.

When you write programs, you cannot assume that a static amount of space will be sufficient for everything.  The program needs the ability to grow and shrink in conjunction with the user.  This is where the idea of link lists came to birth.

Link lists

The idea behind a link list is to create an array-like structure that has the ability to shrink or grow.  The basic structure of a link list is a head and a number of nodes (items in the list).  The list ends with it pointing to nothing (NULL).

HEAD    NODE   NODE   NODE   NODE   END

     If you notice in the diagram above:

1.) The nodes are made of two sections:
    Data section (which is the bigger of the two boxes)
    Pointer section (which is the smaller box with the lines)
2.) The head of the list has a pointer that starts the list

The structure of the head and nodes can be anything you need them to be.  If you are making a list of mailing labels, the data the node can hold might be a person's name, address, and some personal information.  If you a making a list where you want to keep track of the last item of the list, you can make the head point to the beginning and the end of the list.

Implementing the link list

To implement the link list, you have to write your head and node structures.  Here is an example of a simple link list.

Ex.
===========================================================

typedef struct listNodeType
{
char name [NAME];             //This is the data portion that can
int age;                      //have anything but is a better idea
char gender;                  //to consoldate your data in another
                              //structure
struct listNodeType * next;   //This is your pointer to the next item;
}listNodeType;

typedef struct LType
{
listNodeType * first;         //These three variables are pointers
listNodeType * last;          //to different items in the linklist
listNodeType * current;
} LType;

typedef struct LType * listType;  //Trust me, just do this

===========================================================

To elaborate on what I did and why I did it that way, let us start with the node structure.  As you can see, any type of variable can be put in the structure.  However, it is the best idea to make a structure that holds these items and put the structure in the node.  After the data variables, you will notice there is a variable called next that is declared the same way as the node structure.  This is because the next node is going to be the same as the one you are declaring.  You always have to remember to have an asterisk before the variable name; this says it will be a pointer/address.

For the structure of the list itself, if might look a little simple or a little complicated.  The head structure of the list usually is very simple because its only use is to point to a couple different items in the list.  However, you will be wondering about the statement after list structure.

When you are working with a list, the head is always used as a pointer.  I cannot explain if there are any other reason I don't know about; it is just done this way.  So now instead of declaring a list with LType, it can be done using listType.

Using a link list

Every time you want to create a new link list or a new item in the list, you have to check if the memory needed is available.  This is where we use the command called "malloc".  Malloc has only one parameter, which is "sizeof()".  In the parenthesis, the variable's data type is needed.

Ex.  listType list = malloc (sizeof(listType));

After the malloc is called, it returns a pointer to the place in memory.  This place in memory is either:

1.) Memory set aside for the variable
2.) Nothing; NULL

So now, the variable has to be checked to see if space is available

Ex. if (list == NULL)
   {
    printf ("There was not enough space for the list\n");
    return (1);
   }

To add an item to the list, there are a couple of steps to follow:

1.) Gather the data to be stored
2.) Create a new list item to hold the data
3.) Check to see if the new list item exists
4.) Insert data into the new list item
5.) Set the new list item's pointer(s) to NULL
6.) Add the new list item to the list depending how it should be added

Ex. of a function that adds a new item to the end of the list

int AddListItem (listType list)
{
   int age;
   char gender, name [NAME];
   listNodeType * new, * current;

1.) fscanf ("%s %d %c",name, &age, &gender);
2.) new = malloc (sizeof(listNodeType));
3.) if (new == NULL)
   {
    printf ("There is not enough space for another item\n");
    return (1);
   }
4.) strcpy (new->name,name);
   new->age = age;
   new->gender = gender;
5.) new->next = NULL;
   current = list->first;
6.) if (current == NULL)
    list->first = new;
   else
   {
    while (current->next != NULL)
     current = current->next;
    current = new;
   }
   list->last = new;
   return (0);
}

The only places I know you would have questions at are:

1.) Why I had to create memory for "new" but not for "current"
2.) The method I added the new node to the list

The reason why I didn't have to create a place in memory for "current" is because it is not holding any data but is being used to navigate.  The only use of it is to navigate pointers in the link list, which is its data type.

Finally, the method that I used to add the new list item is by finding where the end of the list was and adding it there.  I first check
"list->first" to see if it was equal to NULL.  Then if it wasn't empty, I checked down the item's next pointer.  While the next pointer was not equal to NULL, I could traverse or go down the list until I found the node before the end.  If I continued until I was actually at the end, I could not set the end equal to my new item, so that is why I stopped before it.

I hope that this helps you with the basics of link lists.  I know that there is a little bit more that you will learn, but you are a bright enough person that you can pick it up.

Good luck and good programming!

Add your tutorials to this site Mail Me