DataStructures Series — 4

N.B. This article would make more sense if you read previous articles in this series.

In case you missed last week on the data-structures series here.

We discussed the major difference between an abstract data type and a data structure, an abstract data type basically specifies how data should be organized and what operations can be performed on it while a data-structure an implementation of an abstract data type type tells us how it organizes the data with other data-structures/data types and how it performs the operations on the data.

This week we would be treating the Array Abstract Data Type. Is an Array really an abstract data type???

I know this sounds confusing…it sounded confusing to me at first, but after some reading I was able to understand it. So, let us remember that an ADT (abstract data type) just specifies how data is organized and what operations can be performed on the data.

With this understanding, we can now discuss how an array should organize data and list the operations that should can be performed on an array.

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 way these indices work is specific to implementation, note that the specification here doesn’t really state if the elements of the array are placed in a continuous block of memory or not, however, what is clear is we can place an element at a specific location using an index and retrieve it at a later time using that same index. The calculation to get the memory address of where the element is left to the implementation.

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]);
100

You can check how arrays work in other programming languages too and for those that are extremely geeky ;), you can make further studies to learn how arrays are actually implemented under the hood for your various programming languages.

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

Next week we would be looking at another interesting abstract data type and discuss briefly on implementation, use-cases and its benefits.

REFERENCES:

• https://brilliant.org/wiki/arrays-adt/