|
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).
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
|
