Adding Elements to Array List Shifts The Index
Java

ArrayList – Java Collection

1. ArrayList – Java Collection

ArrayList is the most often used collection object in Java. Before we learn about the ArrayList, first we will have a basic idea about the Java’s collection.

Java provides Collection Frame-Work for storing and reclaiming the objects. In this Collection Frame-Work group of classes and interfaces are packed to act on the group of objects. Arrays are fixed in size. Whereas collection grows when we add objects to it. Collection classes implement the set of interfaces and there by giving the set of functionalities. Unlike arrays, collection can store only objects and to store Std. types we should keep them as objects via Boxing concept.

2. Collection Interface

Collection interface is the root interface for the classes in the collection Frame-Work. Some crucial methods given by this interface is below:

Collection Interface Method & Description
boolean add(E e) – Adds Element E to the Collection.
boolean remove(E e) – Removes an Element E from the Collection.
void clear() – Removes all the elements. Keeps the Collection Empty.
boolean isEmpty() – Tells collection is empty or not.
int size() – Returns number of elements in the Collection.
boolean contains(Object o) – Tells Object o is part of Collection or not
Iterator iterator – Returns an iterator to iterate over Collection of Elements E
Table 1: Java Collection Interface Methods

3. The List Interface

The ArrayList class implements the List interface. The List interface deals with keeping the objects in adjacent memory location. These packed memory cells allow us to refer an object by its index position. Like arrays, the List interface also support index-based pickup of an entry and index 0 points out the first item in the collection.

The List interface allows duplicate values which can hold null values as well. ArrayList and LinkedList in the Java Collections Frame-Work are a good example for List interface classes.

4. ArrayList from java.util Package

The ArrayList implements List interface. The class holds an array and offers List behaviour on it. You can refer Table 1 to know the method of the ArrayList.

5. Add & Remove Elements From ArrayList

We know ArrayList uses the array as its data structure and array keeps each element next to each other. This makes adding an extra element with an overhead. This overhead is directly proportional to the number of elements present in the array. Let us say we have an array with four elements:

Now, we will try to add an element C1 after the element E2 and learn how it adds the overhead. Have a look at the below picture:

Adding Elements to Array List Shifts The Index
Adding Elements to Array List Shifts The Index

In the first part, we see space is allotted next to the element E2. This is because arrays keep its members in the continues memory location. The second part shows, the index numbers 2 and 3 are wrong after setting up the extra element. The third part of the picture shows how collection framework (ArrayList) alters the index location to keep contiguous memory region referencing. This re-indexing is one of the overhead when adding the elements. Now, let us think about one more big overhead!

In the first part of the picture, we also see copying the object from the old location to the new location. Since C1 needs E3’s location, Java will move E3 towards the right. But there is already an element E4 and that also needs to be moved towards the right. This way Java shifts all the element after C1 to the memory location on the right. This copy is a costly operation. After this index re-numbering happens.

Even though adding the items are an overhead in ArrayList, the retrieval by index location is faster. Since the element in the memory is continuous and same size, the indexing will help in picking an item in one go just by counting the offset from the index 0.

6. Product Class

First, we will create a class called Product. Next, we store this product class in the ArrayList Collection and use ArrayList to test its various functions. This will help in learning how ArrayList stores objects in it at runtime.

6.1 Product Class Constructor

The class contains two members to store ID of the Product and Name of the Product. Its constructor initializes these members. Code is below:

6.2 ToString Override

We override the toString method to represent this class in string format. Here, we append a colon between product id and product name. Code is below:

6.3 Getters and Setters

The below methods will read and write values to the internal member variables. The code is below:

7. ArrayList of Products

The ArrayListTest class will form an ArrayList Java Collection object and then add product objects into it. This class also tests various other member functions given by the ArrayList class.

7.1 Add Elements to ArrayList

In the below code, first we create the ArrayList and store that in a reference called Products. Then we create some sample products and add it to the Products collection. Below is the code which add elements:

7.2 Read Elements from the Java ArrayList

We can read each product by specifying the index location. In the below code, we use the ‘For each loop’ to read each product from the ArrayList, Products. Also note, we are supplying the Product instance to the print line statement. The code will invoke the toString override and prints the product information in the console output window.

The above custom function is called by main() method of the ArrayListTest class:

7.3 Remove Method

The remove method of the ArrayList class removes the element from the ArrayList. In the below code, we pass the reference to the object. Java’s ArrayList after making the comparison, removes the element. Below the code snippet for remove action:

7.4 Contains Method

The contains method will check a specific product exists in the ArrayList or Not.  Java Collection classes do not know how to compare two elements. So we have to educate them. In our case, we should tell ArrayList how to compare two products. We do that later.

The below code checks the product existence in the array list. When we call the contains method for the first time, we passed the existing reference to the product class. Next, we created a Product class instance and passed that to the contains method for testing.

In the first case, p4 reference and element added to the ArrayList both points to same object. So, the contains method returns true quickly. Because, the products must be same as they point to same memory location. In the second case, we create a product and use the contains method. Since memory locations are different, this will call the equal override to know how to compare two products. We will override equals method later in this article for this method to work.

7.5 Clear Method

The clear method will remove all the elements from the ArrayList. After the clear method, the call to the isEmpty() method will return true, as ArrayList does not have any element it. Below is the code to test clear method of the Java’s ArrayList:

8. Override hashCode & equals method

Java recommends overriding the hashCode method whenever one overrides the equals method. The equals method tells how to compare two objects. In our case, in the equals override, we tell two products are equal when the product IDs match. In the below code, hashCode override uses only ID as we write equals method to use only the ID. We will learn more about hash code later in a separate collection class.

The collection class invokes the equals method when it needs to compare two objects. For example, the contains method of ArrayList now know how to compare two Products. It can provide a correct reply to the contains method now just by comparing the ID only. The code is below.

Watch Java ArrayList as Video

Code Reference

Product.java
ArrayListTest.java

Do you like this Example? Please comment about it for others!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.