Pointer Basics

Section 1 -- Pointer Rules

1) Pointers and Pointees

A pointer stores a reference to something. Unfortunately there is no fixed term for the thing that the pointer points to, and across different computer languages there is a wide variety of things that pointers point to. We use the term pointee for the thing that the pointer points to, and we stick to the basic properties of the pointer/pointee relationship which are true in all languages. The term "reference" means pretty much the same thing as "pointer" -- "reference" implies a more high-level discussion, while "pointer" implies the traditional compiled language implementation of pointers as addresses. For the basic pointer/pointee rules covered here, the terms are effectively equivalent.

The above drawing shows a pointer named x pointing to a pointee which is storing the value 42. A pointer is usually drawn as a box, and the reference it stores is drawn as an arrow starting in the box and leading to its pointee.

Allocating a pointer and allocating a pointee for it to point to are two separate steps. You can think of the pointer/pointee structure as operating at two levels. Both the levels must be set up for things to work. The most common error is concentrating on writing code which manipulates the pointer level, but forgetting to set up the pointee level. Sometimes pointer operations that do not touch the pointees are called "shallow" while operations on the pointees are called "deep".

2) Dereferencing

The dereference operation on a pointer only works if the pointer has a pointee -- the pointee must be allocated and the pointer must be set to point to it. The most common error in pointer code is forgetting to set up the pointee. The most common runtime crash because of that error in the code is a failed dereference operation. In Java the incorrect dereference will be flagged politely by the runtime system. In compiled languages such as C, C++, and Pascal, the incorrect dereference will sometimes crash, and other times corrupt memory in some subtle, random way. Pointer bugs in compiled languages can be difficult to track down for this reason.

3) Pointer Assignment

These study questions cover review basic features of pointers. Two of the questions make heavy use of memory drawings. Memory drawings are an excellent way to think through pointer problems.

Question 1

Consider the following drawing...

Using C, write some code that creates the above pointer structure.

Question 2

Suppose you have a pointee type called "Node" which contains two things: an int, and a pointer to another Node (the declaration for such a Node type is given below). With such a pointee type, you could arrange three Node pointees in a structure where they were pointing to each other like this...

The pointer named x points to the first Node pointee. The first Node contains a pointer to the second, the second contains a pointer to the third, and the third contains a pointer back to the first. This structure can be build using only the rules of pointee allocation, dereferencing, and assignment that we have seen. Using the declaration below, each Node contains an integer named value and a pointer to another Node named next.

C Code	Java Code
struct Node { int value; struct Node* next; };	class Node { public int value; public Node next; };

Write the code to build the structure in the above drawing. For convenience, you may use temporary pointers in addition to x. The only new syntax required is that in C, the operator -> dereferences a pointer to access a field in the pointee -- so ->value accesses the field named value in x's pointee.

Postscript