A multiple-array representation of objects

We can represent a collection of objects that have the same fields by using an array for each field. As an example, Figure 10.5 shows how we can implement the linked list of Figure 10.3(a) with three arrays. The array key holds the values of the keys currently in the dynamic set, and the pointers are stored in the arrays next and prev. For a given array index x, key[x], next[x], and prev[x] represent an object in the linked list. Under this interpretation, a pointer x is simply a common index into the key, next, and prev arrays.

Figure 10.5: The linked list of Figure 10.3(a) represented by the arrays key, next, and prev. Each vertical slice of the arrays represents a single object. Stored pointers correspond to the array indices shown at the top; the arrows show how to interpret them. Lightly shaded object positions contain list elements. The variable L keeps the index of the Head.

In Figure 10.3(a), the object with key 4 follows the object with key 16 in the linked list. In Figure 10.5, key 4 appears in key[2], and key 16 appears in key[5], so we have next[5] = 2 and prev[2] = 5. Although the constant NIL appears in the next field of the tail and the prev field of the head, we usually use an integer (such as 0 or -1) that cannot possibly represent an actual index into the arrays. A variable L holds the index of the head of the list.

In our pseudocode, we have been using square brackets to denote both the indexing of an array and the selection of a field (attribute) of an object. Either way, the meanings of key[x], next[x], and prev[x] are consistent with implementation practice.

A single-array representation of objects

The words in a computer memory are typically addressed by integers from 0 to M - 1, where M is a suitably large integer. In many programming languages, an object occupies a contiguous set of locations in the computer memory. A pointer is simply the address of the first memory location of the object, and other memory locations within the object can be indexed by adding an offset to the pointer.

We can use the same strategy for implementing objects in programming environments that do not provide explicit pointer data types. For example, Figure 10.6 shows how a single array A can be used to store the linked list from Figures 10.3(a) and 10.5. An object occupies a contiguous subarray A[j ‥ k]. Each field of the object corresponds to an offset in the range from 0 to k - j, and a pointer to the object is the index j. In Figure 10.6, the offsets corresponding to key, next, and prev are 0, 1, and 2, respectively. To read the value of prev[i], given a pointer i, we add the value i of the pointer to the offset 2, thus reading A[i + 2].

Figure 10.6: The linked list of Figures 10.3(a) and 10.5 represented in a single array A. Each list element is an object that occupies a contiguous subarray of length 3 within the array. The three fields key, next, and prev correspond to the offsets 0, 1, and 2, respectively. A pointer to an object is an index of the first element of the object. Objects containing list elements are lightly shaded, and arrows show the list ordering.

The single-array representation is flexible in that it permits objects of different lengths to be stored in the same array. The problem of managing such a heterogeneous collection of objects is more difficult than the problem of managing a homogeneous collection, where all objects have the same fields. Since most of the data structures we shall consider are composed of homogeneous elements, it will be sufficient for our purposes to use the multiple-array representation of objects.

Allocating and freeing objects

To insert a key into a dynamic set represented by a doubly linked list, we must allocate a pointer to a currently unused object in the linked-list representation. Thus, it is useful to manage the storage of objects not currently used in the linked-list representation so that one can be allocated. In some systems, a garbage collector is responsible for determining which objects are unused. Many applications, however, are simple enough that they can bear responsibility for returning an unused object to a storage manager. We shall now explore the problem of allocating and freeing (or deallocating) homogeneous objects using the example of a doubly linked list represented by multiple arrays.

Suppose that the arrays in the multiple-array representation have length m and that at some moment the dynamic set contains n ≤ m elements. Then n objects represent elements currently in the dynamic set, and the remaining m-n objects are free; the free objects can be used to represent elements inserted into the dynamic set in the future.

We keep the free objects in a singly linked list, which we call the free list. The free list uses only the next array, which stores the next pointers within the list. The head of the free list is held in the global variable free. When the dynamic set represented by linked list L is nonempty, the free list may be intertwined with list L, as shown in Figure 10.7. Note that each object in the representation is either in list L or in the free list, but not in both.

Figure 10.7: The effect of the ALLOCATE-OBJECT and FREE-OBJECT procedures. (a) The list of Figure 10.5 (lightly shaded) and a free list (heavily shaded). Arrows show the free-list structure. (b) The result of calling ALLOCATE-OBJECT() (which returns index 4), setting key[4] to 25, and calling LIST-INSERT(L, 4). The new free-list head is object 8, which had been next[4] on the free list. (c) After executing LIST-DELETE(L, 5), we call FREE-OBJECT(5). Object 5 becomes the new free-list head, with object 8 following it on the free list.

The free list is a stack: the next object allocated is the last one freed. We can use a list implementation of the stack operations PUSH and POP to implement the procedures for allocating and freeing objects, respectively. We assume that the global variable free used in the following procedures points to the first element of the free list.

ALLOCATE-OBJECT()
1  if free = NIL
2      then error "out of space"
3      else x ← free
4           free ← next[x]
5           return x

FREE-OBJECT(x)
1  next[x] ← free
2  free ← x

The free list initially contains all n unallocated objects. When the free list has been exhausted, the ALLOCATE-OBJECT procedure signals an error. It is common to use a single free list to service several linked lists. Figure 10.8 shows two linked lists and a free list intertwined through key, next, and prev arrays.

Figure 10.8: Two linked lists, L₁ (lightly shaded) and L₂ (heavily shaded), and a free list (darkened) intertwined.

The two procedures run in O(1) time, which makes them quite practical. They can be modified to work for any omogeneous collection of objects by letting any one of the fields in the object act like a next field in the free list.

Exercises 10.3-1

Draw a picture of the sequence 〈13, 4, 8, 19, 5, 11〉 stored as a doubly linked list using the multiple-array representation. Do the same for the single-array representation.

Exercises 10.3-2

Write the procedures ALLOCATE-OBJECT and FREE-OBJECT for a homogeneous collection of objects implemented by the single-array representation.

Exercises 10.3-3

Why don't we need to set or reset the prev fields of objects in the implementation of the ALLOCATE-OBJECT and FREE-OBJECT procedures?

Exercises 10.3-4

It is often desirable to keep all elements of a doubly linked list compact in storage, using, for example, the first m index locations in the multiple-array representation. (This is the case in a paged, virtual-memory computing environment.) Explain how the procedures ALLOCATE>-OBJECT and FREE-OBJECT can be implemented so that the representation is compact. Assume that there are no pointers to elements of the linked list outside the list itself. (Hint: Use the array implementation of a stack.)

Exercises 10.3-5

Let L be a doubly linked list of length m stored in arrays key, prev, and next of length n. Suppose that these arrays are managed by ALLOCATE-OBJECT and FREE-OBJECT procedures that keep a doubly linked free list F. Suppose further that of the n items, exactly m are on list L and n-m are on the free list. Write a procedure COMPACTIFY-LIST(L, F) that, given the list L and the free list F, moves the items in L so that they occupy array positions 1, 2,..., m and adjusts the free list F so that it remains correct, occupying array positions m + 1, m + 2,..., n. The running time of your procedure should be Θ(m), and it should use only a constant amount of extra space. Give a careful argument for the correctness of your procedure.