DataStructures Series #4 – The Array ADT

Originally posted on my medium page:

The Array Abstract Data Type

The array is a basic abstract data type that holds an ordered collection of items accessible by an integer index. These items can be anything from primitives such as integers to more complex types like instances of classes.

Array Operations:

  • Store using an integer index
  • Retrieve using an integer index

The indices (keys) are used to store/retrieve values via a contiguous block of memory as shown in the image below (this is easily computed knowing the base address of the array when initiated), the elements at these memory addresses may be actual values or references in memory that holds the actual value (this approach is usually used when the values are kept in non-contiguous block of memory). The implementation detail is left to the programmer to decide.

Internal structure of an array

Java Implementation of the Array Abstract Data type

  • Creating an array — Arrays require a size and type when they are created in Java. Below is an example of how you would declare an array of integers with size 10.
>>> int[] myArray = new int[10];
>>> System.out.print(Arrays.toString(myArray));
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  • Storing a value
>>> int[] myArray = new int[5];
>>> myArray[1] = 100;
>>> myArray[3] = 200;
>>> System.out.print(Arrays.toString(myArray));
[0, 100, 0, 200, 0]
  • Getting a value
>>> int[] myArray = new int[5];
>>> myArray[1] = 100;
>>> System.out.print(myArray[1]);

Benefits of Using an Array Data-structure:

  • Store element in constant time by specifying an index
  • Get element in constant time if the index is known