List

1. What is a List?

Answer: List is an ordered collection which maintains the insertion order.
Insertion order means "List always stores the elements in same order in which you have inserted. Hence Iteration over the list will give you the same order every time."
Example: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class ListExample { public static void main(String[] args) { //1. Instantiated List List<Integer> myList = new ArrayList<Integer>(); //2. Adding elements to List myList.add(1); myList.add(2); myList.add(3); myList.add(4); myList.add(5); //3. Iterating over List Iterator<Integer> iterator = myList.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } } }

No matters how many times you execute above code you will get same order as you have inserted.
Note: List allows duplicate elements. If you insert same element multiple times then list will treat each as an individual entry.

---

2. Explain List class hierarchy?

Answer: List is an interface which has following implementation classes:
1. ArrayList
2. LinkedList
3. CopyOnWriteArrayList
4. Vector.

Fig: List Class Hierarchy.

Note: ArrayList and LinkedList do not support concurrent operation i.e not suitable for multi threaded environment.
Vector and CopyOnWriteArrayList are designed for multi threaded environment.

---

3. What is difference between ArrayList and LinkedList?

Answer: ArrayList and LinkedList both are the implementation of List interface. 
Both of them are the ordered collection and maintain the insertion order. So behavior wise both are same as both of them implement list interface.
The difference between these two is about their underlying data structure and their implementation
1. The underlying data structure for an ArrayList is an "Array", whereas the underlying data structure of a LinkedList is a "Linked List".
2. ArrayList allows random access(ArrayList is indexed based) of elements since it based on Array. whereas LiknedList doesn't allow random access as it is based on Linked List.
As we know Array data structure stores the values in continuous memory blocks. Hence in Array random access is possible. Below diagram shows memory allocation of an Array. Let's assume we want to access 36(element at 4th index), to retrieve 36 CPU will add 4 in base location(100) which will give 104 and that is location of 36. So point is in case of Array data structure there is no need of iterating over each element sequentially to retrieve desire value.

Fig: Array Data Structure

Fig: Linked List Data Structure

But Linked List data structure doesn't store the value in continuous memory block as shown above. Hence to access any value linked list need to follow links(pointer to next memory block).
3. Iterating over ArrayList or reading value from ArrayList is faster compare to LinkedList. As LinkedList doesn't support random access and in case of read operation it follows each and every links(pointer) whereas ArrayList directly jumps to desired value as we discussed above.
4. Insertion/Deletion operation is costlier(slower) in ArrayList compare to LinkedList. Insertion operation in LinkedList follow below steps:
1. Iterates over Linked List to reach desired location where we want to insert new element.
2. Adjust the pointers of two adjacent elements to accommodate new element.
Insertion operation in ArrayList follow below steps.
1. Reach to the desired location.
2. Shift every element to it's right from desired location in order to make room for new element.
3. Insert the element. 
It's clear that In case of Array, it's shifts every element(from index where we want to element) to their right which makes it slower for insertion operation.
So if there is 100 element in ArrayList and you want to insert at say 10th index, It will shift every element from and after 10th index to it's right in order to make space at 10th index.
Whereas LinkedList will just adjust pointers(links) of 10th and 11th index.
Deletion operation also has same behavior only difference is ArrayList shift every element to it's left to fill space of deleted element instead of right shift. LinkedList again adjust links to remove items from list.

---

4. When to use ArrayList over LinkedList or vice versa?

Answer: As we discussed in last question "ArrayList performs better in case of read operation and LinkedList performs better in case of insertion/deletion".
So if your requirement is like that you are going to initialize List at once and there after you are only going to read those value (insertion/deletion operations are very less) through out your code, you should go for ArrayList.
But if your requirement is like that where you will frequently perform insertion/deletion on list through out your code, you should go for LinkedList.

---

5. Discuss time complexity of ArrayList and LinkedList?

Answer: 

Read operation: Time complexity of ArrayList is O(1) whereas for LinkedList it is O(n).

Insert/Delete operation: Time complexity of ArrayList is O(n) whereas for LinkedList it is O(1).