2. Array-Based Lists

In this chapter, we will study implementations of the List and Queue interfaces where the underlying data is stored in an array, called the backing array. The following table summarizes the running times of operations for the data structures presented in this chapter:


  $ \ensuremath{\mathrm{get}(\ensuremath{\mathit{i}})}$/ $ \ensuremath{\mathrm{set}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ $ \ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$/ $ \ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$
ArrayStack $ O(1)$ $ O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}-\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}})$
ArrayDeque $ O(1)$ $ O(\min\{\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}},\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}-\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}\})$
DualArrayDeque $ O(1)$ $ O(\min\{\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}},\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}-\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}\})$
RootishArrayStack $ O(1)$ $ O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}-\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}})$

Data structures that work by storing data in a single array have many advantages and limitations in common: The third point is important. The running times cited in the table above do not include the cost associated with growing and shrinking the backing array. We will see that, if carefully managed, the cost of growing and shrinking the backing array does not add much to the cost of an average operation. More precisely, if we start with an empty data structure, and perform any sequence of $ m$ $ \ensuremath{\mathrm{add}(\ensuremath{\mathit{i}},\ensuremath{\mathit{x}})}$ or $ \ensuremath{\mathrm{remove}(\ensuremath{\mathit{i}})}$ operations, then the total cost of growing and shrinking the backing array, over the entire sequence of $ m$ operations is $ O(m)$. Although some individual operations are more expensive, the amortized cost, when amortized over all $ m$ operations, is only $ O(1)$ per operation.



Subsections
opendatastructures.org