|
|
|
|
|
|
|
In the last chapter, we saw that C++ has a mechanism for creating dynamic variables. These dynamic variables, which can be of any simple or structured type, can be created or destroyed at any time during execution of the program using the operators new and delete. A dynamic variable is referenced not by a name but through a pointer that contains its address (location). Every dynamic variable has an associated pointer by which it can be accessed. We used dynamic variables to save space and machine time. In this chapter, we see how to use them to build data structures that can grow and shrink as the program executes. |
|
|
|
|
|
|
|
|
Sequential Versus Linked Structures |
|
|
|
|
|
|
|
|
As we have pointed out in previous chapters, many problems in computing involve lists of items. A list is an abstract data type (ADT) with certain allowable operations: searching the list, sorting it, printing it, and so forth. The structure we have used as the concrete data representation of a list is the array, a sequential structure. By sequential structure we mean that successive components of the array are located next to each other in memory. |
|
|
|
|
|
|
|
|
If the list we are implementing is an ordered list-one whose components must be kept in ascending or descending order-certain operations are efficiently carried out using an array representation. For example, searching an ordered list for a particular value is quickly done by using a binary search. However, inserting and deleting items from an ordered list are inefficient with an array representation. To insert a new item into its proper place in the list, we must shift array elements down to make room for the new item (see Figure 18-1). Similarly, deleting an item from the list requires that we shift up all the array elements following the one to be deleted. |
|
|
|
|
|
|
|
|
Figure18-1
Inserting into a Sequential Representation of a List |
|
|
|
|
|
