Vector vs ArrayList

Introduction

Arrays are one of the fundamental components of data structures. They play a vital role in solving everything from basic to very complex problems. The issue with arrays is that they are static and have a fixed size that we must define to store elements. What if we need a dynamically growing array and don't care about its size? Here, ArrayList and Vector, which are part of Java programming, come in handy.

The Java collection framework includes two dynamically resizable lists: ArrayList and Vector. Both extend AbstractList and implement the List, RandomAccess, Cloneable, and Serializable interfaces. Vector and ArrayList both use an ordinary array with initial capacity and dynamic growth capability.?

What is Vector?

The Vector class in Java (package java.util.Vector) since Java 1.0 implements a growable array of objects, Like an array, it contains components that can be accessed using an integer called "Index". The size of Vector automatically grows or shrinks required to accommodate adding or removing items after the instantiation of Vector. It implements all operational list operations and permits all elements, including null.

Vector is a synchronized data structure. It was introduced with Java Development Kit 1.0. Later, the vector is rectified by extending it with AbstractList, which was introduced in JDK 1.2 as part of the Java collection framework. Besides that, the vector also implements List, RandomAccess, Cloneable and Serializable interfaces. All of the operations in the vector are thread-safe and actually allow one thread at a time to enter. As a result, a vector is slower than other similar data structures, such as an array list. If a thread-safe implementation is not required, java.util.ArrayList is recommended. If a thread-safe, highly concurrent implementation is coveted, then the recommendation is to use java.util.concurrent.CopyOnWriteArrayList.

How does Vector grow dynamically?

The vector class holds an array of objects to store data named elementData. This array is initialised with an initial capacity of 10. The key point to grasp here is the distinction between the capacity and size of the inner array. Size refers to the number of elements contained within the array, whereas capacity refers to the magnitude of the array elementData.?

When we create a "Vector" object, it creates an internal array "elementData" with a capacity of 10. This is the vector's initial capacity, whereas size is the actual number of elements stored in the vector using the method add. Once you start adding elements, the size increases and reaches capacity. At that point, when the total number of elements exceeded its capacity, the vector increased and doubled the size of the internal array elementData.?Vector makes sure to keep all existing values while increasing the current capacity of the array.?

The issue with vectors is the mechanics of their growth. As you can see, the elementData array grows twice when the threshold is exceeded. As a result, we can see a lot of empty boxes. To trim elementData capacity to its actual size (number of elements inside it), there is a method called trimToSize.

What is ArrayList?

Since Java 1.2, the ArrayList class (package java.util.ArrayList) has been introduced as a resizable array, just like a vector. ArrayList implements all operational list methods to store any type of data insertion, including null values. Except for how it grows internally and its non-synchronized nature, this class is roughly equivalent to the vector data structure.?

ArrayList, unlike vector, is not synchronized. When multiple threads access an ArrayList instance concurrently and one or more threads are modifying it, dirty reads and writes problems, or race conditions, can occur. ArrayList, unlike vector, is not synchronized. When multiple threads access an ArrayList instance concurrently and one or more of them are modifying it, dirty reads and writes problems or race conditions, can occur. If multithreading is a concern, then we can synchronize an array list with Collections.synchronizedList, which will convert the current list to synchronized, which will allow only one thread to perform an operation at a time. As mentioned above in the vector section if a thread-safe, highly concurrent implementation is coveted, then the recommendation is to use java.util.concurrent.CopyOnWriteArrayList.

ArrayList was introduced in Java Development Kit 1.2 as part of the Java collection framework. It extends AbstractList and implements List, RandomAccess, Cloneable and Serializable just like Vector.

How does ArrayList grow dynamically?

You can skip the first paragraph as it is pretty much the same as we discussed in Vector,

TL;DR The ArrayList class holds an array of objects to store data named elementData. This array is initialised with an initial capacity of 10. The key point to grasp here is the distinction between the capacity and size of the inner array. Size refers to the number of elements contained within the array, whereas capacity refers to the magnitude of the array elementData.?When we create an "ArrayList" object, it creates an internal array "elementData" with a capacity of 10. This is the ArrayList's initial capacity, whereas size is the actual number of elements stored in the vector using the method add.

Important: Once you start adding elements, the size increases and reaches capacity. At that point, when the total number of elements exceeded its capacity, the ArrayList increased by 50% of its actual size of the internal array elementData.?ArrayList make sure to keep all existing values while increasing the current capacity of the array.?

Vector vs ArrayList

Let's go over some of the key differences and similarities between the two data structures so you know which one to use when.

• Vector is legacy and was introduced in Java 1.0, while ArrayList is not legacy.
• After the release of the collection framework, both classes implement the same behaviour due to extending the same classes and implementing the same interfaces.
• Vector is synchronized while ArrayList is not synchronized. Due to Synchronization supported in Vector, it can be used with multiple threads. ArrayList can also be converted to synchronized by using Collections.synchronizedList but if thread-safety concurrent behaviour is a major concern we can use java.util.concurrent.CopyOnWriteArrayList was introduced as part of Java 1.5.
• Due to synchronization Vector performance is slow as compared to ArrayList.
• ArrayList growth is more intelligent than vector as it increased its internal capacity by 50% while vector does 100%.
• In both data structures most of the operations like get, size, isEmpty, set etc run in constant time. The add operation runs in amortized constant time, which means adding n elements requires O(n) time. Adding a single element is O(1) but imagine we are adding N number of elements and during that data structure will resize a couple of times (as it is not that often).
• Vector is traversed by both Enumerator and Iterator because it was introduced in Java 1.0 and at that time it only supported Enumerator but after it upgraded and became part of Java collections as part of JDK 1.2 it started supporting Iterator as well. As the Iterator is a?Fail-Fast and the enumerator is a Fail-Safe vector supports both behaviours, while ArrayList only traverses by Iterator which is Fail-Fast.

Conclusion

This brings us to the conclusion of this article, where we will learn about Vector and ArrayList data structures. How do Vector and ArrayList store data and grow dynamically, and what are the time complexities of both data structures? We also look at the fundamental differences and similarities between ArrayList and Vector and dive into supported traversal interfaces both support. I hope you understand those concepts and have a good reading day!