List interface and its implementations

The List interface models an ordered collection of objects. It returns the objects to you in the order in which you added them to a List. It allows you to store duplicate elements.

In a List, you can control the position where you want to store an element. This is the reason that this interface defines overloaded methods to add, remove, and retrieve elements at a particular position. Apart from including the iterator method to return an Iterator, List also includes a method to return a ListIterator, to iterate the complete list or a part of it.

In this section, I’ll cover only one of the two implementations of interface List: ArrayList. Because the other List implementation, LinkedList, also implements the interface Deque, I’ll cover it in the next section on Deque.

ARRAYLIST CLASS:

An ArrayList is a resizable array implementation of the List interface. It’s interest- ing to note that internally, an ArrayList uses an array to store its elements. An Array- List defines multiple constructors:

Class ManipulateArrayList creates an ArrayList and manipulates it using methods add(), remove(), set(), and contains():

It’s interesting to note that an ArrayList uses the size variable to keep track of the number of elements inserted in it. By default, an element is added to the first available position in the array. But if you add an element to an earlier location, the rest of the list elements are shifted to the right. Similarly, if you remove an element that isn’t the last element in the list, ArrayList shifts the elements to the left. As you add more elements to an ArrayList that can’t be added to its existing array, it allocates a bigger array and copies its elements to the new array. An ArrayList maintains a record of its size, so that you can’t add elements at arbitrary locations.

Figure below shows how elements are added, removed, and modified in an ArrayList.

An ArrayList offers a resizable array. Internally, it uses an array to store its elements. It manipulates this array to add, remove, or modify ArrayList elements. The elements of the internal array are moved to the left or right, when elements are removed from or added to it, respectively. If the ArrayList exceeds the existing size of the internal array, its elements are copied to a new array with increased size.

What happens when you ask an ArrayList to remove an object by using method remove(Object obj)? It sequentially searches the ArrayList to find the target object. Have you ever wondered how the class ArrayList determines the equality of objects? In the preceding example, you’re trying to remove a String object with the value Harry. ArrayList compares the target object and the object that it stores by using method equals(). If a match is found, the ArrayList removes the first occurrence of the String value Harry.

To remove an element, an ArrayList first searches through its elements to find an element that can be considered equal to the target element. It does so by calling method equals() on the target object and its own objects, one by one. If a matching element is found, remove(Object) removes the first occurrence of the match found.

IMPORTANCE OF THE EQUALS METHOD IN FINDING AND REMOVING VALUES FROM AN ARRAYLIST :

The example code in the preceding section uses String instances, which override method equals(). Let’s work with an example in which the class, whose objects are stored by an ArrayList, doesn’t override method equals().

In the following example, class UsingEquals stores Emp instances in an ArrayList. Class UsingEquals tries to remove an Emp object from its ArrayList by using method remove(). Do you think it’ll work? Here’s the code:

In the preceding example, no Emp objects were removed from list. This is because Emp doesn’t define method equals(), so the default implementation of method equals() of class Object is used. As you already (should) know, this compares the object references for equality and not the object contents. So method remove() fails to find a matching object referred by emp in list. The answer is to override method equals() in class Emp (modified code in bold):

With the preceding definition of class Emp, class UsingEquals will be able to find and remove a matching value for the Emp instance referred by emp.