top of page

Internal working of ArrayList in Java

Writer's picture: mohit patelmohit patel

 



Introduction:

The ArrayList class in Java is a widely utilized collection for storing and accessing data. With its ability to preserve insertion order, accommodate duplicates, and offer efficient traversing, ArrayList have become a popular choice among developers. In this article, we will delve into the inner workings of ArrayList, exploring how they are created, how they dynamically grow their capacity, and how they can be optimized for different scenarios. Additionally, we will touch upon synchronization considerations and alternative data structures that can be used in specific situations. By the end of this article, you will have a comprehensive understanding of ArrayList and be equipped with valuable insights for utilizing them effectively in your Java programs.


Here are the key characteristics of ArrayList:


1. Contains duplicates: ArrayList allow duplicate elements.

2. Preserves insertion order: The order in which elements are added to the ArrayList is maintained.

3. Non-synchronized: ArrayList are not synchronized by default, meaning they are not thread-safe.

4. Allows null values: ArrayList can store null values.

5. Faster traversing: Traversing an ArrayList is efficient due to its underlying data structure.


Now let's delve deeper into the workings of ArrayList, including how they handle capacity and growth. To fully grasp the concept, it's important to understand the various ways to create an ArrayList. If you're unfamiliar with these methods, don't worry. This article will provide you with accurate details.


Creating an ArrayList:

The three ways to create an ArrayList are as follows:


1. Empty ArrayList:



ArrayList<String> emptyList = new ArrayList<>();


2. ArrayList with initial capacity:



ArrayList<Integer> numbers = new ArrayList<>(20);


3. ArrayList from a collection:



List<String> colors = Arrays.asList("Red", "Green", "Blue");
ArrayList<String> colorList = new ArrayList<>(colors);

Internal working of an ArrayList:

As there are three ways to create an ArrayList, the ArrayList class offers three corresponding constructors. When you create an instance of ArrayList using one of these constructors, it initializes the ArrayList with the capacity you specified or with a default capacity of 10 elements.


Now that we know the default capacity is 10, let's explore how ArrayList dynamically grows when it becomes full. ArrayLists utilize dynamic arrays as their underlying data structure. Unlike traditional arrays, ArrayLists increase their capacity when the number of elements reaches a specific threshold. This threshold is calculated using the formula `(load factor * current capacity)`, where the default load factor is 0.75f. For the initial capacity of 10, the threshold is calculated as follows:


Threshold = load factor * current capacity

= 0.75 * 10

= 7


Hence, the default threshold is 7. Therefore, when an ArrayList contains 7 elements and an 8th element is added, the following occurs:

1. A new ArrayList is created with a capacity equal to the current capacity plus 50% of the current capacity.

2. All previous elements are copied to the new ArrayList.

3. The new ArrayList is returned.


Fun Fact: The capacity growth rate mentioned above (50%) applies to Java version 7 and onwards. In Java 6, the capacity increases by 1.5 times!

On the topic of shrinking an ArrayList, while growing dynamically is beneficial in terms of memory usage, ArrayList do not automatically shrink when elements are removed. However, you can manually shrink the ArrayList using the `trimToSize()` function, which sets the size of the ArrayList to its current size.


Regarding synchronization, ArrayList do not support it inherently. While this improves the performance of ArrayList, it is not advisable to use them in a multithreaded environment. Instead, you can make an ArrayList synchronized using `Collections.synchronizedList()`. Here's an example code snippet:




List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());


This creates a synchronized wrapper on the ArrayList, ensuring thread safety. However, it does not guarantee atomicity for compound operations. For compound operations, you can replace ArrayLists with `CopyOnWriteArrayList`. Similarly, if you have scenarios involving frequent insertion and deletion operations, replacing ArrayList with LinkedList might be more efficient.


Conclusion:

In conclusion, ArrayList provide a flexible and efficient solution for storing and accessing data in Java. With their ability to handle duplicates, preserve insertion order, and offer fast traversing, ArrayList have become a go-to choice for developers. By understanding the various ways to create an ArrayList and how it dynamically grows its capacity, you can optimize memory usage and improve performance in your programs. While ArrayLists are not synchronized by default, you can make them thread-safe using synchronization wrappers or explore alternative data structures like CopyOnWriteArrayList or LinkedList for specific scenarios. With this knowledge in hand, you can leverage ArrayLists effectively to handle data in your Java applications with confidence and efficiency.




64 views0 comments

Recent Posts

See All

Battle of the Backends: Java vs Node.js

Comparing Java and Node.js involves contrasting two distinct platforms commonly used in backend development. Here’s a breakdown of their...

Comments


bottom of page