Array Data Structure

An array is a very basic data structure. It can be used to implement another data structure.

Here are the few properties of the array -

• Store elements in the contiguous memory.

    x = [10, 11, 32, 0, -1, 22];
    suppose &x[0] = 0X0234
    then &x[1] will be 0X0235
        &x[2] will be 0X0236
        and so on...
  Note: & (ampersand) denotes as the memory address
  

• Store elements of same type like if it is defined as integer then it can only stores integers.

  int x[10];
  // Now try to add x[0] = 'c';
  // it will throw an error 
  

• Can possible random access. Note in practical array index start from 0.

  x = [1, 4, 2, 5, 6, 2];
  print(x[0]); // output 1
  print(x[3]) //output 5
  print(x[100]) // throw an error because element not found
  

• Insertion at the end takes O(1) time and deletion at the end takes O(n) time.

• Insertion takes O(n) time if it’s not the end element.

• If the size of an array is N then it can be indexed from 0…N-1 or 1…N (theoretically).

• Total size of the array depends on the length of the array and its data type

    int x[10];
    /**
    total size = size of int * 10
                  = 4 bytes * 10
                  = 40 bytes
    **/
    
    char name[100];
    /**
     total size = size of char * 100
                  = 1 bytes * 10
                  = 100 bytes
    **/
  

Underflow and Overflow Conditions:

• Underflow: This condition occurs when you are accessing elements from an array with an index less than 0.
• Overflow: This condition occurs when you are accessing elements to an array with an index greater than N-1.

    int x[10]; 
    // The valid range of values for the example above is 0 through 9. The first element of the array is accessed using index value 0 and the last element of the array is accessed using index value 9.
    // An overflow error occurs when one attempts to access the example array using an index value greater than 9.
    // An underflow error occurs when one attempts to access the example array using an index value less than 0.
  

Practice Questions of Array:

1. How do you find the missing number in a given integer array of 1 to 100?
2. How do you find the duplicate number on a given integer array?
3. How do you find the largest and smallest number in an unsorted integer array?
4. How do you find all pairs of an integer array whose sum is equal to a given number?
5. How do you find duplicate numbers in an array if it contains multiple duplicates?
6. How are duplicates removed from a given array in Java?
7. How is an integer array sorted in place using the quicksort algorithm?
8. How do you remove duplicates from an array in place?
9. How do you reverse an array in place in Java?
10. How are duplicates removed from an array without using any library?