## Growable Arrays

### October 16, 2009

Most programming languages provide a data structure called an array that provides constant-time access and update to its elements, at the cost of fixing the size of the array in advance of its use; Scheme calls that data structure a vector. In their book *The Practice of Programming*, Brian Kernighan and Rob Pike describe arrays that can grow during use, using the C language and its `realloc`

function to double the size of an array when needed. In this exercise we will create a tree-based data structure that provides logarithmic-time access and update to its elements without requiring periodic reallocations, based on the functional arrays in Lawrence Paulson’s book *ML for the Working Programmer*.

A growable array has subscripts from 1 to *n*, where *n* is the current number of elements in the array. The elements are stored in a binary tree. To find the *k*‘th element of the array, start at the root and repeatedly divide *k* by two until it becomes one, moving left if the remainder is zero and right if the remainder is one. For instance, the 12th element of the array is found by moving left, left and right from the root, as shown in the diagram at right. The operations on a growable array are `get`

, which retrieves an element of the array, `put`

, which returns a new array containing the element, and `hirem`

, which shrinks the array by a single element. The `put`

operation can increase the upper bound of the array by one.

Your task is to implement the growable array data structure. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Pages: 1 2

[…] today’s Programming Praxis we’re going to implement a growable array, which is a data structure with […]

My Haskell solution (see http://bonsaicode.wordpress.com/2009/10/16/programming-praxis-growable-arrays/ for a version with comments):

[…] […]

[…] Exercise from: http://programmingpraxis.com/2009/10/16/growable-arrays/ […]

A python solution. joedoliner.com for comments and test code.

Here’s another python solution. This one uses a wrapper class around the root node which keeps track of the current upper bound and uses that for put() and hirem(). I’m sure hirem() could be cleaner, though. :-S