Exotic Data StructuresOr maybe not so exotic... 1. Dynamic arrays 2. Linked lists 3. Unordered maps 4. Ordered maps 5. Ordered maps (over finite keys) The last one is starting to sound exotic though. 1. Compact dynamic array (compactarrays) Based on the deque variant of [1]. Bounds:
This is simply a O(sqrtN) array of O(sqrtN) subarrays. Two lists of arrays are maintained, small and big (twice bigger) Also, pointers to head/tail indexes, and the big/small separation are maintained. Conceptually, the virtual array is the concatenation of all small subarrays followed by the big subarrays, and indexed between head/tail. All operations are straightforward. In order to maintain the global invariants, small subarrays are sometimes merged into big arrays, or big arrays are split into small arrays (this happens at the boundary between the two lists). when one of both lists is empty, we swap the lists (big arrays become small and viceversa) Variant: Compact integer arrays Has the same time complexity bounds, but takes NlgM +o(N) bits in the worst case, where M is the biggest integer stored in the array. This is implemented by growing subarrays dynamically when an update overflows. it makes updates O(sqrtN) worst case (amortized if O(N) numbers take O(lgM) bits). 2. Succinct lists (succinctlists) [1] A. Brodnik, S. Carlsson, E. D. Demaine, J. I. Munro, and R. Sedgewick. Resizable arrays in optimal time and space. Technical Report CS9909, U. Waterloo, 1999. This revision created on Sun, 7 Dec 2008 16:34:51 by prunedtree 

All content is © 20082010 by its respective authors. By adding content to this wiki, you agree to release it under the BSD license. 