Notes on linked lists/pointers - March 31, 2003

A pointer is a 32-bit (on the computers we use) value that simply is an address of a location in memory.  Every piece of system memory can be addressed much as every spot on Earth can be addressed using latitude and longitute coordinates.  Just like latitudes and longitudes, the values matter as you wouldn't like to build your house in the Artic Ocean by accident, you also don't want to overwrite important pieces of data in the system memory (like the operating system for instance...).  This is why pointers can be very dangerous.  They also afford us some interesting advantages, such as the linked list.  

The syntax for pointers is fairly simple initially.  To declare a variable as a pointer to a variable you add the * in front of the name when declaring it.  For instance, to declare a pointer to an int named var you would do the following:

int *var;

When you are using the variable if you use var without an * in front of it, you are referring to the 32-bit value saying where the int is that you are addressing, with the * in front of it, you are referring to the actual int that you are supposed to be pointing to.

Note:  when you declare the int *var you aren't actually pointing to anything.  You need to have it point to an integer before you try to access it otherwise you may have big problems.  To tell C++ to allocate room for a new variable you can use the new keyword.  For instance to tell your var pointer to point to a new integer you can say this:

var = new int;

In addition you have the & operator which will return a pointer to a variable.  For instance if you want your var pointer to point to a normal int (non-pointer) named fred you would type the following:

var = &fred;

Linked lists are usually defined as structs, and they consist of the data you want each element to store, and a pointer to the next instance of the linked list (often called a node).  The key issues to keep in mind are that you need to keep track of where the 1st instance of the list is, and you should make sure that at the last node of the linked list you set the pointer to the next item to be 0 such that you can easily tell you're at the end of the linked list.  

Example code on a simple implementation of a linked list (with comments) is here