All you need to know about Array Data Structure - one-dimensional arrays

Last updated : Jul 30, 2023 12:00 AM

An array is a fixed-length list of variables of the same data type. An array can be one-dimensional or multidimensional.

Array length is fixed. The length cannot be extended or trimmed
All variables stored in an array must have the same data type
The variables stored in an array can be referenced by their index

Arrays are the most common data structure used across many programming languages. Most built-in data structures in programming languages, such as Lists, Maps, and tables, use arrays under the hood. There are two types of arrays.

Single dimensional array
Multidimensional array

This chapter will investigate how one-dimensional arrays are created and managed in Java. We will perform basic operations, such as sorting, deleting, inserting, searching, and reversing elements on an array. More complex and efficient algorithms are discussed in later chapters. Please note that we use the unsorted arrays below examples. We will use sorted arrays when we discuss more standard and complex data structures.

One dimensional array

How to declare and define an array

int[] arr = new int[10]; //Array image

The above code declares the variable arr and defines it as an array of integers with an array length of 10. This code creates an array with empty elements. This array can hold only integer values.

Insert an item into an array

When an array is defined with a given size, the size cannot be extended or shrunk later. Therefore, an array defined as arr[10] can hold a maximum of 10 elements. The positions or indexes of the array are from 0 to length-1. It is essential to maintain this range, as any violations will cause an ArrayIndexOutOfBoundsException. That means you are trying to access an array element with an out-of-range index.

Figure 3 : Empty array with length of 10

The valid range for the above array is

int length = arr.length -> 10
First element index - 0
Last element index - length-1 -> 9

To insert an item, mention the index position of the item to be inserted. Note that if a value exists in the index position, the new value will override the existing value.

arr[0] = 100; //Insert into first position
arr[1] = 124; //Insert into second position
arr[9] = 800; //Insert into 10th (last) position

Figure 4 : Array with randomly inserted data

Note that the insert position depends on the index. To populate the array in order, we must know the index of the next empty position in the array. Let's find out how we can insert elements into the array without leaving empty indexes between items.

public class LearnBestCoding {
   static int[] arr = new int[10];	
   public static void main(String[] args) {
      insertItem(arr, 24);
      insertItem(arr, 10);
      insertItem(arr, 35);
      insertItem(arr, 1);
      insertItem(arr, 16);
      insertItem(arr, 8);
      System.out.println(Arrays.toString(arr));
   }

   private static void insertItem(int[] arr, int item) {
      int length = arr.length;
      for(int a=0; a < length; a++) {
         if(arr[a] == 0) {
            arr[a] = item;
            break;
         }
      }
   }
}

Output : [24, 10, 35, 1, 16, 8, 0, 0, 0, 0]

Note that we use an array of integers. The default uninitialized value for int is 0. Therefore, we check if each position is 0 to determine if a value in that position exists or not. The comparison will have been against null if this is an array of objects. The new value is not inserted if the int array is already full.

Delete an item from an array

To delete an item from an array, first, we have to know the item's index to be deleted. Then, we have to left-shift all the items to the deleted item. That will leave the array in a consistent state. The below code deletes an item from the array and shifts the remaining items to the left to fill the gap.

public class LearnBestCoding {
   static int[] arr = {24, 10, 35, 1, 16, 8, 0, 0, 0, 0};	

   public static void main(String[] args) {
      deleteItem(arr, 24);
      System.out.println(Arrays.toString(arr));
   }

   private static void deleteItem(int[] arr, int item) {
     int length = arr.length;
     for(int a=0; a < length-1; a++) {
        if(arr[a] == item) {
           for(int b=a; b < length-1; b++) {
              arr[b] = arr[b+1];
           }
           arr[length-1] = 0;//To ensure last element set to default value
           break;
        }
     }
   }
}

Output : [10, 35, 1, 16, 8, 0, 0, 0, 0, 0]

Search for an item in an array

Search algorithms return the item index for the matching element. We will be discussing search algorithms in more detail during advanced algorithms topics. If the search item doesn't exist in the array, the code will return -1.

public class LearnBestCoding {
	
   static int[] arr = {24, 10, 35, 1, 16, 8, 0, 0, 0, 0};	

   public static void main(String[] args) {
      System.out.println(searchItem(arr, 16));
   }

   private static int searchItem(int[] arr, int item) {
      int length = arr.length;
      for(int a=0; a < length-1; a++) {
         if(arr[a] == item) {
            return a;
         }
      }
      return -1;
   }
}

Output : 4

How to reverse elements in an array?

An array can be reversed in many different ways. The below algorithm uses the original array and modifies it during iterations.

public class LearnBestCoding {
	
   static int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};	

   public static void main(String[] args) {
      reverseArray(arr);
      System.out.println(Arrays.toString(arr));
   }

   private static void reverseArray(int[] arr) {
   int first = 0;
   int last = arr.length-1;
   int temp;
     while(first <= last) {
        temp = arr[first];
        arr[first] = arr[last];
        arr[last] = temp;
        first++;
        last--;
     }
   }
}

Output : [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Identify if a sentence is a palindrome

This reverse algorithm can also help us to solve another common code challenge asked in most interviews. How to determine if a given the word is a palindrome? We will discuss more complex variations of this question in advanced algorithm topics. But for now, let's take a look at this simple implementation.

public class LearnBestCoding {
	
   static String str = "1Able was I ere I saw Elba1";

   public static void main(String[] args) {
	
      //To eliminate any spaces
      String trimmedStr = str.replaceAll(" ", "");

      //Convert the word to array before reversing
      char arr[] = trimmedStr.toCharArray();

      reverseArray(arr);
      System.out.println("The word : " + str+ " is"+(trimmedStr.equalsIgnoreCase(String.valueOf(arr)) ? "" : " not")+" a palindrome");
}

  private static void reverseArray(char[] arr) {
	int first = 0;
	int last = arr.length-1;
	char temp;
    while(first <= last) {
      temp = arr[first];
      arr[first] = arr[last];
      arr[last] = temp;
      first++;
      last--;
    }
  }
}

Output : The word : 1Able was I ere I saw Elba1 is a palindrome

Sort array in descending order

We can sort the array in descending order with a minor change to the ascending-order sort algorithm.

public class LearnBestCoding {
	
   static int[] arr = {6, 10, 8, 9, 7, 1, 5, 3, 4, 2};	

   public static void main(String[] args) {		
      sortArray(arr);
      System.out.println(Arrays.toString(arr));
   }

   private static void sortArray(int[] arr) {		
   int length = arr.length-1;
   int temp;
      for(int a=0; a < length-1; a++) {
         for(int b=0; b < length-a; b++) {
            if(arr[b] < arr[b+1]) {
               temp = arr[b];
               arr[b] = arr[b+1];
               arr[b+1] = temp;
            }
         }
      }
   }
}

Output : [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Sort array in ascending order

That is how we sort an array in ascending order. This algorithm is called bubble sort. More about it in later chapters.

public class LearnBestCoding {
	
   static int[] arr = {6, 10, 8, 9, 7, 1, 5, 3, 4, 2};	

   public static void main(String[] args) {		
      sortArray(arr);
      System.out.println(Arrays.toString(arr));
   }

   private static void sortArray(int[] arr) {		
     int length = arr.length-1;
     int temp;
     for(int a=0; a < length-1; a++) {
        for(int b=0; b < length-a; b++) {
           if(arr[b] > arr[b+1]) {
              temp = arr[b];
              arr[b] = arr[b+1];
              arr[b+1] = temp;
           }
        }
     }
   }
}

Output : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Find maximum number in an array

This algorithm returns the index of the maximum number in the array.

public class LearnBestCoding {
	
   static int[] arr = {6, 10, 8, 9, 7, 1, 5, 3, 24, 2};	

   public static void main(String[] args) {		
      System.out.println(findMax(arr));
   }

   private static int findMax(int[] arr) {		
     int length = arr.length;
     int temp = arr[0];
     for(int a=1; a < length; a++) {
        if(arr[a] > temp) {
           temp = arr[a];
        }
     }
     return temp;
   }
}

Output : 24

Find minimum number in an array

We can find the minimum number in the array with a minor change to the max number algorithm.

public class LearnBestCoding {

   static int[] arr = {6, 10, 8, 9, 7, 1, 5, 3, 24, 2};	

   public static void main(String[] args) {		
      System.out.println(findMax(arr));
   }

   private static int findMax(int[] arr) {		
      int length = arr.length;
      int temp = arr[0];
      for(int a=1; a < length; a++) {
         if(arr[a] < temp) {
            temp = arr[a];
         }
      }
      return temp;
   }
}

Output : 1

Summary

In this chapter, we looked at how to create a one-dimensional array. We also applied basic algorithms on that array to insert, sort, delete, search, etc. That is a prerequisite to preparing for arrays' data structures and algorithms.

In the next chapter, we will learn how to create a multi-dimensional array and apply basic algorithms to perform basic operations. The multi-dimensional arrays are a bit more complex than one-dimensional arrays. Therefore, multi-dimensional arrays deserve a dedicated chapter to master them.