What is an unbounded array?

What is an unbounded array and is there any difference between an unbounded array and a dynamically allocated array? What are the common operations associated with the unbounded array? (like we have pop and push for stack data structure)

Unbounded arrays can be (and usually are) statically allocated.

The primary concern when implementing an unbounded array is to provide dynamic-array like freedom to decide the array size during run-time without the performance penalties of run-time memory allocation.

The following excerpt from an excellent article on unbounded arrays explains it succinctly -

The general implementation strategy is as follows. We maintain an array of a fixed length limit and an internal index size which tracks how many elements are actually in the array. When we add a new element we increment size, when we remove an element we decrement size. The tricky issue is how to proceed when we are already at the limit and want to add another element. At that point, we allocate a new array with a larger limit and copy the elements we already have to the new array.

Notice that during run-time, until size exceeds the initial value of limit there is no dynamic allocation involved with an unbounded array.

Some features (design requirements) of an unbounded array :

• Getting or setting the value at a particular index (constant time)
• Iterating over the elements in order (linear time, good cache performance)
• Inserting or deleting an element at the end of the array (constant amortized time)

Keeping performance in mind, the only additional operations(compared to regular arrays) associated with unbounded arrays are :

• add_to_end()
• delete_from_end()

to allow modifying the size of the unbounded array.

Operations like Insert_in_middle() and Delete_in_middle() are NOT provided keep in mind the primary design principle of an unbounded array i.e. performance.

For more details, checkout the answers to this question.

_{NOTE : Though the question specifically mentions dynamically allocated arrays, probably you might also want to checkout dynamic arrays. A good example of a dynamic-array is the C++ std::vector itself which addresses several of the same design principles as that of an unbounded array.}