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

Last updated : 13 October 2021

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 the index
Figure 1 : Array data structure

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

In this chapter, we will investigate how one-dimensional arrays are created and managed in Java. We will also perform a set of basic operations, such as sorting, delete, insert, search, and reverse elements on an array. More complex and efficient algorithms are discussed in later chapters. Please note that we use 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.

Figure 2 : Empty array

Insert an item into an array

When an array is defined with a given size, the size cannot be extended or shrank 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 important 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, just 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. If we want to populate the array in order, we have to know the index of the next empty position in the array. Let's find out how can we insert elements into the array without leaving any 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. If this is an array of Objects, the comparison would have been against null. If the int array is already full, the new value is not inserted.

Delete an item from an array

To delete an item from an array, first, we have to know the index of the item to be deleted. Then, we have to left-shift all the items located right to the deleted item. This 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 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

This 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

With a minor change to the max number algorithm, we can find the minimum 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 : 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 and search, etc. That is a prerequisite to prepare for the actual data structures and algorithms on arrays.

In the next chapter, we will find out how to create a multi-dimensional array and how to 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.

Lance
By: Lance
Lance is a software engineer with over 15 years of experience in full-stack software development.
Read more...

Comments are disabled

No Comments