Occasionally, a linked structure that does not use references is useful. One such structure uses an array whose items are "linked" by array indexes. Figure 5-35a illustrates an array of nodes that represents the linked list in Figure 5-31. Each node has two data fields, item and next. The next data field is an integer index to the array element that contains the next node in the linked list. Note that the next data field of the last node contains -1. The integer variable head contains the index of the first node in the list.

The array elements that currently arc not a part of the linked list make up a free list of available nodes. These nodes form another linked list, with the integer variable free containing the index of the first free node. To insert an item into the original linked list, you take a free node from the beginning of the free list and insert it into the linked list (Figure 5-35b). When you delete an item from the linked list, you insert the node into tl1e beginning of the free list (Figure 5-35c). In this way, you can avoid shifting data items.

Implement the ADT list by using this array-based linked list.