2.1 ADT

What are the most abstract operations for an array? let us first review, very quickly, how arrays are typically used in a program.

int nums[256];

The above line is the definition of an array called nums. It is an array of 256 integers.

nums[2] = 5;

The above line is the indexing of the array. We are accessing an element in the array. To be more specific, we are updating the value of the element.

s = sizeof(nums[2]);

The above line gets the number of bytes allocated to nums.

At the minimum, an array ADT has the following three user interface operation:

• allocation (creation)
• indexing
• return the size of it

Note that the C/C++ built-in implementation of array does not permit an array to be resized once it is created. There is also no checking of ``index out of bound'' errors. On the other hand, an array (a vector in mathematics) inherently has no size limit.

To make an array ADT as abstract as possible, without implementation limitations, we define the following interface:

• Creation/Initialization: this operation needs to be used once, when an array is first created.
• Deletion: this operation needs to be used once, when an array is not needed anymore.
• Indexing: this operation retrieves an element in an array. It returns the storage of an element, not the value.
  • An index should be non-negative.
  • There is no inherent limit to the index.
• Resize: this operation manually resizes an array to a particular number of elements. An array may shrink or grow.
• Number of elements: this operation returns the number of elements (that are in use) in an array.