Lists are the most versatile and most frequently used data structure in Java programming. In some sense Lists are to Java what arrays are to C programming language. Since Lists are so very important we will spend this and the next lesson on them studying their concrete implementations and important methods. Later we will see how to roll out our own hand made Lists.
Lists represents an ordered sequence of objects. A List allows duplicates, therefore you can insert the same element in a List as many times as you want. Lists are indexed data structures meaning you can access the elements of a List using indices. This property directly follows from the fact that Lists are ordered and every element has a unique numerical position.
Concrete Lists in Collections Framework
Java Collections Framework provides the following ready to use List implementations –
- ArrayList
- LinkedList
- Vector
There are a few thread safe implementations of List such as CopyOnWriteArrayList in the java.util.concurrent package. We will be covering those in lessons on multi-threading.
ArrayList
ArrayList is one of the most popular data structures among Java programmers. Its resizable nature and array like properties make it ideal in a wide range of applications.
ArrayList is a List and also implements the Iterator interface. The Iterator interface has a single factory method called iterator() which is used to retrieve an iterator.
The following properties of ArrayList make it so versatile –
- ArrayList can theoretically contain infinite number of elements. This comes directly from the fact that ArrayList implements the List ADT. Whereas an array declaration requires you declare the size as well, a List can be declared without explicitly specifying the size. Moreover, the ArrayList will grow and shrink without any intervention from the programmer. This is extremely useful in modelling real world problems because the size of the ArrayList can dynamically adjust to the scenario.
- ArrayList is an ordered collection. This means that elements of ArrayList have index numbers that are indicative of order of element insertion.
- ArrayList can contain null as well as duplicate elements.
- ArrayList uses arrays in their underlying implementation. Therefore, they allow random access to elements using index number and accessing an element is always Ο(1) operation.
Deleting an element in an ArrayList is a linear i.e. Ο(n) in time operation. This is because index numbers of all elements past the element that is being deleted need to be adjusted. The best practice is to put a marker element such as null in place of deleted element and thereby avoid moving a lot of element.
LinkedList
LinkedList is the less popular first cousin of ArrayList. Both LinkedList and ArrayList are Lists and therefore have a lot of common traits. Both are ordered collections, permit duplicates and nulls, and have no size limits.
Nevertheless, they differ in one critical aspect. LinkedList is a doubly linked list where each element is a chunk of memory. ArrayList uses array for implementation. This results in different element access time characteristics for LinkedList and ArrayList. It is not possible to have random access with LinkedList.Deleting an element in the LinkedList is a constant time operation. ArrayList, on the other hand, allows random access but it takes linear i.e. O(n) time to delete an element.
LinkedList also implements the Deque interface so we can access LinkedList from either end. Since a LinkedList is Deque it is trivial to use it as a Stack or Queue. In fact, in real world problem there are two (and possibly only two) popular use cases of LinkedList –
- For implementing Deque, Stack or Queue
- For implementing Lists where manipulations (adding/removing middle element) is more common than element addition and traversal
Vector
Vectors are legacy implementation which were used prior to Java 2. They have been totally replaced by ArrayList and LinkedList and there should be no excuse for using Vector in a modern day code.
Differences Between ArrayList and LinkedList
The table below summarizes important differences between ArrayList and LinkedList –
| ArrayList | LinkedList |
|---|---|
| ArrayLists are better suited where reads and writes are more numerous than deletions and additions in the middle. | LinkedLists are better suited when frequent adding or removal of elements inside the List. |
| ArrayList can act only a List. | LinkedList can act as List, Queue, Deque, Stack and Priority Queue. |
| Random access of elements is the most important iteration feature. | Ability to efficiently traverse the list in reverse order. |
| Default constructor creates an ArrayList (even in Java 8) with initial capicity 10. | Default constructor creates a LinkedList with initial capicity 0. |
| An ArrayList upon resizing grows up to 1.5 of its current size through copying of underlying array. | A LinkedList grows one element at a time and is never copied entirely behind the scenes. |
Differences Between ArrayList and Vector
The table below summarizes important differences between ArrayList and Vector –
| ArrayList | Vector |
|---|---|
| ArrayList does not have any locking mechanism and is not intended to be used in multi threading scenario. | All methods of Vector are synchronized. This creates locking overhead even if your application is single threaded. Moreover, synchronized methods in themselves are not very useful as a combination of synchronized methods is itself not thread safe. |
| When an ArrayList needs to resize it increases its capacity by approximately 50%. | When an Vector needs to resize it increases its capacity by 100%. |
| An ArrayList is fast and is the preferred implementation of List | Vector is obsolete and is much slower. A Vector suffers from overhead of lock maintenance even if you are writing a single threaded application |
| ArrayList implement Iterator interface | Vector implements the legacy Enumeration interface |
Having seen the most important concrete Lists, we will next take a look at the most important methods in the next lesson.