Java / List and its implementations

using the traditional for-loop, we always have the index of the element.

for (int i = 0; i < myList.size(); i ++) {
    // i hold the index.
    // myList.get(i) retrives the element.
}

In case of enhanced/condensed for loop, we need to manually add index variable and increment on each iteration as shown below.

int index = 0;
for(String item : itemsList) {
	index++;
    System.out.println("The current index is: " + index);
}

The enhanced for-loop does not support index directly as it could iterate through any collection implementing Iterable interface and the collection may not even have any index.

An array and an array list share the below properties that make its behavior similar in Java.

• Both array and ArrayList allow duplicate elements.
• Both are unordered lists.
• Both uses index to refer and retrieve its elements and index starts with 0.
• Both supports null values.
• Both maintain the order of insertion.

Using Collections.reverse (list) an ArrayList elements can be reversed. The method does not return a reversed list instead it reverses the same list.

ArrayList aList = new ArrayList();
//Add elements to ArrayList object
aList.add("1");
aList.add("2");
aList.add("3");
aList.add("4");
aList.add("5");
Collections.reverse(aList);
System.out.println("After Reversing the ArrayList Elements are: " + aList);

Using HashSet implementation which doesn't allow duplicates can be used to identify the elements that are duplicate at the List. Set has a method add() that return boolean value true if the element already exists else returns false which can be used as a tracker to find the duplicate elements as shown below.

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DuplicateElements {

public static void main(String[] args) {
	String[] stringList = { "Javapedia.net", "Javapedia.net", "minim.tk", "weatherman.com" };
	List<String> listwithDuplicates = Arrays.asList(stringList);
	final Set<String> tempSet = new HashSet<>();
	final Set<String> duplicateElements = new HashSet<>();

	for (String element : listwithDuplicates) {
		if (!tempSet.add(element)) {
			duplicateElements.add(element);
		}
	}
	System.out.println(duplicateElements);
}

}

removeAll method removes the collection elements (List, Set, Vector also Collection) that exist in the specified collection of elements.

public class ArrayListEx {

	public static void main(String[] args) {
		List<String> myList = new ArrayList<>();
		myList.add("A");
		myList.add("B");
		myList.add("C");
		myList.add("D");
		List<String> mySubList = myList.subList(2, 3);
		System.out.println("List content is " + myList);
		myList.removeAll(mySubList);
		System.out.println("List content  after remove is" + myList);

	}

}

Output:
List content is [A, B, C, D]
List content  after remove is [A, B, D]

retainAll method retains the collection elements (List, Set, Vector also Collection) that exist in the specified collection of elements and it removes all other elements.

public class ArrayListEx {

	public static void main(String[] args) {
		List<String> myList = new ArrayList<>();
		myList.add("A"); myList.add("B");myList.add("C");myList.add("D");
		
		List<String> mySubList = myList.subList(2, 3);
		System.out.println("List content is " + myList);
		myList.retainAll(mySubList);
		System.out.println("List content  after retaining is " + myList);

	}

}

Output:
List content is [A, B, C, D]
List content  after retaining is [C]

using clear() method, we can remove all the elements from an ArrayList in Java.

Another way is passing the same ArrayList reference as an argument to the removeAll() method removes all the elements.

ArrayList.clear() will traverse the underlying Array and set each entry to null that eventually removes all the elements of ArrayLIst.

removeAll(collection) traverse through the ArrayList comparing for collection and remove the element, if it exists.

ArrayList.clear() is comparatively faster as it does not perform any comparison.

O(1) accurately describes inserting at the end of the array. However, if you're inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n) for arrays.

For linked list, you have to traverse the list to do middle insertions, so that's O(n). You don't have to shift elements down though.

Binary search.

CopyOnWriteArrayList is a thread-safe collection while ArrayList is not thread-safe.

Iterator of ArrayList is fail-fast and throw ConcurrentModificationException once detect any modification in List once iteration begins but Iterator of CopyOnWriteArrayList is fail-safe and doesn't throw ConcurrentModificationException.

Iterator of CopyOnWriteArrayList doesn't support remove operation while ArrayList Iterator supports remove() operation.

CopyOnWriteArrayList implements List interface but its a thread-safe collection.

CopyOnWriteArrayList creates copy of underlying ArrayList with every mutation operation e.g. add or set. Normally CopyOnWriteArrayList is very expensive because it involves costly Array copy with every write operation but its very efficient if you have a List where Iteration outnumber mutation.

RandomAccess is a marker interface used by List implementations to indicate that they support fast (constant time) random access.

The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

Using Collections.unmodifiableList(list) we can create an immutable list in Java.

UnsupportedOperationException is thrown when we try to modify or add element in an unmodifiableList.

The method set(int index, Element E) updates the element of specified index with the given element E and also returns the element E previously stored at this index.

ArrayList is faster than Vector since ArrayList is not synchronized while Vector is. Synchronization usually affects performance.

The order of Stream.forEach is random while Iterable.forEach is always executed in the iteration order of the Iterable.

If Iterable.forEach is iterating over a synchronized collection, Iterable.forEach takes the collection's lock once and holds it across all the calls to the action method. The Stream.forEach call uses the collection's spliterator, which does not lock.

The action specified in Stream.forEach is required to be non-interfering while Iterable.forEach is allowed to set values in the underlying ArrayList without problems.

A new array is created and the contents of the old one are copied over.

While an element is being added to the ArrayList, JVM checks if ArrayList has adequate space available by calling ensureCapacity method. If a space exists, it adds the element to the ArrayList otherwise Array resizing happens.

During resizing process, a new array of a greater size is created, the old array is copied to new array using Arrays.copyOf and the new array is assigned to the existing array.

Below is the formula used to resize the array.

int newCapacity= (oldCapacity * 3)/2 +1;

When we use ArrayList() constructor we get a ArrayList with Size=10. On adding 11th element in the list new Arraylist is created inside ensureCapacity() method and existing array is copied.

The growing factor of ArrayList is 1.5 times when resized.

The growing factor is 1.5 while hashmap is 2,

If the current capacity of ArrayList is 10, then the new capacity would be 16.

The add operation runs in amortized constant time, meaning that adding n elements requires O(n) time. All of the other operations run in linear time.

LinkedList does NOT have initial capacity. It is initiated to empty.

The list items can be iterated only in forward direction.

Once the end of the list is reached, we cannot reiterate and need to create new iterator.