In our previous lesson, we saw that it is very simple to create data structures that are organized similar to the way the computer's memory is organized. For example, the list of employee's from the XYZ company is a linear data structure. Since the computer's memory is also linear, it is very easy to see how we can represent this list with the computer. Any data structure which organizes the data elements one after the other is a linear data structure. So far we have seen two examples of linear data structures: the string data structure (a list of characters) and the XYZ company list (a list of strings).
You may have noticed that these two examples of linear data structures resemble each other. This is because they are both really different kinds of lists. In general, all linear data structures look like a list. However, this does not mean that all linear data structures are exactly the same. Suppose I want to design a list to store the names of the XYZ employees in the computer. One possible design is to organize the names similar to the example picture above. Another possible design is to use the pointers we learned about in the last lesson. While these two designs provide the same functionality (i.e. a list that can hold names), the way they are implemented in the computer is much different. This means that there is an abstract view of a list which is distinct from any particular computer implementation. We will return to this idea of an abstract view of a data structure in the next few lessons.
You may have also noticed that the example picture of the XYZ employees is not exactly the same as the original list. Take another look at the employee list to the right. When we make a list of names, we tend to organize this list in a column rather than a row. In this case, the conceptual or logical representation of a list is a column of names. However, the physical representation of the list in the computer's memory is a row of strings. For most data structures, the way that we think about them is far different from the way they are implemented in the computer. In other words, the physical representation is much different than the logical representation, especially in data structures that use pointers.
During the next few lessons, we will examine several different linear data structures with a focus on the following ideas:
- The abstract view versus the implementation
- The logical representation verses the physical representation
- Comparison of various implementations