Classes implementing List


Classes implementing List - Pros and Cons

The List 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.

Classes implementing List

These are all of the public classes in Java SE 8 that implement the java.util.List interface:

  • Abstract Classes:
    • AbstractList
    • AbstractSequentialList
  • Concrete Classes:
    • ArrayList
    • AttributeList
    • CopyOnWriteArrayList
    • LinkedList
    • RoleList
    • RoleUnresolvedList
    • Stack
    • Vector

Pros and Cons of each implementation in term of time complexity

ArrayList

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:

  • The add operation runs in amortized constant time, that is, adding n elements requires O(n) time

Removing an element requires O(n) time.

LinkedList

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializabl

LinkedList is implemented by a doubly-linked list a linked data structure that consists of a set of sequentially linked records called nodes.

Iitialize LinkedList of Integer

List<Integer> myList = new LinkedList<Integer>(); // Constructs an empty list.

- PROS:

Adding or removing an element to the front of the list or to the end has constant time.

myList.add(10); // \
myList.add(0,2); // | => constant time => O(1)
myList.remove(); // /

- CONS:

Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Operations such as:

myList.get(10); // \
myList.add(11,25); // | => worst case done in O(n/2)
myList.set(15,35); // /

Finding common elements between 2 lists

Suppose you have two lists: A and B, and you need to find the elements that exist in both lists.

You can do it by just invoking the method List.retainAll().

Example:

public static void main(String[] args) {
    List<Integer> setX = new ArrayList<>();
    List<Integer> setY = new ArrayList<>();
    setX.addAll(Arrays.asList(new Integer[] { 2, 4, 5, 7, 8 }));
    setY.addAll(Arrays.asList(new Integer[] { 1, 5, 6, 8, 9 }));
    System.out.println("X: " + setX);
    System.out.println("Y: " + setY);
    List<Integer> commonElements = new ArrayList<>();
    commonElements.addAll(setX);
    commonElements.retainAll(setY);
    System.out.println("Set X: " + setX);
    System.out.println("Set Y: " + setY);
    System.out.println("Common elements between X and Y: " + commonElements);
}

Basic Programs