- Linked lists are considered an advanced C language topic.
That's because the linked list construction
uses pointers and memory allocation.
It's also a bit crazy to describe,
so I will be patient.
In this movie, you'll see how a linked list
is set up and configured.
I'll demonstrate how it's used
and how to access its members.
All this will be shown one step at a time,
so hang on.
In this code, the stats structure is defined.
A pointer to that structure is declared at line 10.
Memory is allocated for the structure at line 14.
The structure is filled on lines 22 through 24.
Finally, the printf statement starting at line 27
displays the structure's values.
Build and run this code.
I'll type in a pitiful amount.
And it works.
Say you wanted to create more of these structures
by allocating additional chunks of memory.
You could put them into an array.
An array of structures is something
that's completely possible in the C language.
But how big would you make the array?
If you run a bank, and you need this code
to keep track of the accounts,
you obviously don't want to keep paying a programmer
to continuously make the array larger.
Instead, you can dynamically increase
the number of structures
by allocating space for new structures.
The problem is how to keep track of the structures.
Here's the secret.
Open exercise file linkedlist2.
In this code, another member
is added to the stats structure.
It's a pointer to another stats structure
shown in line nine.
That pointer is assigned
a memory location for another structure at line 26.
The other structure isn't created in this code,
but there's room for it
and it could be filled in with information.
But not yet.
Build and run this code.
It runs no differently from the preceding example,
but memory has been allocated for a new structure.
The problem that you run into at this point
is repetitive code,
specifically, lines 15 through 20 and lines 26 through 31.
When you see that type of thing,
it's begging for a function.
Open exercise file linkedlist3.
The first thing I did with this code
is to make the declaration of the stats structure
a global variable.
A global variable is a variable that can be accessed
in any function.
For a linked list,
the structure pretty much has to be global
because all the functions in the code need to know
the structure's definition.
You can make any variable a global variable
simply by defining it outside of any other function,
usually at the top of the code before the main function.
Do, however, avoid the temptation to make
all the code's variables global.
That works, but it's bad programming practice.
Now, I've written the 'create' function
which allocates storage for one stats structure.
It's found at line 25.
The memory is allocated and its location is returned
from the function.
If not, the program quits.
The exit function at line 34 causes the program
to immediately stop.
Control returns to the operating system.
This function is prototyped in the stdlib header file,
and it carries an argument that's passed to the
operating system, similar to the return statement
in the main function.
Back in the main function,
three structure pointer variables are declared,
each of which is used in the linked list
but not currently in this code.
'First' always holds the address
of the first structure in the list.
It's the base of the linked list.
'Current' is the structure currently being manipulated.
'New' is used when new structures are created.
Now, the word 'new' is a keyword in the C++ language,
which is why it's highlighted here.
It's not a keyword in the C language.
Now, if it is highlighted in the editor
and people tell you not to use it, they're wrong.
As long as you compile in C code, you're okay.
If you're going to go back and forth,
you'll probably need a new name for that variable.
The code does a little bit more than simply
allocate space for a structure.
It doesn't generate any output.
You could build it and run it.
But instead, open exercise file linkedlist4.
The addition here is the 'fill structure' function
starting at line 29.
It fetches information for a newly-created structure.
For the next pointer, null is assigned.
That's okay.
In fact, later you'll see
how null marks the end of the linked list.
Also, you see in line 23 how this function is called
with the 'current' pointer as an argument.
That variable references the current record
in the linked list.
For the first record, 'current' and 'first' are the same,
as shown in line 21.
For now, build and run this code.
One record is input.
Nothing is output.
That's not a linked list.
So, more modifications are needed.
Open exercise file linkedlist5.
In this code, five structures are built in a linked list.
That value is set by the 'for' statement at line 24.
Line 26 checks for the first iteration of the loop.
If so, the 'first' pointer is set up.
That's the location where the linked list starts.
Otherwise, a new structure is fetched, at line 34.
Line 35 references the new structure
from the current structure.
This is the 'link' part of the linked list.
Then, line 36 sets the current structure
to point at the new structure,
which moves forward in the list.
That structure is then filled with data
and the loop repeats.
That's the current next assignment at line 35.
That's what builds the list.
One more thing you need to add.
You need to mark the end of the linked list.
Insert a line 40.
The null pointer is the end-of-list flag.
It's not used yet, but it will be.
For now, build and run the code.
Fill in the five account values.
The next step is to write a function
that displays the contents of the linked list.
Open exercise linkedlist6.
Here are the modifications from the previous exercise.
At line 42, the linked list structures are displayed.
This starts by setting the 'current' pointer
back to the 'first' pointer,
which is the start of the linked list.
A 'while' loop then plows
through each structure in the list,
displaying the information.
The loop's condition is the 'current' pointer,
which means the loop will repeat
until that pointer's value is null.
Coincidentally, null marks the end of the list.
The loop advances because of the statement on line 48.
The 'current' pointer is updated
to point at the next structure in the list.
I confess, it's all complex.
But each structure in the linked list
points to the following structure.
That's why it's called a linked list.
Build and run the code.
And the values are displayed.
You can modify this code further, if you like.
You can add a menu that lets you
choose whether to add a structure, list structures,
even remove structures.
As long as you keep each structure in the list
linked to the following structure, it works.