Array Data Structure
An array is one of the basic data structures. It is one of the most used and a basis for the implementation of more complicated data structures.
An array is a collection of fixed size that contains elements of specified type.
When analyzing data structures we are interested in how efficient they are when executing some of the most common operations. Like: accessing an element, searching for an element, inserting an element, deleting an element.
But lets first see how can we initialize an array.
Array Initialization
When we initialize an array, we have to specify the size of an array and the type of elements which it can contain. For an example:
Here we initialized an array that can hold 5 elements the most and only elements of type int.
What happened on the low level when we initialized this array is:
1) we made array reference and made it point to some free memory location
2) we reserved 5 memory locations starting with location array points to
If we wanted to initialize an array with some data in it we could do it like this:
and this would be the result:
Accessing an Array Element
When we want to access an element in an array we must know its memory location.
In our example, array points to the memory location of the first element. Using this information, we can calculate every other element’s memory location.
We first calculate the distance between the element we want to access to the first element in the array. We call this distance index.
For example, if we want to access 3rd element in the array:
We see that it’s index is 2. This is the value that we need to provide if we want to access 3'rd element in Java.
3'rd element’s memory location would automatically be calculated by adding: location array points to + index:
Example code of accessing an array element in Java by providing an index value:
Now, this is a very interesting mechanism. To access any element in an array, no matter the size of an array, all we need to know is element’s index.
If you read my post about Big O notation or are in general familiar with it, you know that this results in O(1) time complexity. And this is great. There is no better access time than this.
Finding an element in Array
When we want to find a specific element in an array, we have to check each element in an array, one by one. Let’s say we want to find an element D in the example array:
In Java we can do this with for loop:
This operation has O(n) complexity because in the worst case we have to check every element in the array if its the one we search for.
Inserting an element into an Array
Let’s say we want to insert an element into an array. For example, an element B into this example array at index position 1:
To do this, we first have to move all elements starting from the index position 1 for one spot to the right:
Now we can place B to the index location 1 :
This is the example code in Java that I used to solve this task:
If we did a Big O analysis of this algorithm we would get O(n) complexity. So we conclude that inserting an element into an array has O(n) time complexity.
Deleting an element in an Array
Very similar to the insert into an Array operation.
Let’s take an array from the previous example but now we want to delete an element at the index location 2:
All we have to do is to move all elements after index location 2 one position to the left:
And then, we set the last element in the array to \u0000 which is the null character in Java:
Here is my example code for element deletion in an array:
This code also has Big O(n) time complexity, because in the worst case we have to move all n elements to the left.
Conclusion
Array is one of the cornerstones of every programing language. You might not use it directly that often, but many data structures use it in their implementations.
Hope you find this post informative and stay tuned for more.
You can check out my other articles in my: Java Vault publication
Have a nice day everybody! ☀️🍹
