Let's take a quick review of all that we have learned about data structures
in these lessons.
- 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.
- 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
- 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
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.
- 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.