List - sivakrsna/Java-Interview GitHub Wiki

• A List is an ordered collection, also known as a sequence. List is in interface
• Lists may contain duplicate elements.
• They typically allow multiple null elements
• The user of this interface has precise control over where in the list each element is inserted.
• The user can access elements by their integer index (position in the list), and search for elements in the list.
• A Java List collection can only hold objects (not primitive types like int), and it defines a strict contract about how it behaves.With autoboxing in Java the primitive type int will become an Integer when necessary

Autoboxing is the automatic conversion that the Java compiler makes between the primitive types and their corresponding object wrapper classes.

List listOfStrings = new ArrayList(); List listOfPersons = new ArrayList();

1. ArrayList
2. LinkedList

• Resizable-array implementation of the List interface
• Allows all elements, including null
• The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.
• Adding n elements requires O(n) time
• It can take advantage of System.arraycopy when it has to move multiple elements at the same time.
• This implementation is not synchronized

List list = Collections.synchronizedList(new ArrayList(...));

• Fail-fast iterators throw ConcurrentModificationException
• This class is roughly equivalent to Vector, except that it is unsynchronized

• If you frequently add elements to the beginning of the List or iterate over the List to delete elements from its interior, you should consider using LinkedList
• You pay a big price in performance. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList.

• Doubly-linked list implementation of the List and Deque interfaces.
• Permits all elements (including null).
• This implementation is not synchronized.

List list = Collections.synchronizedList(new LinkedList(...));

• Fail-fast iterators throw ConcurrentModificationException on a best-effort basis.

1. ArrayList internally uses dynamic array to store the elements. LinkedList internally uses doubly linked list to store the elements.
2. Manipulation with ArrayList is slow because it internally uses array. If any element is removed from the array, all the bits are shifted in memory. Manipulation with LinkedList is faster than ArrayList because it uses doubly linked list so no bit shifting is required in memory.
3. ArrayList class can act as a list only because it implements List only. LinkedList class can act as a list and queue both because it implements List and Deque interfaces.
4. ArrayList is better for storing and accessing data. LinkedList is better for manipulating data.

1. CopyOnWriteArrayList

• It is a List implementation backed up by a copy-on-write array.
• A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.
• No synchronization is necessary, even during iteration, and iterators are guaranteed never to throw ConcurrentModificationException.
• All elements are permitted, including null.

"Copy on write" means more or less what it sounds like: everyone has a single shared copy of the same data until it's written, and then a copy is made. Usually, copy-on-write is used to resolve concurrency sorts of problems. In ZFS, for example, data blocks on disk are allocated copy-on-write; as long as there are no changes, you keep the original blocks; a change changed only the affected blocks. This means the minimum number of new blocks are allocated.

These changes are also usually implemented to be transactional, ie, they have the ACID properties. This eliminates some concurrency issues, because then you're guaranteed that all updates are atomic.