One of the drawbacks of all previous data structures in this chapter is that, because they store their data in one or two arrays and they avoid resizing these arrays too often, the arrays frequently are not very full. For example, immediately after a operation on an ArrayStack, the backing array is only half full. Even worse, there are times when only one third of contains data.
In this section, we discuss the RootishArrayStack data structure, that addresses the problem of wasted space. The RootishArrayStack stores elements using arrays. In these arrays, at most array locations are unused at any time. All remaining array locations are used to store data. Therefore, these data structures waste at most space when storing elements.
A RootishArrayStack stores its elements in a list of arrays called blocks that are numbered . See Figure 2.5. Block contains elements. Therefore, all blocks contain a total of
As we might expect, the elements of the list are laid out in order within the blocks. The list element with index 0 is stored in block 0, elements with list indices 1 and 2 are stored in block 1, elements with list indices 3, 4, and 5 are stored in block 2, and so on. The main problem we have to address is that of determining, given an index , which block contains as well as the index corresponding to within that block.
Determining the index of within its block turns out to be easy. If index is in block , then the number of elements in blocks is . Therefore, is stored at location
With this out of the way, the and methods are straightforward. We first compute the appropriate block and the appropriate index within the block and then perform the appropriate operation:
If we use any of the data structures in this chapter for representing the list, then and will each run in constant time.
The method will, by now, look familiar. We first check to see if our data structure is full, by checking if the number of blocks, , is such that . If so, we call to add another block. With this done, we shift elements with indices to the right by one position to make room for the new element with index :
The method does what we expect. It adds a new block:
Ignoring the cost of the operation, the cost of an operation is dominated by the cost of shifting and is therefore , just like an ArrayStack.
The operation is similar to . It shifts the elements with indices left by one position and then, if there is more than one empty block, it calls the method to remove all but one of the unused blocks:
Once again, ignoring the cost of the operation, the cost of a operation is dominated by the cost of shifting and is therefore .
The above analysis of and does not account for the cost of and . Note that, unlike the operation, and do not copy any data. They only allocate or free an array of size . In some environments, this takes only constant time, while in others, it may require time proportional to .
We note that, immediately after a call to or , the situation is clear. The final block is completely empty, and all other blocks are completely full. Another call to or will not happen until at least elements have been added or removed. Therefore, even if and take time, this cost can be amortized over at least or operations, so that the amortized cost of and is per operation.
Next, we analyze the amount of extra space used by a RootishArrayStack. In particular, we want to count any space used by a RootishArrayStack that is not an array element currently used to hold a list element. We call all such space wasted space.
The operation ensures that a RootishArrayStack never has more than two blocks that are not completely full. The number of blocks, , used by a RootishArrayStack that stores elements therefore satisfies
Next, we argue that this space usage is optimal for any data structure that starts out empty and can support the addition of one item at a time. More precisely, we will show that, at some point during the addition of items, the data structure is wasting an amount of space at least in (though it may be only wasted for a moment).
Suppose we start with an empty data structure and we add items one at a time. At the end of this process, all items are stored in the structure and distributed among a collection of memory blocks. If , then the data structure must be using pointers (or references) to keep track of these blocks, and these pointers are wasted space. On the other hand, if then, by the pigeonhole principle, some block must have a size of at least . Consider the moment at which this block was first allocated. Immediately after it was allocated, this block was empty, and was therefore wasting space. Therefore, at some point in time during the insertion of elements, the data structure was wasting space.
The following theorem summarizes our discussion of the RootishArrayStack data structure:
The space (measured in words)2.2 used by a RootishArrayStack that stores elements is .