Figure 3.2 Graphic Representation of the List STOCKS
The stock portfolio example is represented in a list in Figure 3.2. The variable labeled head contains a pointer to the first record in the list. Each record is composed of two fields: 1) an information field, which may itself be made up of subfields such as name, shares, value, datebought (or accountnumber, balance, address); and 2) a link field, which contains the pointer to the next record. The x in the link field of the last record denotes the null pointer and indicates that this is the last record on the list. The list with no records is called the null list, and is denoted by a head containing the null pointer.
It does no good to know that a phone number (say, 642-3715) contains the digits 1, 2, 3, 4, 5, 6, and 7, unless the order 6, 4, 2, 3, 7, 1, 5 is retained as well. Notice that the list data structure, besides being a new way to store information, allows the information to be remembered in a specific order?/FONT>the order in which the records appear on the list. Arrays provide this ability as well. The order in which records (or the pointers to them) are stored does this, but the operations that make lists interesting and powerful are insertion and deletion.
In effect, a list works as if the pointers from a pointer array were incorporated into the records to which they point. This is the crucial advantage of lists compared to arrays. The price of the added convenience is the loss of the capability to select an arbitrary record. Instead of access to the list records being through the pointer array, the list records must now be accessed via the pointer to the first list record (in head or name). Knowing only the head of a list means that only the first record is immediately visible. To access another list record, the chain of pointers linking list records must be followed until the desired record is encountered.
Consider the simple list l in Figure 3.3(a). Two situations are depicted in Figure 3.3(b,c): (b) is the case when the list head l is known, and (c) the case when a pointer, ptr, to a list record is known. In each case only the record to which the known pointer points is visible.
When only one pointer points to a record, if that pointer value is changed, then the record cannot be accessed. It is as if the programmer had stored something somewhere but had no hope of remembering where. If that pointer happens to be in the head of a list, then access to the list is lost. Suppose the programmer must start with the situation depicted in Figure 3.3(a) and must create two lists. One, l, is to consist of all records of the original list, from the record pointed to by ptr to the last record. Another, newl, is to consist of the original list records, from the first to the record prior to that pointed to by ptr. Simply copying the value of ptr into l creates the correct modified version of l. However, newl cannot be created since the pointer to the original first record that had been stored in l has been lost. Such a predicament must be avoided.
Keeping track of pointers in processing lists is extremely important. One reason is that more than one pointer can point to a record. The only way to see if two pointers point to the same record is to see if their pointer values are equal.
3.2.1 Insertion and Deletion of Records in Lists
Figure 3.3 Simple Lists