14.3 The concrete classes implementing the core interfaces > 14.3.1 List

14.3.1 List

Conceptually a list is a collection of elements where elements are stored in an ordered fashion. In simple words, if you insert an element B after element A, then element A will always appear before element B in the ordered collection. Thus, order is very important for the lists. Usually the order is maintained by keeping an index for each element in the collection. Another important thing about lists is that it allows duplicate elements. For instance, if you entered an element twice in a list, there will be actually two elements entered in the list. Each element will be at a different position depending on the order in which it was entered in the list.

As the lists are ordered, the core interface List defines many index-related methods. For instance, the key methods of List interface include-

get(int index)

indexOf(Object)

set(int index, Object obj)

You can store an object at a specific index using set(int index, Object obj) method or retrieve it from a particular index position using get(int index) method. You can also add an element to a list without specifying index using add(Object obj) method. In that case, the object is appended to the end of the list.

The collection framework provides three main implementer classes of List interface:

1.    ArrayList

2.        Vector

3.        LinkedList

All the implementer classes implement the same List interface. But each one of them internally uses distinct data structures to store the elements. For instance, ArrayList and Vector classes internally use array to store elements whereas LinkedList stores elements in doubly linked list. But all these three List implementers are ordered by index position. They are discussed in the following section.

java.util.ArrayList

This class implements the List interface to store an ordered collection of elements which are accessible by index. You may recall that the built-in arrays in Java (Chapter 7) do precisely the same thing. They too store elements in ordered fashion and provide an indexed access to the elements. Then why do we need this class? The answer lies in the important difference between the built-in arrays and ArrayList class. The built-in arrays are fixed size which means once they are created, they can hold only fixed number of elements. However, the ArrayList objects are resizable which means they can change their size dynamically after they are created. Therefore, you can go on adding elements without worrying about the capacity of the collection. For example, you can create an ArrList of size 2, but add 4 elements in it without any problem.

java.util.ArrayList arrList = new java.util.ArrayList(2);

arrList.add(0,"Mogaly");

arrList.add(1,"Bhalu");

arrList.add(2,"Baghira");

arrList.add(3,"Seeta");

System.out.println(arrList);

This class got its name as ArrayList because it implements the List interface and internally uses a Java array to store the elements. Therefore this class shares the advantages of using arrays for data storage such as it is easier to maintain order among elements and faster to access elements using the index etc. Note that searching a particular element is not very efficient in any list. For example, if we want to search an element, say “Mogaly” in a ArrayList of 100 elements, we need to do a sequential search which means we need to check every element till we find the element “Mogaly”. Thus searching is slower in ArrayList. On the other hand, the random access is faster. It means if you know the index (that is the position of an element in collection), then accessing the element is faster. For instance, if you want to access an element at 50^th index, you can access it very fast by directly specifying the index.

Another major disadvantage when arrays are used for storing elements is at the time of insertion or deletion. The insertion in the middle of array requires moving all the elements past the point of insertion over to make room for the new element. Therefore, insertion takes time, which is proportional to the elements required to move. The same is true about deletion. Thus ArrayList shares almost all advantages and disadvantages of built-in arrays. It also has two characteristics that all lists have, it is ordered and it allows duplicate elements.

java.util.Vector

The Vector class also implements the List interface to store an ordered collection of elements. It represents an array of objects of growable size. A Vector is essentially same as an ArrayList as it also uses a Java array to store the elements. However, there is one major difference between the two. The methods in Vector class are synchronized for thread safety. It means that a Vector object can be shared by multiple threads without compromising the integrity of its contents. The synchronized methods are best if you have a multithreaded application, but they also add a performance overhead. Therefore, you will probably use ArrayList instead of Vector if your application does not need thread safety. Since this class uses a Java array to store the elements internally, it shares the advantages of using arrays for data storage.

java.util.LinkedList

The LinkedList class implements List interface. It internally uses a doubly linked list data structure to store the elements.

In a linked list, you can easily store elements at the beginning as well as at the end of the list. In fact, you can insert element in the middle of the list without any overheads. Insertion at any position in a linked list is a constant time operation, because it only involves changing a fixed number of references. In LinkedList type of list, the elements are doubly linked to one another, hence insertion and deletion at beginning and end is easier. Therefore LinkedList has new methods (beyond what it must implement from the List interface) for adding and removing from the beginning or end, such as addFirst(), removeFirst(), addLast(), removeLast() etc. These operations allow LinkedList to be used as a stack, queue, or deque (double-ended queue).

The major disadvantage is that accessing (getting or storing) an element using index is much slower in LinkedList. The linked lists used in LinkedList are not as good as arrays for random access (that is same as the accessing using index). Another important thing about LinkedList is that its methods are not synchronized. Therefore, the elements in it are not thread-safe. Therefore, concurrent access may result into loss of data integrity.

Table 14.1 compares the three implementations of the List interface. This comparison would be easier to remember when you take into account the underlying data structure used for storing elements.

 Table 14.1 Comparing three implementations of List interface