As we have learned, arrays and vectors are used to manage lots of
values with a single “variable” (plus an index for each
element). Arrays and vectors in C++ are very efficient (accessing
individual elements takes virtually no time at all), but inserting new
elements in the middle (and growing the array or vector) takes a lot
of time: the whole array/vector has to be copied into a larger one
before the insertion can take place.
An alternative to arrays/vectors is linked lists. Linked lists are not
as efficient at “jumping to the middle” and grabbing a value, but they
can grow and shrink without requiring copying the whole list.
(Note: download all the code in these lecture notes as a complete
program: list.cpp)
How a linked list works
A linked list is composed of “nodes.” Each node is a value plus a
pointer to the next node. Here is the typical linked list diagram:
So a linked list is a chain of “node” types of things. Each node must
have (at least) two things: a value and a pointer to the next
node. The value is necessary because the list is supposed to have
values in it; the value can be anything, of course (a double, an
int, whatever; maybe even something complicated like a linked list!
though that’s a little funny to think about). The pointer is
necessary in order to create the chain.
Now we can make a single node:
In oder to keep track of the contents/length of the list, we create
another class:
And now we can make a bona fide list:
There we have it. Our first linked list! It only has one node (one
value), so it’s not much of a list.
Linking nodes
Let’s make another node, so we can link the first to the second. And
then we’ll make a third, and get the equivalent of the diagram above.
Now we have the equivalent of the diagram above.
A menagerie of functions
It was tedious to make each node and then link them together. Let’s
make functions that do this for us. Since these functions will be
creating node variables using the new operator, we’ll create a
function that deletes an entire list (because when you use new you
gotta remember to delete).
Node at some position (counting from 0)
Value at some position (counting from 0)
Insert front
Push back
Insert before some position
Remove some position
Print the list
Delete list
Here is an example of how such functions can be used:
This is what we see:
empty list: {}
insert front 7.3: {7.3}
insert 1.2 before position 0: {1.2, 7.3}
insert 9.3 before position 1: {1.2, 9.3, 7.3}
delete list, then print: {}
add 4.0, 3.0 to front, 5.0 to back: {3.0, 4.0, 5.0}
val_at(0): 3.0
val_at(1): 4.0
add 2.0 to front, 6.0 to back: {2.0, 3.0, 4.0, 5.0, 6.0}
insert 4.5 before position 3: {2.0, 3.0, 4.0, 4.5, 5.0, 6.0}
insert 0.0 before position 6 (i.e., at end): {2.0, 3.0, 4.0, 4.5, 5.0, 6.0, 0.0}
remove_at(0): {3.0, 4.0, 4.5, 5.0, 6.0, 0.0}
remove_at(2): {3.0, 4.0, 5.0, 6.0, 0.0}
remove_at(4) (i.e., remove end): {3.0, 4.0, 5.0, 6.0}
remove_at(-1) (should do nothing): {3.0, 4.0, 5.0, 6.0}
remove_at(2): {3.0, 4.0, 6.0}
delete list, then print: {}