Let's take a quick review of all that we have learned about data structures in these lessons.

  1. We began by introducing the idea of a data structure as a way of organizing data in a computer's memory. We discussed how a computer's memory is organized as a long row of memory cells with each cell having a particular address. We also examined how these memory cells can contain the address of another memory cell. These pointers allow us to build very flexible and complex data structures.

  2. We examined a class of data structures called linear data structures that are organized in a linear fashion similar to the computer's memory. The first linear data structure was the ordered list. With this data structure we introduced the idea of abstraction and implementation. We saw there are two different ways to implement a list, but both implementations still have the same list operations. The second linear data structure was the stack. We discovered that the stack is really a list with the restriction that items can only be added and removed from the top of the stack. The third linear data structure was the queue. As we studied the queue, we found that our queue implementation had two distinct representations: logical and physical. In the logical representation, our queue was similar to a ring, but in the physical representation, our queue was actually implemented with an array.

  3. We looked at another class of data structures call nonlinear data structures that are organized quite differently from the computer's memory. These data structures included multidimensional arrays, trees, and graphs. For each data structure, we examined one implementation of the data structure and discussed how the logical representation of the data structure was different from the physical representation.

  4. We introduced the idea of an abstract data type that groups a data structure with certain operations. These operations form an interface for the ADT through which the data structure can be manipulated.