In the first lesson of this section, we discussed the problem of representing relationships between employees at the XYZ company. Since these relationships are not linear, we could not adequately show the relationships using a linear data structure like a list or a stack. Instead, we needed something that looks more like a tree.

A tree is just one example of a nonlinear data structure. Two other examples are multidimensional arrays and graphs. In the next few lessons, we will examine these data structures to see how they are represented using the computer's linear memory. Remember that in the last lesson we saw that we could create a logical representation of a circular queue. Although the actual memory locations were just an array (a group of linear memory cells), we made them seem to be circular by wrapping our pointers around to the front of the array each time they reached the end. This example demonstrated that there are two ways of representing our data structure. The logical representation was a circle or a loop, while the physical representation was a simple linear array.

For each of the data structures we examine, we will look at a simple implementation for the data structure to see how it can be represented in physical memory. Then we will compare this physical representation with the logical representation of the data structure.