Introduction

Have you ever been curious about how an Arraylist (C#/JAVA) works behind the scenes? Yes, this post deals with dynamic/extendable/resizable Arraylist dubbed here as an infinite array as per the article title. I talk about the power of dynamic Arraylist and its Achilles heel weakness.

Ubiquitous Dynamic ArrayList

Unlike a regular array, ArrayList doesn’t require a predetermined count/capacity to be mentioned upfront. Why so? But, before that what is an ArrayList? A dynamic array ( or here ArrayList) is a special type of array that can grow and shrink by the addition or removal of items from its end, while still supporting constant-time access (like a regular array) to each item stored in the array given its index. Since the size of an array varies over time, space-efficient maintenance of a resizable array requires dynamic memory allocation from the heap. Here is a pictorial representation of the above  explanation:

For the sake of disambiguation, size means here, the size of the ArrayList holding legit values excluding the holes or unused spaces. Capacity means the real length of the ArrayList, including the unused + used spaces.

Let’s say you start by adding value 2 and then 7 etc,. See how the capacity of the ArrayList grows when the size equals capacity. This is called as doubling capacity approach, where when you have filled the ArrayList with values to its fullest capacity, it immediately doubles the capacity and copies the previous content of values into the new list. This will lead to empty holes in the new ArrayList.

Nature of the problem

As much as the infinite size of one size fits all concept enamors every software programmer, there is a downside to this. Remember, I told you all about doubling ArrayList capacity and copying from old to new doubled capacity ArrayList, this slows down (performance) by adding new elements to the list when it hits the dynamic allocation and copying part. This in computer science terminology is called amortized cost. Which ideally is the worst of a worst-case scenarios in performance and efficiency. One doesn’t feel the pain when you deal with smaller size problems but as the size becomes bigger, like 20K items, there is an obvious huge cost associated with this approach. C# source/JAVA source follows suit when it comes to this doubling capacity approach.

Doubling Capacity Pseudo-Code 

Conclusion

Be wary about choosing ArrayList or any sort of dynamic data structure. There is a huge penalty of performance cost associated with it. One thumb rule I have applied is, when you can predetermine the size of an array, start with that size and work on that array. Amateurs tend to oversee the perils of ArrayList.

“Craft is the uncommon skill developed by the constant endeavor, incessant curiosity, relentless pursuit, passionate application, persistent refinement, meticulous alteration and, made through practice and discipline in the formation of a work of art (software). It could be a sculpture, a chai, a chicken tikka, a painting, a symphony, a software…” ~ CBA.