In our last lesson, we discovered a problem with representing data structures that are not linear. We need some way to map these data structures to the computer’s linear memory. One solution is to use pointers. Pointers are memory locations that are stored in memory cells. By using a pointer, one memory cell can “point” to another memory cell by holding a memory address rather than data. Let’s see how it works.
In the diagram above, the memory cell at address 2003 contains a pointer, an address of another cell. In this case, the pointer is pointing to the memory cell 2005 which contains the letter ‘c’. This means that we now have two ways of accessing the letter ‘c’ as stored data. We can refer to the memory cell which contains ‘c’ directly or we can use our pointer to refer to it indirectly. The process of accessing data through pointers is known as indirection. We can also create multiple levels of indirection using pointers. The diagram below shows an example of double indirection. Notice that we must follow two pointers this time to reach the stored data.
As you can see, pointers can become very complex and difficult to use with many levels of indirection. In fact, when used incorrectly, pointers can make data structures very difficult to understand. Whenever we use pointers in constructing data structures, we have to consider the tradeoff between complexity and flexibility. We will consider some examples of this tradeoff in the next few lessons.
The idea of pointers and indirection is not exclusive to computer memory. Pointers appear in many different aspects of computer use. A good example is hyperlinks in web pages. This links are really pointers to another web page. Perhaps you have even experienced “double indirection” when you went to visit a familiar web site and found the site had moved. Instead of the page you expected, you saw a notice that the web pages had been moved and a link to the new site. Rather than clicking a single link, you had to follow two links or two pointers to reach the web page.