Introduction To Arrays

Arrays are the most fundamental data structures of all. Arrays are built in most programming languages. In java and many other languages, arrays are static(fixed size).

What are Arrays?

Arrays are the most fundamental data structures of all in computer science. An array organizes items sequentially, one after another in memory.

Arrays are built in most programming languages. In java and many other languages, arrays are static(fixed size).

The items could be integers, Strings, Objects, – anything. The items are stored in contiguous (adjacent to each other) memory locations.

Each position in the array has an index, starting at the 0th index. In Java integers take 4 bytes, so the memory addresses of each adjacent element are added by 4 bytes.

A simple sketch of this is as follows.

A simple array with 5 elements in it, with a memory address, pointed from 100 to 120. So theoretically anything that we store after this array takes the address from 124.

We knew everything on the computer is stored in bits 0 or 1. Another sketch follows and this is how the integers 1,2,3,4,5,6 from above are stored in memory.

Strengths

1. Fast Lookups: Retrieving the element at a given index takes O(1) time, regardless of the length of the array.

2. Fast Appends: Adding a new element at the end of the array takes O(1) time if the array has space.

Weaknesses

1. Fixed Size: You need to specify how many elements you’re going to store in your array ahead of time. (Unless you’re using a fancy dynamic array).

2. Memory unused or waste: Imagine an array with a capacity of 5. We have two elements to store in this array, then we are wasting three cells that are unfilled and waste of memory, which means 3*(4 bytes) = 12 bytes of memory wasted (integer takes 4 bytes).

3. Size Doubling: Let us consider an array with a capacity of 5 elements. But the elements we want to store in this array are more, which means we have to double the size and create a new array, copy the old array elements and add new elements. this time is O(n).

4. Costly Inserts: Inserting an element at the end of the array takes O(1) time. But, inserting an element in the start/middle of the array takes O(n) time. Why? If we want to insert something into an array, first we have to make space by “scooting over” everything starting at the index we’re inserting into as shown in the image. In the worst case, we’re inserting into the 0​^th​ index in the array (prepending), so we have to “scoot over” everything in the array. That’s O(n) time.

Inserting an element at the 2^nd index and moving the rest of the element right shift each once, The resultant array becomes – { A, B, C, D, E }.

We recommend you read Array insertions and shifting algorithms which have a clear explanation with code snippets, sketches to understand why these inserts at the start and middle are expensive.

5. Costly Deletes: Deleting an element at the end of the array takes O(1) time, which is the best case. In computer science, we only care about the worse case scenarios when working on algorithms. But, when we remove an element from the middle or start of the array, we have to fill the gap by scooting over all the elements that were after it. This will be definitely O(n) if we consider a case of deleting an element from the 0^th index.

Deleting element at the 3rd index and filling the gap by left shifting the rest of the elements, The resultant array becomes – { A, B, C, D, E }.

Arrays: Worst-case time complexities (Chart).

Good vs Bad Practices

Let us see some of the Good and Bad ways of using Arrays in Java.

// Good, go for this
dataType[] refVariable; // Recommended

// bad, don't use this
dataType refVariable[]; // not recommended but works fine.

Array of integers

Declaration, Instantiation

Let us see how we can declare and initialize a java array of integers.

Approach # 01

int[] array = new int[10];

Approach # 02

int[] array; // declaration
array = new int[10] // instantiation of array

Declaration, Instantiation with values

Approach # 01

int[] array = new int[3];
array[0] = 100;
array[1] = 200;
array[2] = 300;

Approach # 02

Here, we didn’t mention the size, but we initialized with values and java considers this as the size by counting the elements on the right flower brackets and creating an array in memory.

int[] array = { 100, 200, 300 };

Print Elements

Let us declare an array with leap years and try to access and print them.

class HelloWorld {
  public static void main(String args[]) {
    int[] array = {2000, 2004, 2020, 2024};
    System.out.println(array); // prints [I@28d93b30 which is hash, @ memory location address.
  }
}

We cannot print array elements directly in java, unlike javascript. So we have to either use a for-loop to iterate over all the elements or print them or we use a simple toString() method from the Arrays class to print all the elements in O(n) time, where n is the number of elements present in the array.

The following code snippet explains this approach.

import java.util.Arrays;

class HelloWorld {
  public static void main(String args[]) {
    int[] array = {2000, 2004, 2020, 2024};
    System.out.println(Arrays.toString(array));
  }
}

Array of Strings

Declaration, Instantiation

Let us see how we can declare and initialize a java array of strings.

Appraoch # 01

String[] strings = new String[10]

Appraoch # 02

String[] strings;
string = new String[10]

Declaration, Instantiation with values

Appraoch # 01

String[] strings = new String[4];
strings[0] = "English";
strings[1] = "Spanish";
strings[2] = "French";
strings[3] = "latin";

Appraoch # 02

Here, we didn’t mention the size but we initialized with values and java considers this as the size by counting the elements on the right flower brackets and creating an array in memory.

String[] strings = { "English", "Spanish", "French", "latin" };

Print Elements

Let us declare an array with leap years and try to access and print them.

class HelloWorld {
  public static void main(String args[]) {
    String[] languages = {"English", "Spanish", "French", "latin"};
    System.out.println(strings); // prints [I@28d93b30 which is hash, @ memory location address.
  }
}

We cannot print array elements directly in java, unlike javascript. So we have to either use a for-loop to iterate over all the elements or print them or we use a simple toString() method from the Arrays class to print all the elements in O(n) time, where n is the number of elements present in the array.

import java.util.Arrays;

class HelloWorld {
  public static void main(String args[]) {
    String[] languages = {"English", "Spanish", "French", "latin"};
    System.out.println(Arrays.toString(languages));
  }
}

Array of objects

Everything is the same for an array of objects like we discussed for an array of integers and an array of strings.