As we have learned, arrays are used to manage lots of values with a single “variable” (plus an index for each element). Arrays in C++ are very efficient (accessing individual elements takes virtually no time at all, thanks to random-access memory), but inserting new elements in the middle (and growing the array) takes a lot of time: the whole array has to be copied into a larger one before the insertion can take place.

An alternative to arrays 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.

## 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 order 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.

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

## 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: {}