|
|
|
|
|
|
|
Figure 18-5
Implementation Hierarchy for a List ADT |
|
|
|
|
|
|
|
|
Dynamic Data Representation of a Linked List |
|
|
|
|
|
|
|
|
Representing a list either as an array or as a linked list stored in an array of structs has a disadvantage: the size of the array is fixed and cannot change while the program is executing. Yet when we are working with lists, we often have no idea of the number of components we will have. The usual approach in this situation is to declare an array large enough to hold the maximum amount of data we can logically expect. Because we usually have less data than the maximum, memory space is wasted on the unused array elements. |
|
|
|
|
|
|
|
|
There is another technique for representing a list in which the list components are dynamic variables that are created only as they are needed. We represent the list as a linked list whose nodes are dynamically allocated on the free store, and the link member of each node contains the memory address of the next dynamic node. In this data representation, called a dynamic linked list, the arrows in the diagram of Figure 18-2 really do represent pointers (and the slash in the last node is the null pointer). We access the list with a pointer variable that holds the address of the first node in the list. The pointer variable, named head in Figure 18-2, is called the external pointer or head pointer. Every node after the first node is accessed by using the link member in the node before it. |
|
|
|
|
|
|
|
|
Such a list can expand or contract as the program executes. To insert a new item into the list, we allocate more space on the free store. To delete an item, we deallocate the memory assigned to it. We don't have to know in advance how long the list will be. The only limitation is the amount of available memory space. Data structures built using this technique are called dynamic data structures. |
|
|
|
|
|
