Java Array List is possibly the most commonly used data structure from the Java Collections framework. More often than not, this is the first option we try to explore when trying to store a list of items in any program.
In this post, we will discuss the properties of Java Array List, its common use-cases and the various advantages and disadvantages that come along with it.
1 – Usage
Java Array List is part of the core Java libraries. As a result, we don’t need to setup any additional libraries to start using it. All we have to do is import the package in our program as below:
List<String> list = new ArrayList<>();
Being a list, it is an ordered sequence of values and it is perfectly possible for a particular value to be present more than one time.
Array List extend the List interface and it is backed by an array. This array is able to dynamically grow and shrink as we add/remove elements. We can also access elements using by their indexes.
Some important properties of an array list are as follows:
- Random access in array list has O(1) time complexity. This is not something we could achieve using Java Linked List.
- Adding an element has an amortized constant time of O(1). This is because when the array becomes full, it needs to be resized and such an operation involves copying the elements from the existing array to a new array. The copying operation has a linear time complexity of O(n).
- Inserting and deleting an element has a linear time complexity i.e. O(n).
- Searching operation on an unsorted array list has linear time complexity. However, if the list is sorted, the time complexity is O(log n) because in such a case, we can use binary search.
2 – Creating a Java Array List
Array List has several constructors. We will look at them in this section.
Important point to understand is that Array List is a generic class. In other words, we can parameterize it with any data type and the compiler will make sure that we can only use that data type with the array list instance. So, we cannot put an Integer into a String Array List. This also helps prevent the need for casting data types when retrieving from the list.
Another point is to use the generic interface List while instantiating an Array List. This decouples our variable from a particular implementation.
2.1 – Default Constructor
The most common approach is to use the default constructor as below.
List<String> list = new ArrayList<>();
This creates an empty Array List.
2.2 – Constructor with Initial Capacity
The constructor can also have an initial capacity or initial size of the Array List as below:
List<String> list = new ArrayList<>(10);
The advantage of this approach is that we can avoid unnecessary resizing of the array which is costly operation.
2.3 – Constructor Accepting Collection of Objects
Since List also extends the Collection interface, we can also instantiate an Array List with another Collection. See below example:
Collection<Integer> numbers
= IntStream.range(0, 10).boxed().collect(toSet());
List<Integer> list = new ArrayList<>(numbers);
3 – Add Elements to Array List
We can add elements to Array List at the end or at specific position.
List<Integer> list = new ArrayList<>();
list.add(4);
list.add(5);
list.add(1, 6);
In the above example, the third addition is at index 1. Note that inserting element at a particular position has a worst-case time complexity of O(n) since we have to move the elements by the one position to accommodate the new element.
4 – Iterating Over a Java Array List
It is a common use-case to iterate over all the elements in a list to perform some action. There are two types of iterators available – the Iterator interface and the ListIterator. The difference between them is that the Iterator interface traverses the list in one direction while ListIterator can traverse in both directions.
Below is an example of the ListIterator to traverse the array list backwards. We get a ListIterator pointing to the end of the array list and then use the hasPrevious() method to traverse backwards.
List<Integer> list = new ArrayList<>(
IntStream.range(0, 10).boxed().collect(toCollection(ArrayList::new))
);
ListIterator<Integer> it = list.listIterator(list.size());
List<Integer> result = new ArrayList<>(list.size());
while (it.hasPrevious()) {
result.add(it.previous());
}
5 – Removing an Element
There are a couple of approaches to remove an element.
The first approach is to remove using the index value. We can find an index to the object and then perform the removal using the remove() method.
list.remove(0);
The above statement removes the element at index 0.
Another approach is to use the overloaded method that accepts an object to be removed. This method first searches the object and then removes the first occurrence.
list.remove(Integer.valueOf(1));
In the above example, we want to remove the first occurrence of 1 in the array list. Notice that we have to box the integer value 1 to the Integer data type otherwise it would remove the element at index 1.
With this, we have successfully looked at Java Array List and the various operations. We also created Java Array List and adding, removing and iterating over the list.
If you have any questions or queries, please do mention in the comments section below.
0 Comments