Linked lists are an important data structure, and they are typically implemented using pointers. So in these notes we will review pointers, and then see how to implement a simple linked lists.
Consider the following line of code:
int n = 5;
This declares n to be a variable of type int, and it is given the initial value of 5.
In memory, we can imagine that 5 is sitting inside a box a like this:
int
---
n | 5 |
---
This box is just a region of memory, perhaps 32-bits in size (C++ does not specify a standard int size). Computer memory is adressable, which means that any region of memory has an address associated with it. Usually, we don’t care about the exact address because the exact memory location of a variable typically changes from run to run of a program (due to the operating system deciding where to put the program in memory).
So we could image the box as having an address:
int
---
n | 5 |
---
Address: 384763
The address is just made-up here, of course.
C++ lets you determine the address of a variable using the & operator:
int n = 5;
int* n_addr = &n; // address of n
The variable n has the type int, meaning that n holds a value of type int.
The variable n_addr has the type int*, meaning that n_addr holds a value of type int*, i.e. an address of an int.
You can print n_addr like this:
cout << n_addr;
What exactly gets printed will vary from run to run of your program. When I ran it I saw this:
0xbfd913c8
This is the address in memory on my computer where n is stored.
The address is printed in hexadecimal (base-16) notation (you can tell because it starts with 0x), which is usually much more convenient when you are working at a the level of memory addresses. For example, since a hex digit represents a particular 4-bit pattern, and we can see that this is a 32-bit address (8 hex digits, each 4-bits long).
In this course, we will rarely, if ever, be concerned with the actual concrete value of a pointer.
It turns out that having a pointer to a value makes it easy to get the value itself. For example:
int n = 5;
int* n_addr = &n; // address of n
cout << n_addr << endl; // prints the address of n (in hexadecimal)
cout << *n_addr << endl; // prints the value of n (as a regular int)
This is important: n_addr points to n, while *n_addr is the value of n. The * is called the de-referencing operator, and it is how you access a value given a pointer to it.
Example. Consider this code:
double a = 6.08;
double* p = &a; // p points to a
cout << a << endl; // prints 6.08
cout << *p << endl; // prints 6.08
*p = -2.1;
cout << a << endl; // prints -2.1
cout << *p << endl; // prints -2.1
This shows that you can access the value of a either using a or *p.
Example. The following code makes two different pointers point to the same value:
int n = 25;
int* p = &n; // p points to n
int* q = p; // q points to the same thing p points, i.e. n
++*p;
++*q;
cout << n; // prints 27
Here we use the ++ operator to increment the value of n via pointers to it.
As you may be aware, C++ divides the memory of a running programming into three distinct parts:
Static memory, where global variables and non-changing values go. Static memory is fixed in size at compile-time.
Stack memory, where local variables and values related to functional calls go. Stack memory is entirely automatic in C++: you never need to explicitly request or give back stack memory. C++ does all that for you automatically. The size of the stack grows and shrinks as your program runs.
Free store memory (aka heap memory) is where memory that is requested manually by the program while it is running is kept. Memory on the free store is allocated when the new (or new[]) operator is used, and the memory is de-allocated when delete (or delete[]) is used.
All free store memory is access through pointers. When you call new, it returns a pointer to a chunk of new memory on the free store, and when you call delete you must pass it a pointer to a chunk of free store memory.
An important application of the free store is that it lets us write data structures whose size changes dynamically during the run of a program.
Let’s look at some simple examples of how to use the free store.
Here’s how to allocate a single int on the free store:
int* p = new int; // new returns a pointer to an int-size chunk of memory
// on the free store; it's initial value is unknown
*p = 5; // set the int p points to to 5
You can do all this in one statement like this:
int* p = new int(5); // p points to a newly created int on the free store
// initialized to the value 5
You use *p just like a regular int, e.g.:
--*p; // *p is now 4
*p = *p / 2; // *p is now 2
When you are done with memory on the free store, you should de-allocate it so that the memory can be used again in future calls to new. You use delete to de-allocate free store memory:
delete p;
Forgetting to delete free store memory you no longer need is a subtle error known as a memory leak. Memory leaks can be hard to find because memory gets used up very slowly, one “drop” at a time.
Example. Look at the memory leak in this code:
int* p = new int;
*p = 3;
int n = 4;
p = &n; // oops: p no longer points to the int created on the free store in
// in the first line; but that int still exists, and, since it has
// not been de-allocated, it is now wasted memory
This code doesn’t cause any errors, but it does have a bug. You would probably only notice problems when it’s called many times (e.g. inside a loop), with one int being wasted each time. In a long-running program, such as an operating system, this could cause it to eventually crash.
Aside. Memory leaks, and another memory-related issues, is the source of so many bugs that many modern programming languages provide a garbage collector, which automates the task of calling new and delete for you. For instance, in the Java programming language you never need to worry about calling delete because it simply does not exist: the garbage collector automatically deletes unused memory for you. Garbage collectors exist for C++, but we will not use them in this course.
Different forms of new and delete are used to allocate/de-allocate arrays on the free store. Please see p.180-181 of the textbook for information on this.
Now that we’ve review pointers, we can introduce a new kind of data structure known as a linked list. While there are many variations, the all linked lists are based on the same idea: each value stored in a list contains both a data value and a pointer to the next value on the list.
For example, suppose we want to make a linked list of ints. We would store the ints in the following structure:
struct Node {
int value; // value of this node
int* next; // pointer to the next node
}; // struct Node
Diagrammatically, this creates a box that looks like this:
------- ------
| value | next |
------- ------