What is an ArrayList?

An ArrayList in Java is a resizable array implementation of the List interface. It's part of the Java Collections Framework. Unlike regular arrays, ArrayLists can dynamically grow or shrink in size as needed, which makes them highly versatile for storing and manipulating collections of objects. It is backed by an array internally.

ArrayList Class Detailed Explanation

Creation

You can create an ArrayList using one of its constructors:

• ArrayList(): Creates an empty ArrayList with an initial capacity of 10.
• ArrayList(int initialCapacity): Creates an empty ArrayList with the specified initial capacity.
• ArrayList(Collection<? extends E> c): Creates an ArrayList containing the elements of the specified collection, in the order they are returned by the collection's iterator.

 import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) {
        // Creating an empty ArrayList with default capacity (10)
        ArrayList<String> names = new ArrayList<>();

        // Creating an ArrayList with a specified initial capacity
        ArrayList<Integer> numbers = new ArrayList<>(20);

        // Creating an ArrayList from another collection
        List<String> initialNames = Arrays.asList("Alice", "Bob", "Charlie");
        ArrayList<String> moreNames = new ArrayList<>(initialNames);

        System.out.println("Names: " + names);       // Output: Names: []
        System.out.println("Numbers: " + numbers);   // Output: Numbers: []
        System.out.println("More names: " + moreNames); // Output: More names: [Alice, Bob, Charlie]
    }
} 

Adding Elements

ArrayList provides several methods to add elements:

• add(E e): Appends the specified element to the end of the list. Time Complexity: Amortized O(1)
• add(int index, E element): Inserts the specified element at the specified position in the list. Time Complexity: O(n)
• addAll(Collection<? extends E> c): Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's Iterator. Time Complexity: O(n)
• addAll(int index, Collection<? extends E> c): Inserts all of the elements in the specified collection into this list, starting at the specified position. Time Complexity: O(n)

 import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<>();

        // Adding elements to the end
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");

        System.out.println("Names after adding to the end: " + names); // Output: Names after adding to the end: [Alice, Bob, Charlie]


        // Adding an element at a specific index
        names.add(1, "David"); // Inserts "David" at index 1

        System.out.println("Names after inserting at index 1: " + names); // Output: Names after inserting at index 1: [Alice, David, Bob, Charlie]


        //Adding elements from another ArrayList
        ArrayList<String> newNames = new ArrayList<>();
        newNames.add("Eve");
        newNames.add("Frank");

        names.addAll(newNames); //add at the end
        System.out.println("Names after adding collection to end: " + names); // Output: Names after adding collection to end: [Alice, David, Bob, Charlie, Eve, Frank]


        names.addAll(2, newNames); // add at the index 2
        System.out.println("Names after adding collection at index: " + names); // Output: Names after adding collection at index: [Alice, David, Eve, Frank, Bob, Charlie, Eve, Frank]

    }
} 

Retrieving Elements

You can access elements in an ArrayList using their index:

• get(int index): Returns the element at the specified position in this list. Time Complexity: O(1)

 import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");

        // Getting the element at index 0
        String firstElement = names.get(0);

        System.out.println("First element: " + firstElement); // Output: First element: Alice
    }
} 

Removing Elements

ArrayList provides methods to remove elements:

• remove(int index): Removes the element at the specified position in this list. Time Complexity: O(n)
• remove(Object o): Removes the first occurrence of the specified element from this list, if it is present. Time Complexity: O(n)
• removeAll(Collection<?> c): Removes all of this list's elements that are also contained in the specified collection. Time Complexity: O(n*m), where n is size of the list and m is the size of the collection c
• clear(): Removes all of the elements from this list. The list will be empty after this call returns. Time Complexity: O(1)

 import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        names.add("Bob"); // Adding Bob again to demonstrate remove(Object)

        // Removing the element at index 1
        names.remove(1); // Removes "Bob" at index 1

        System.out.println("Names after removing index 1: " + names); // Output: Names after removing index 1: [Alice, Charlie, Bob]


        // Removing the first occurrence of "Bob"
        names.remove("Bob"); // Removes the first "Bob"

        System.out.println("Names after removing 'Bob': " + names); // Output: Names after removing 'Bob': [Alice, Charlie]

        // Removing all elements
        names.clear();

        System.out.println("Names after clearing: " + names); // Output: Names after clearing: []
    }
} 

Iterating

You can iterate through an ArrayList using various methods:

• For loop with index: Accessing elements using their index. Time Complexity: O(n)
• Enhanced for loop (for-each loop): A simpler way to iterate. Time Complexity: O(n)
• Iterator: Using an iterator for more control, especially when removing elements during iteration. Time Complexity: O(n)
• ListIterator: Provides bidirectional iteration and modification capabilities. Time Complexity: O(n)
• Streams: Using Java 8 streams for functional-style iteration and processing. Time Complexity: Depends on the stream operations. Can vary from O(n) to O(n log n) or more.

 import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.stream.Stream;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");

        // 1. For loop with index
        System.out.println("Using for loop with index:");
        for (int i = 0; i < names.size(); i++) {
            System.out.println(names.get(i));
        }

        // 2. Enhanced for loop (for-each loop)
        System.out.println("\nUsing enhanced for loop:");
        for (String name : names) {
            System.out.println(name);
        }

        // 3. Iterator
        System.out.println("\nUsing Iterator:");
        Iterator<String> iterator = names.iterator();
        while (iterator.hasNext()) {
            String name = iterator.next();
            System.out.println(name);
        }


        // 4. ListIterator
        System.out.println("\nUsing ListIterator:");
        ListIterator<String> listIterator = names.listIterator();
        while (listIterator.hasNext()) {
            String name = listIterator.next();
            System.out.println("Forward: " + name);
        }
        while (listIterator.hasPrevious()) {
            String name = listIterator.previous();
            System.out.println("Backward: " + name);
        }

        // 5. Streams (Java 8+)
        System.out.println("\nUsing Streams:");
        Stream<String> nameStream = names.stream();
        nameStream.forEach(System.out::println);
    }
} 

Searching

ArrayList provides methods for searching elements:

• contains(Object o): Returns true if this list contains the specified element. Time Complexity: O(n)
• indexOf(Object o): Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. Time Complexity: O(n)
• lastIndexOf(Object o): Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element. Time Complexity: O(n)

 import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        names.add("Bob"); // Adding Bob again

        // Checking if the list contains "Alice"
        boolean containsAlice = names.contains("Alice");
        System.out.println("Contains Alice: " + containsAlice); // Output: Contains Alice: true

        // Finding the index of "Bob"
        int indexOfBob = names.indexOf("Bob");
        System.out.println("Index of Bob: " + indexOfBob); // Output: Index of Bob: 1

        // Finding the last index of "Bob"
        int lastIndexOfBob = names.lastIndexOf("Bob");
        System.out.println("Last index of Bob: " + lastIndexOfBob); // Output: Last index of Bob: 3

        // Searching for a non-existent element
        int indexOfEve = names.indexOf("Eve");
        System.out.println("Index of Eve: " + indexOfEve); // Output: Index of Eve: -1
    }
} 

Resizing

ArrayList automatically handles resizing. When the ArrayList reaches its capacity, it creates a new array with a larger capacity (typically 1.5 times the old capacity) and copies the elements from the old array to the new array. This process is transparent to the user.

The resizing operation involves:

1. Creating a new array with a larger capacity.
2. Copying all elements from the old array to the new array.
3. Updating the ArrayList to refer to the new array.

Because of the element copying, the resizing operation has a time complexity of O(n), where n is the number of elements in the ArrayList. However, since resizing doesn't happen with every add() operation (only when the capacity is reached), the amortized time complexity of add() is O(1).

Time Complexity Summary