Arrays and ArrayList in JAVA
Tags: programming, coding, java, beginners
Published: 2024-05-09 22:48:46

## What is Array?

An array in Java is a fixed-size collection of elements of the same data type. It allows you to store and access multiple values under a single variable name. Arrays are indexed starting from 0 and are useful for managing collections of data efficiently.

## Why do we need Arrays?

Arrays are essential because they:

1. Group related data under one variable.
2. Allow efficient access to individual elements.
3. Optimize memory usage.
4. Facilitate iteration through elements.
5. Enable passing data to functions efficiently.

## Syntax of Array

In Java, the syntax for declaring and initializing an array is as follows:

```
// Example: declaring and initializing an array of integers with a size of 5
int[] numbers = new int[5];
```

Alternatively, you can declare and initialize the array in separate steps:

```
int[] numbers; // Declaration
numbers = new int[5]; // Initialization
```
You can also initialize the array with values:

```
// Example: initializing an array of integers with specific values
int[] numbers = {10, 20, 30, 40, 50};
```

## How does Array work?

Arrays in Java store elements of the same data type in consecutive memory locations, accessible by index starting from 0. They have a fixed size and are efficient for accessing and manipulating data.

## Internal working of an Array

Internally, arrays in Java are implemented as contiguous blocks of memory where elements of the same data type are stored sequentially. Here's a deeper look at how arrays work internally in Java:

1. **Memory Allocation**: When you declare an array in Java, memory is allocated for it based on the specified size and data type. This memory allocation is done from the heap, the region of memory reserved for dynamic memory allocation in Java.

2. **Contiguous Storage**: Array elements are stored consecutively in memory, one after another. This contiguous storage ensures efficient memory access, as elements can be accessed directly using their indices.

3. **Indexing**: Each element in the array is assigned an index starting from 0. When you access an element of the array using its index, the Java runtime calculates the memory address of the element based on its index and the size of the data type.

4. **Element Access**: Once the memory address of the desired element is calculated, the runtime retrieves the value stored at that address and returns it to the program. This process of accessing elements by index is very efficient, typically taking constant time, O(1).

5. **Fixed Size**: Arrays in Java have a fixed size, meaning their size cannot be changed after they are created. If you need to store more elements than the size of the array allows, you would need to create a new array with a larger size and copy the elements from the old array to the new one.

6. **Primitive vs. Reference Types**: Arrays can hold elements of primitive data types (such as int, float, char) or reference types (such as objects). When an array holds elements of reference types, it actually holds references (memory addresses) to the objects rather than the objects themselves.

7. **Garbage Collection**: Arrays, like other objects in Java, are subject to automatic garbage collection. Once an array is no longer referenced by any part of the program, it becomes eligible for garbage collection, and the memory it occupies is reclaimed by the JVM.

Overall, arrays provide a low-level mechanism for efficiently storing and accessing collections of elements in memory, making them a fundamental data structure in Java.

## Continuity of an Array

1. **Array objects are typically located in the heap**. In Java, arrays are objects, and as such, they are allocated memory on the heap.

2. **Heap objects are not necessarily stored contiguously**. While the elements within an array object are contiguous, the overall structure of the heap doesn't guarantee that objects are stored consecutively.

3. **Dynamic Memory Allocation** is indeed used for arrays and other objects in Java. Memory for arrays is allocated at runtime, allowing for flexibility in memory usage.

Therefore, while the elements within an array are guaranteed to be stored contiguously, the arrangement of objects in the heap may not be continuous. This behavior is dependent on how the JVM manages memory.

## Index of an Array

The index of an array is a numeric value representing the position of an element within the array. It starts from 0, increments by 1 for each subsequent element, and allows for direct access to array elements.

## New Keyword

The `new` keyword in Java is used to dynamically allocate memory for objects at runtime. It creates instances of classes, allocates memory on the heap, invokes constructors to initialize objects, returns references to the allocated memory, and enables automatic garbage collection.

## String Array

A string array in Java is an array that holds elements of type String. It allows you to store multiple strings under a single variable name, making it useful for managing collections of text data.

## What is null in JAVA?

`null` in Java represents the absence of a value or an uninitialized object reference. It's used to indicate that a variable does not currently refer to any object and can lead to a `NullPointerException` if accessed improperly.

## Array Input

**For loop**

```
        Scanner scanner = new Scanner(System.in);

        // Get the size of the array from the user
        System.out.print("Enter the size of the array: ");
        int size = scanner.nextInt();

        // Create the array
        int[] numbers = new int[size];

        // Input the elements of the array
        System.out.println("Enter the elements of the array:");
        for (int i = 0; i < size; i++) {
            numbers[i] = scanner.nextInt();
        }

        // Display the elements of the array
        System.out.println("The elements of the array are:");
        for (int i = 0; i < size; i++) {
            System.out.println(numbers[i]);
        }
```

**For each loop**

```
        Scanner scanner = new Scanner(System.in);

        // Get the size of the array from the user
        System.out.print("Enter the size of the array: ");
        int size = scanner.nextInt();

        // Create the array
        int[] numbers = new int[size];

        // Input the elements of the array
        System.out.println("Enter the elements of the array:");
        for (int i = 0; i < size; i++) {
            numbers[i] = scanner.nextInt();
        }

        // Display the elements of the array using for-each loop
        System.out.println("The elements of the array are:");
        for (int number : numbers) {
            System.out.println(number);
        }
```

## toString() Method

```
        int[] numbers = {1, 2, 3, 4, 5};
        String str = Arrays.toString(numbers);
        System.out.println(str); // Output: [1, 2, 3, 4, 5]

```
## Storage of objects in heap

Objects in Java are stored in the heap memory. When you create an object using the `new` keyword, memory is allocated on the heap to store its data, and a reference to this memory location is returned. Java's automatic garbage collection manages memory deallocation, ensuring efficient use of heap memory resources.

## Array passing in function

You can pass arrays as parameters to functions in Java, allowing you to work with array elements within the function. Modifications made to the array within the function affect the original array. This enables modularization and reusability of code when working with arrays.

```
public class ArrayExample {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        printArray(numbers); // Pass the array to the function
    }

    // Function to print array elements
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
```

## Multi-dimensional Arrays

Multi-dimensional arrays in Java are arrays of arrays, allowing you to create tables or matrices with rows and columns. They are useful for representing data in multiple dimensions, such as 2D grids or 3D spaces.

Here's an example of how to create and work with multi-dimensional arrays in Java:

```
public class MultiDimensionalArrayExample {
    public static void main(String[] args) {
        // Creating a 2D array (matrix)
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        // Accessing elements of the 2D array
        System.out.println(matrix[0][0]); // Output: 1
        System.out.println(matrix[1][2]); // Output: 6

        // Iterating over the 2D array
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}
```

## Internal working of 2D Array

can be written like

`int[][] arr = new int[3][];`

individual arrays can have different size

A 2D array in Java is internally represented as an array of arrays, with elements stored row by row in contiguous memory locations. Accessing elements is efficient, using row and column indices to calculate the memory location directly.

## 2D Array Input and Output

```
import java.util.Scanner;

public class TwoDArrayInputOutput {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Get the dimensions of the 2D array from the user
        System.out.print("Enter the number of rows: ");
        int rows = scanner.nextInt();
        System.out.print("Enter the number of columns: ");
        int columns = scanner.nextInt();

        // Create the 2D array
        int[][] matrix = new int[rows][columns];

        // Input the elements of the 2D array
        System.out.println("Enter the elements of the 2D array:");
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        // Output the 2D array
        System.out.println("The 2D array is:");
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }

        scanner.close();
    }
}
```
Arrays are Mutable

## Complexity Analysis of Operations on Array:

**Time Complexity:**

Operation:

Traversal O(N)
Insertion O(N)
Deletion O(N)
Searching O(N)

**Space Complexity:**

Operation:

Traversal O(1)
Insertion O(N)
Deletion O(N)
Searching O(1)

## Advantages of Array:

- Arrays allow random access to elements. This makes accessing elements by position faster.
- Arrays have better cache locality which makes a pretty big difference in performance.
- Arrays represent multiple data items of the same type using a single name.
- Arrays are used to implement the other data structures like linked lists, stacks, queues, trees, graphs, etc.

## Disadvantages of Array:

- As arrays have a fixed size, once the memory is allocated to them, it cannot be increased or decreased, making it impossible to store extra data if required. An array of fixed size is referred to as a static array. 
- Allocating less memory than required to an array leads to loss of data.
- An array is homogeneous in nature, so a single array cannot store values of different data types. 
- Arrays store data in contiguous memory locations, which makes deletion and insertion very difficult to implement. This problem is overcome by implementing linked lists, which allow elements to be accessed sequentially.  

## Applications of Array:

They are used in the implementation of other data structures such as array lists, heaps, hash tables, vectors, and matrices.
Database records are usually implemented as arrays.
It is used in lookup tables by computer.

## Dynamic Arrays 

## What is ArrayList?

An `ArrayList` in Java is a resizable array-like data structure provided by the `java.util` package. It implements the `List` interface and extends the `AbstractList` class, making it a part of the Java Collections Framework. Unlike regular arrays, `ArrayList` can dynamically resize itself as elements are added or removed.

Here are some key characteristics of `ArrayList`:

1. **Resizable**: Unlike arrays, which have a fixed size, `ArrayList` can dynamically grow or shrink in size as elements are added or removed.

2. **Ordered Collection**: `ArrayList` maintains the order of elements in which they are inserted. You can access elements by their index.

3. **Allows Duplicates**: `ArrayList` can contain duplicate elements. It preserves the insertion order, so elements can be added and accessed based on their position.

4. **Indexed Access**: You can access elements in an `ArrayList` using their index. This allows for efficient retrieval and modification of elements.

5. **Backed by Array**: Internally, an `ArrayList` is backed by an array. When the array's capacity is reached, `ArrayList` automatically resizes the underlying array to accommodate more elements.

6. **Iterating Over Elements**: `ArrayList` provides various methods to iterate over its elements, including traditional loops, enhanced for loops, and iterators.

Here's a basic example of using `ArrayList`:

```
import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // Create a new ArrayList
        ArrayList<Integer> numbers = new ArrayList<>();

        // Add elements to the ArrayList
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);

        // Print the ArrayList
        System.out.println("ArrayList: " + numbers);

        // Accessing elements
        int value = numbers.get(1);
        System.out.println("Element at index 1: " + value);

        // Size of the ArrayList
        System.out.println("Size of the ArrayList: " + numbers.size());
    }
}
```

`ArrayList` is widely used in Java for its flexibility, ease of use, and dynamic resizing capabilities, making it a versatile choice for storing and manipulating collections of elements.

## ArrayList Functions

ArrayList functions, also known as methods, are built-in operations provided by the `ArrayList` class in Java. These methods enable you to perform various operations on ArrayLists, such as adding, removing, searching, sorting, and iterating over elements. Here are some commonly used ArrayList functions in Java:

1. **Adding Elements**:
   - `add(E e)`: Adds the specified element to the end of the ArrayList.
   - `add(int index, E element)`: Inserts the specified element at the specified position in the ArrayList.

2. **Removing Elements**:
   - `remove(Object o)`: Removes the first occurrence of the specified element from the ArrayList.
   - `remove(int index)`: Removes the element at the specified position in the ArrayList.

3. **Accessing Elements**:
   - `get(int index)`: Returns the element at the specified position in the ArrayList.
   - `set(int index, E element)`: Replaces the element at the specified position in the ArrayList with the specified element.

4. **Size and Capacity**:
   - `size()`: Returns the number of elements in the ArrayList.
   - `isEmpty()`: Returns true if the ArrayList is empty; otherwise, returns false.
   - `ensureCapacity(int minCapacity)`: Increases the capacity of the ArrayList, if necessary, to ensure that it can hold at least the specified number of elements.

5. **Searching and Sorting**:
   - `contains(Object o)`: Returns true if the ArrayList contains the specified element; otherwise, returns false.
   - `indexOf(Object o)`: Returns the index of the first occurrence of the specified element in the ArrayList; returns -1 if the element is not found.
   - `sort(Comparator<? super E> c)`: Sorts the elements of the ArrayList using the specified comparator.

6. **Iterating Over Elements**:
   - `forEach(Consumer<? super E> action)`: Performs the given action for each element of the ArrayList until all elements have been processed or the action throws an exception.
   - `iterator()`: Returns an iterator over the elements in the ArrayList.

7. **Converting to Array**:
   - `toArray()`: Returns an array containing all of the elements in the ArrayList in proper sequence.

```
import java.util.ArrayList;

public class ArrayListFunctionsExample {
    public static void main(String[] args) {
        // Create an ArrayList
        ArrayList<Integer> numbers = new ArrayList<>();

        // Adding elements
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);

        // Removing elements
        numbers.remove(Integer.valueOf(20));

        // Accessing elements
        int firstElement = numbers.get(0);

        // Size
        int size = numbers.size();

        // Sorting
        numbers.sort(null);

        // Iterating
        for (Integer number : numbers) {
            System.out.println(number);
        }
    }
}
```

## Internal working of ArrayList

An `ArrayList` in Java dynamically manages an array internally to accommodate the addition or removal of elements. It automatically resizes its underlying array when needed, typically using a doubling strategy for capacity management. This allows for flexible storage of collections of elements with efficient random access and ensures fast element retrieval.

## Multi-Dimensional ArrayList

In Java, you can create a multi-dimensional ArrayList by nesting ArrayLists within each other. This allows you to create structures resembling matrices or grids with multiple dimensions. Here's how you can create and work with a multi-dimensional ArrayList:

```
import java.util.ArrayList;

public class MultiDimensionalArrayListExample {
    public static void main(String[] args) {
        // Create a 2D ArrayList
        ArrayList<ArrayList<Integer>> matrix = new ArrayList<>();

        // Add rows to the 2D ArrayList
        for (int i = 0; i < 3; i++) {
            ArrayList<Integer> row = new ArrayList<>();
            for (int j = 0; j < 3; j++) {
                row.add(i * 3 + j + 1); // Add elements to the row
            }
            matrix.add(row); // Add the row to the 2D ArrayList
        }

        // Accessing elements
        int value = matrix.get(1).get(2); // Accessing element at row 1, column 2
        System.out.println("Element at row 1, column 2: " + value);

        // Printing the 2D ArrayList
        for (ArrayList<Integer> row : matrix) {
            for (int element : row) {
                System.out.print(element + " ");
            }
            System.out.println();
        }
    }
}
```

In this example:

- We create a 2D ArrayList named `matrix` by nesting ArrayLists within each other.
- We add rows to the 2D ArrayList using nested loops, where each row is an ArrayList containing integer elements.
- We access elements of the 2D ArrayList using the `get()` method on both the outer and inner ArrayLists.
- We print the elements of the 2D ArrayList using nested loops to traverse each row and element within the rows.

This approach allows you to create and manipulate multi-dimensional data structures using ArrayLists in Java. You can extend this concept to create 3D, 4D, or higher-dimensional ArrayLists by nesting ArrayLists further.