What is the difference between Array and ArrayList in Java?

Imagine packing for a trip with two choices for luggage: a regular suitcase (Array) and an expandable suitcase (ArrayList).

Array: It's like a regular suitcase. You choose its size when you pack, like a small, medium, or large suitcase. Once you pick, it's fixed. If it's small and you try to add more, it won't fit. If it's not full, you still carry the empty space. In Java, an Array of size 10 can only store 10 elements, no more, no less.

ArrayList: This is an expandable suitcase. It grows or shrinks as needed. Start with a few items? It adjusts. Found souvenirs? It expands. Decided to leave stuff behind? It shrinks. In Java, ArrayList is part of the Java Collection Framework and adjusts its size as you add or remove elements.

Key Differences:

1. Size: Arrays have fixed sizes. ArrayLists can change size dynamically.
2. Type: Arrays can hold primitive types (like int, char) and objects. ArrayLists only hold objects, not primitives.
3. Performance: Adding or removing items in an ArrayList might be slower due to potential resizing and copying to a new location.
4. Utility: ArrayLists offer methods like .add(), .remove(), .indexOf(), making them more user-friendly than Arrays.

Time and Space Complexities of Arrays and ArrayLists in Java

Understanding the time and space complexities of Arrays and ArrayLists is like knowing how long it takes to do tasks with your regular suitcase (Array) or expandable suitcase (ArrayList), and how much space they take up.

Arrays

• Space Complexity: O(n). The size is fixed, and it occupies space for all its elements, regardless of whether they are used or not.
• Accessing an Element (Read/Write): O(1). Like picking an item from a specific pocket in your suitcase; it's quick because you know where it is.
• Inserting/Deleting an Element: Not applicable in the traditional sense, as the size is fixed. But if you consider overwriting an existing element or setting it to null, it's O(1).

ArrayLists

• Space Complexity: O(n). However, it can be more due to the dynamic resizing. When an ArrayList grows, it usually doubles its size, which temporarily increases the space requirement before it's filled up.
• Accessing an Element (Read/Write): O(1). Similar to arrays, direct index access.
• Inserting an Element:
  • Average Case: O(1). If there's room in the ArrayList.
  • Worst Case (resizing required): O(n). Resizing involves creating a new array and copying elements, which takes more time.
• Deleting an Element:
  • Average/Worst Case: O(n). Removal requires shifting elements to fill the gap left by the deleted element, which takes more time as the size of the ArrayList increases.

In summary, both arrays and ArrayLists offer quick access to elements. Arrays have a fixed space, while ArrayLists can resize, affecting their space complexity. Inserting and deleting elements are generally more time-consuming in ArrayLists, especially when resizing or shifting elements is involved.

Choose Arrays when you know the exact number of elements. Choose ArrayLists for flexibility and convenience.