Array

Array is a data structure that holds a fixed number of values (data points) of the same data type. Each item, or value, is called an element. When we initialize an array, we get to choose what type of data(data type) it can hold and how many elements(length) it can hold. 

Each position in the array has an index, starting at 0.

The items in an array are allocated at adjacent(next to each other) memory locations. 

By default, an array are filled with default value of its data type once it’s initialized. For example an array of int will have 0 as the default value.

From the above image:

  • data type – integer
  • length – 6
  • array name – Arr
  • first index – 25
  • last index – 7
int[] arr = new int[6];
arr[0] = 25;
arr[1] = 35;
arr[2] = 45;
arr[3] = 53;
arr[4] = 25;
arr[5] = 7;

System.out.println("length: " + arr.length);

System.out.println(Arrays.toString(arr));

arr = new int[]{25, 35, 45, 53, 25, 7};

System.out.println("length: " + arr.length);

System.out.println(Arrays.toString(arr));
length: 6
[25, 35, 45, 53, 25, 7]
length: 6
[25, 35, 45, 53, 25, 7]

 

Worst Case(Big O)

space
lookup
append(last element)
insert
delete

Advantages

  • Fast lookups – retrieving an element at a given index takes  time, regardless of the length of the array.
  • Fast appends – adding a new element at the end of the array takes  time, if the array has space.
  • An array can store multiple values in a single variable.
  • Arrays are fast as compared to primitive data types.
  • We can store objects in an array.
  • Members of the array are stored in consecutive memory locations.

Disadvantages

  • 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.)
  • Costly inserts and deletes. You have to “scoot over” the other elements to fill in or close gaps , which takes worst-case  time.
  • We cannot increase or decrease the size of the array at runtime.
  • In array, memory wastage can be more.
  • We can only store similar data type items.

Inserting elements into an Array

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.

In the worst case we’re inserting into the 0th index in the array (prepending), so we have to “scoot over” everything in the array. That’s  time.

In java

If we want to insert something into an array, first we must have the index or position where the element is going to. Once we have the position, we just set it.

In the worst case the time complexity is  time.

 

Deleting elements from an Array

Array elements are stored adjacent to each other. So when we remove an element, we have to fill in the gap—”scooting over” all the elements that were after it.

In the worst case we’re deleting the 0th item in the array, so we have to “scoot over” everything else in the array. That’s O(n) time.

Why not just leave the gap? Because the quick lookup power of arrays depends on everything being sequential and uninterrupted. This lets us predict exactly how far from the start of the array the 138th or 9,203rd item is. If there are gaps, we can no longer predict exactly where each array item will be.

In java

If we want to delete an element from an array, first we must have the index or position where the element is in. Once we have the position, we just set it to its data type default value, 0 or null. FYI, there is no Delete operation available on Arrays. We can symbolically delete an element by setting it to some specific value, e.g. -1, 0, etc. depending on our requirements

In the worst case the time complexity is  time.

 




Subscribe To Our Newsletter
You will receive our latest post and tutorial.
Thank you for subscribing!

required
required


Leave a Reply

Your email address will not be published. Required fields are marked *