Previous Section
 < Free Open Study > 
Next Section


6.5 A Linked List as an Array of Records

We have used both statically allocated arrays and dynamically allocated arrays for our array-based implementations. We have used dynamic memory allocation to obtain the necessary memory for the nodes making up the linked structures developed in this and previous chapters.

The choice between array-based and linked list representations is not the same as the choice between static and dynamic storage allocation. They are separate issues. We typically store arrays in variables that have been declared statically, as illustrated in Figure 6.15(a), but an array-based implementation does not necessarily use static storage. The entire array could exist in a dynamically allocated area of memory; that is, we could get space for the whole structure at once using the new operator, as illustrated in Figure 6.15(b).

We tend to think of linked structures as residing in dynamically allocated storage, as depicted in Figure 6.16(a), but this is not a requirement. A linked list could be implemented in an array; the elements might be stored in the array in any order and "linked" by their indexes (see Figure 6.16b). In the following sections, we develop the array-based linked-list implementation.

Click To expand
Figure 6.15: Array-based lists in static and dynamic storage
Click To expand
Figure 6.16: Linked lists in static and dynamic storage

Why Use an Array?

Dynamic allocation of list nodes offers many advantages, so why would we even discuss using an array-of-records implementation instead? We have noted that dynamic allocation is merely one advantage gained by choosing a linked implementation; another advantage relates to the efficiency of the insertion and deletion algorithms. Most of the algorithms that we have discussed for operations on a linked structure can be used for either an array-based or a dynamic implementation. The main difference involves the requirement that we manage our own free space in an array-based implementation. Managing the free space ourselves gives us greater flexibility.

Another reason to use an array of records is the fact that a number of programming languages do not support dynamic allocation or pointer types. You can still use linked structures when programming in one of these languages, but you would have to represent pointer values as array indexes.

Using pointer variables presents a problem when we need to save the information in a data structure between runs of a program. Suppose we want to write all the nodes in a list to a file and then use this file as input the next time we run the program. If the links are pointer values-containing memory addresses-they are meaningless on the next run of the program because the program may be placed somewhere else in memory the next time. We must save the user data part of each node in the file and then rebuild the linked structure the next time we run the program. An array index, however, remains valid on the next run of the program. We can store the entire array, including the next data member (indexes), and then read it back in the next time we run the program.

Most importantly, sometimes dynamic allocation isn't possible or feasible, or dynamic allocation of each node, one at a time, is too costly in terms of time-especially in system software such as operating system code.

How Is an Array Used?

Let's return to our discussion of how we can implement a linked list in an array. As noted earlier, the next member of each node tells us the array index of the succeeding node. The beginning of the list is accessed through a "pointer" that contains the array index of the first element in the list. Figure 6.17 shows how a sorted list containing the elements David, Joshua, Leah, Miriam, and Robert might be stored in an array of records called nodes. Do you see how the order of the elements in the list is explicitly indicated by the chain of next indexes?

Click To expand
Figure 6.17: A sorted list stored in an array of records

What goes in the next member of the last list element? Its "null" value must be an invalid address for a real list element. Because the nodes array indexes begin at 0, the value -1 is not a valid index into the array; that is, no nodes [-1] exists. Therefore -1 makes an ideal value to use as a "null" address. Let's use the constant identifier NUL rather than NULL to keep the distinction clear. We could use the literal value -1 in our programs,

while (location != -1)

but it is better programming style to declare a named constant. In fact, we can define NUL to be - 1.

const int NUL = -1;

When using an array-of-records implementation to represent a linked list, the programmer must write routines to manage the free space available for new list elements. Where is this free space? Look again at Figure 6.17. All of the array elements that do not contain values in the list constitute free space. Instead of the built-in allocator new, which allocates memory dynamically, we must write our own function to allocate nodes from the free space. We call this function GetNode.

When elements are deleted from the list, we need to free the node space. We can't use delete, because it only works for dynamically allocated space. We write our own function, FreeNode, to return a node to the pool of free space.

This collection of unused array elements can be linked together into a second list, a linked list of free nodes. Figure 6.18 shows the array nodes with both the list of values and the list of free space linked through their next members. Here list is the external pointer to a list that begins at index 0 (containing the value David). Following the links in the next member, we see that the list continues with the array slots at index 4 (Joshua), 7 (Leah), 2 (Miriam), and 6 (Robert), in that order. The free list begins at free, at index 1. Following the links in the next member, we see that the free list also includes the array slots at indexes 5, 3, 8, and 9. Two NUL values appear in the next column because the nodes array contains two linked lists.

Click To expand
Figure 6.18: An array with a linked list of values and free space

Two approaches to using an array-of-records implementation for linked structures are possible. The first is to simulate dynamic memory. One array stores many different linked lists, just as the nodes on the free store can be dynamically allocated for different lists. In this approach, the external pointers to the lists are not part of the storage structure, but the external pointer to the list of free nodes is part of the structure. Figure 6.19 shows an array that contains two different lists. The list indicated by list1 contains the values John, Nell, Susan, and Susanne, and the list indicated by list2 contains the values Mark, Naomi, and Robert. The remaining three array slots in Figure 6.19 are linked together in the free list.

Click To expand
Figure 6.19: An array with three lists (including the free list)

The second approach is to have one array of records for each list. In this approach, the external pointer is part of the storage structure itself (see Figure 6.20). The list constructor takes a parameter that specifies the maximum number of items on the list. This parameter is used to dynamically allocate an array of the appropriate size. Note that the array itself resides in dynamic storage, but the linked structure uses array indexes as "pointers." If the list will be saved between runs of the program, the contents of the array are saved, and the indexes (links) remain valid.

Click To expand
Figure 6.20: List and linked structure are together

Let's implement this second approach. In implementing our class functions, we need to keep in mind that two distinct processes go on within the array of records: bookkeeping related to the space (such as initializing the array of records, getting a new node, and freeing a node) and the operations on the list that contains the user's data. The bookkeeping operations are transparent to the user. The prototypes of the member functions stay the same, including both a parameterized and a default constructor. The private data members, however, change. We need to include the array of records. Let's call this array nodes and place it in dynamic storage. MemoryType, then, is a struct containing two items: an integer "pointer" to the first free node and a true pointer to the dynamically allocated array of nodes.

To simplify the following discussion and code, we assume that the items on the list are integers rather than using a template class.

struct MemoryType;

class ListType
{
public:
  // Member function prototypes go here.
private:
  int listData:
  int currentPos;
  int length;
  int maxItems;
  MemoryType storage;
};

The functions that do the bookkeeping are auxiliary ("helper") functions, not class member functions. Member functions are those functions that the user invokes; auxiliary functions are those functions that help to implement the member functions. Let's look first at these bookkeeping functions. The nodes are all free initially, so they must be chained together and the index of the first node stored into free. GetNode must return the index of the next free node and update free. FreeNode must take the node index received as a parameter and insert it into the list of free nodes. Because the first item in the list is directly accessible, we have GetNode return the first free item and FreeNode insert the node being returned at the beginning of the free list. (Yes, we keep the free list as a stack-not because we need the LIFO property but because the code is the simplest for what we need.)

The following code defines MemoryType and implements these auxiliary functions:

// Prototypes of auxiliary functions.
void GetNode(int& nodeIndex, MemoryType& storage);
// Returns the index of a free node in nodeIndex.
void FreeNode(int nodeIndex, MemoryType& storage);
// Returns nodeIndex to storage.
void InitializeMemory(int maxItems, MemoryType&);
// Initializes all memory to the free list.

// Define end-of-list symbol.
const int NUL = -1 ;

struct NodeType
{
  int info;
  int next;
};

struct MemoryType
{
  int free ;
  NodeType* nodes;
};

void InitializeMemory(int maxItems, MemoryType& storage)
{
  for (int index = 1; index < maxItems; index++)
    storage.nodes[index-1].next = index;
  storage.nodes[maxItems-1] = NUL;
  storage.free = 0;
}

void GetNode(int& nodeIndex, MemoryType& storage)
{
  nodeIndex = storage.free;
  storage.free = storage.nodes[free].next;
}

void FreeNode(int nodeIndex, MemoryType& storage)
{
  storage.nodes[nodeIndex].next = storage.free;
  storage.free = nodeIndex;
}

The class constructors for the class ListType must allocate the storage for the array of records and call InitializeMemory. For the default constructor, we arbitrarily choose an array size of 500.

ListType::ListType(int max)
{
  length - 0:
  maxItems = max;
  storage.nodes = new NodeType[max];
  InitializeMemory(maxItems, storage);
  listData = NUL;
}
ListType::ListType()
{
  length = 0;
  maxItems = 500;
  storage.nodes = new NodeType[500];
  InitializeMemory(500, storage);
  listData = NUL;
}

ListType::~ListType()
}
  delete [] storage.nodes;
}

Let's look at our design notation, the dynamic pointer-based equivalent, and the array-of-records equivalent. We also need to examine the bookkeeping equivalent of the dynamic pointer-based operations and the array-of-records version. Once we understand all these relationships, coding the member functions of ListType is quite straightforward. In fact, it is so straightforward, we leave the code as a programming assignment.

Design Notation/Algorithm

Dynamic Pointers

Array-of-Records "Pointers"

Node(location)

*location

storage. nodes[location]

Info(location)

location->info

storage.nodes[location].info

Next(location)

location->next

storage.nodes[location].next

Set location to Next(location)

location = location->next

location = storage.nodes[location].next

Set Info(location) to value

location->info = value

storage.nodes[location].info = value

AlIocate a node

nodePtr = new NodeType

GetNode(nodePtr)

Deallocate a node

delete nodePtr

FreeNode(nodePtr)



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)