sandbox/ods/notes/chapter2.txt

# Chapter 2 (Array-based lists)

These data structures have common advantages and limitations:

* constant-time access

* resizing the array adds potentially non-trivial complexity, both in time and
  storage, as a new array generally must be created and the old array copied
  over.

* arrays aren't dynamic, which means inserting or deleting in the middle of an
  array requires shifting all the following elements.

With some careful management, the additional *amortised* complexity added by
resizing isn't too bad.

## Array stack

* Uses backing array *a*.
* Typically, the array will be larger than necessary, so an element *n* is
  used to track the actual number of elements stored in the stack.
* Add and remove requires shifting all the elements after i (O(n - i)
  complexity), ignoring potential calls to resize
* Resizing is triggered when we run out of room in an add or when a remove
  brings us to the point where the array is more than 3n elements
* Resizing creates a new array of size 2n and copies all the elements over;
  this then has complexity O(n).
* The analysis of add and remove didn't consider cost of resize.
* An amortised analysis is done instead that considers the cost of all calls
  to add and remove, given a sequence of *m* calls to either.
* **Lemma**: if an empty ArrayStack is created and any sequence of *m* >= 1
  calls to add and remove are performed, the total time spent in calls to 
  resize is O(m).
* Optimisations (FastArrayStack): using memcpy or std::copy to copy blocks of
  data, not one element at a time.

## ArrayQueue

* ArrayStack is a bad implementation for a FIFO queue; either add or remove
  must work from the head with index = 0, which means all calls to that
  method will result in running time of O(n).
* We could do this with an infinite array, using an index into the head (*j*)
  and the size of the backing array. We don't have an infinite array, so we'll
  have to use modular arithmetic with a finite stack.
* **Theorem**: Ignoring the cost of calls to resize, an ArrayQueue supports the
  operations add and remove in O(1) per operation. Beginning with an empty
  ArrayQueue, any sequence of m add/remove operations will result in a total
  of O(m) time resizing.

## ArrayDeque

* Implementation of adding and removing from both ends using the same circular
  buffer technique.
* add/remove check whether their index is before or after the halfway point and
  shift from there as a performance benefit.
* **Theorem**: Ignoring the cost of calls to resize, an ArrayDeque supports
  set/get in time O(1) time per operation, and add/remove in O(1+min(i, n-1))
  time per operation. Beginning with an empty ArrayDeque, performing any 
  sequence of m operations results in a total of O(m) time resizing.

## Dual Array Deque 

* Same performance bounds as ArrayDeque using a pair of ArrayStacks.
* While not better, it's instructive as an example of building a more complex
  data structure from simpler ones.
* List is represented as a pair of ArrayStacks; these are fast when a
  modification occurs at the end. The DAD uses two ArrayStacks called
  front and back.
  * front: list elements that are 0...front.size()-1
  * back: same but reverse order