The [List](<https://docs.oracle.com/javase/7/docs/api/java/util/List.html>)
interface is implemented by different classes. Each of them has its own way for implementing it with different strategies and providing different pros and cons.
These are all of the public
classes in Java SE 8 that implement the java.util.List
interface:
- AbstractList
- AbstractSequentialList
- ArrayList
- AttributeList
- CopyOnWriteArrayList
- LinkedList
- RoleList
- RoleUnresolvedList
- Stack
- Vector
public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable
ArrayList is a resizable-array implementation of the List interface. Storing the list into an array, ArrayList provides methods (in addition to the methods implementing the List interface) for manipulating the size of the array.
Initialize ArrayList of Integer with size 100
List<Integer> myList = new ArrayList<Integer>(100); // Constructs an empty list with the specified initial capacity.
- PROS:
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. So getting and setting each element of the List has the same time cost:
int e1 = myList.get(0); // \\
int e2 = myList.get(10); // | => All the same constant cost => O(1)
myList.set(2,10); // /
- CONS:
Being implemented with an array (static structure) adding elements over the size of the array has a big cost due to the fact that a new allocation need to be done for all the array. However, from documentation: