Link List Tutorial by Andrew Feller
you are at this point, then that means you have used and know the following
which I will refer to:
are the basic 3 ideas I will try to explain the logic behind link lists, how
they are implemented and how they are used.
and Function Protocols
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).
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:
Passing a variable to a function and letting the function change it
More efficient way of passing variables in general
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.
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.
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.
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).
If you notice in the diagram above:
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)
The head of the list has a pointer that starts the list
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.
the link list
implement the link list, you have to write your head and node structures.
Here is an example of a simple link list.
//This is the data portion that can
//have anything but is a better idea
//to consoldate your data in another
listNodeType * next; //This is your pointer to the next item;
* first; //These three variables
* last; //to different
items in the linklist
struct LType * listType; //Trust me, just do this
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.
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.
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
a link list
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.
listType list = malloc (sizeof(listType));
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
now, the variable has to be checked to see if space is available
if (list == NULL)
printf ("There was not enough space for the list\n");
add an item to the list, there are a couple of steps to follow:
Gather the data to be stored
Create a new list item to hold the data
Check to see if the new list item exists
Insert data into the new list item
Set the new list item's pointer(s) to NULL
Add the new list item to the list depending how it should be added
of a function that adds a new item to the end of the list
AddListItem (listType list)
char gender, name [NAME];
listNodeType * new, * current;
fscanf ("%s %d %c",name, &age, &gender);
new = malloc (sizeof(listNodeType));
if (new == NULL)
printf ("There is not enough space for another item\n");
new->age = age;
new->gender = gender;
new->next = NULL;
current = list->first;
if (current == NULL)
list->first = new;
while (current->next != NULL)
current = current->next;
current = new;
list->last = new;
only places I know you would have questions at are:
Why I had to create memory for "new" but not for "current"
The method I added the new node to the list
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.
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
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.
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