What is an array?
An array is a contiguous data structure of a predefined size where elements are adjacent to each other. Each element on this data structure is a variable we store values to. The entire array is ultimately a collection of these variables.
Arrays can be one-dimensional, called vectors, as well as two-dimensional, called matrices.
Array memory structure
To understand the memory structure of an array, let’s see an example of how storing an array of 5 integers in memory works. An integer is 32 bits in size, which translates into 4 bytes (8 bits = 1 Byte).
Now given each memory address is 1 byte, we will need to reserve 4 bytes of memory for each integer value on our array. The operating system (‘OS’) usually handles and assigns those addresses based on memory availability.
Now let’s assume our array’s first element starts at the memory address 2040. Then the next element will be at the address 2044, the third at 2048, fourth at 2052 and the last at address 2056. That results in our array allocating memory from address 2040-2059 and the next available memory address starting at 2060.
Arrays are one of the oldest and most commonly used data structure that efficiently handles the computer memory addressing system. We use arrays as a collection of different types of variables.
We also use arrays as the base for creating other data structures such as lists and strings. For example, a String in Java language is implemented of an array of chars.
Arrays are a static data structure which means once an array is created we cannot change its size. You may manipulate the values of each array element, but in order to change the type and size of the array, you need to create a new one.
Being a static data structure, arrays are slow at inserting and deleting elements. To delete or insert elements in a static array we have to shift position of elements to achieve that. This makes the process slower.
Also, it is very important to know that indexing of arrays starts at position “0”. Meaning that the first element in an array is located at the array index position “0” and the next one at the index position “1”.
Find some code below that shows few of the simple ways we create and manipulate arrays.
Advanced usage of arrays
Appart from the basic but important usages of arrays, there are also some more advanced techniques which are mostly used within algorithms to solve more complex problems.
For example, I’ll go through a method I wrote that checks if two given strings are an anagram of each other.
In this method, I am using an integer array of 26 slots, where each slot represents each letter of the English alphabet (a-z). I will be considering only lower-case letters for this example but can be easily modified to include the upper-case letters as well. Let’s have a look!
Anagram Algorithm with Simple Array
This algorithm loops over each letter of two given strings and subtract from the decimal ASCII value of each letter the value of the letter “a”. The result of this calculation is in the range of 0-25 (a-z).
For example, the decimal ASCII value of letter “a” is 97 and for the letter “b” is 98. If a String contains the letter “a”, the calculation is 97 – 97 = 0. If a String contains the letter “b”, the calculation is 98 – 97 = 1. This result corresponds to the index of our integers array, representing the letter we found in the String.
When we have the array index for each letter of the first String, we use them to increment the value of the corresponding array elements.
After we complete this procedure with the first String, we do the same with the second String. Though, instead of incrementing the array elements, we are now going to decrement them.
When we complete those two loops, we’ll go through one more final loop to check our letters array and its element values.
If we find any element to have a value other than zero, we immediately know that our Strings are not anagrams. That particular letter was either only incremented or decremented. This means it was only found in one of the Strings.
Check this approach of solving this problem with a simple array in some Java code below.
Bonus: Reverse String method with an Array
As a bonus, you may find one more method that shows how creatively you could be using arrays. On the below code snippet I am using a simple array to swap the characters of a given string in order to reverse the entire string.
Arrays are easy to learn and use. At the same time are a very important data structure you need to master.
Arrays are used almost everywhere in programming. From the simple usage of storing multiple variables to more complex algorithms.
I hope this article helps you realize the importance of this data structure; motivates you to further study arrays; and discover new and innovative ways to use them.Share this post