Arrays

Arrays are a built-in type in many programming languages: Java virtual machine, C/C++, and so on. Here arrays are defined to mean fixed-sized sequences of elements of the same type, allocated in a continuous block of memory. In many programming languages, “arrays’’ can mean more sophisticated data structures, see the discussion at the end of this section. In Java and Scala, elements in arrays are either primitive types or references to objects residing in their own memory locations. Some other languages, such as C and C++, allow array elements to be structured objects.

Example

The figure below shown an object diagram for an array of integers.

_images/array-int-1.png

For an array of integer pair objects, the object diagram looks as following for Java and Scala. The third entry in the array on the right contains a null-reference not pointing to any object.

_images/arrays-1.png

Properties:

  • ​ Constant time indexed access to elements (read and write).

  • ​ Searching for an element takes \(\Theta(n)\) time in the worst case (unless the array is sorted for binary search etc).

  • ​ Elements cannot be appended at the beginning or end. If this is desired, a new array with bigger size must be allocated and the array contents copied there together with the new element, a \(\Theta(n)\) time operation. To see how this can be done so that the insertions take constant time on avegare, see Section Resizable arrays.

In some higher-level interpreted languages, one has to use special libraries to use the “low-level” arrays discussed above. For instance, in Python neither list or array are low-level arrays but resizable array data types. To access low-level arrays, one can use the ctypes library. Similarly, in JavaScript Arrays are not low-level arrays but allow resizing (appending at the end etc) and the data is not necessarily stored in a continuous block of memory. To access low-level arrays, one can use TypedArrays.