Collection2

1. ArrayList VS LinkedList

	ArrayList	LinkedList
Structure	ArrayList is an index based data structure where each element is associated with an index.	Elements in the LinkedList are called as nodes, where each node consists of three things – Reference to previous element, Actual value of the element and Reference to next element.
Insertion And Removal	Insertions and Removals in the middle of the ArrayList are very slow. Because after each insertion and removal, elements need to be shifted.	Insertions and Removals from any position in the LinkedList are faster than the ArrayList. Because there is no need to shift the elements after every insertion and removal. Only references of previous and next elements are to be changed.
	Insertion and removal operations in ArrayList are of order O(n).	Insertion and removal in LinkedList are of order O(1).
Retrieval(Searching or getting an element)	Retrieval of elements in the ArrayList is faster than the LinkedList . Because all elements in ArrayList are index based.	Retrieval of elements in LinkedList is very slow compared to ArrayList. Because to retrieve an element, you have to traverse from beginning or end (Whichever is closer to that element) to reach that element.
	Retrieval operation in ArrayList is of order of O(1).	Retrieval operation in LinkedList is of order of O(n).
Random Access	ArrayList is of type Random Access. i.e elements can be accessed randomly.	LinkedList is not of type Random Access. i.e elements can not be accessed randomly. you have to traverse from beginning or end to reach a particular element.
Usage	ArrayList can not be used as a Stack or Queue.	LinkedList, once defined, can be used as ArrayList, Stack, Queue, Singly Linked List and Doubly Linked List.
Memory Occupation	ArrayList requires less memory compared to LinkedList. Because ArrayList holds only actual data and it’s index.	LinkedList requires more memory compared to ArrayList. Because, each node in LinkedList holds data and reference to next and previous elements.
When To Use	If your application does more retrieval than the insertions and deletions, then use ArrayList.	If your application does more insertions and deletions than the retrieval, then use LinkedList.

2. Java Collection Usage

https://stackoverflow.com/questions/48442/rule-of-thumb-for-choosing-an-implementation-of-a-java-collection

3. Collection Implementations

Interface	Hash Table	Resizable Array	Balanced Tree	Linked List	Hash Table + Linked List
Set	HashSet		TreeSet		LinkedHashSet
List		ArrayList		LinkedList
Deque		ArrayDeque		LinkedList
Map	HashMap		TreeMap		LinkedHashMap

4. Vector VS ArrayList VS LinkedList

ArrayList is implemented as a resizable array. As more elements are added to ArrayList, its size is increased dynamically. It's elements can be accessed directly by using the get and set methods, since ArrayList is essentially an array. LinkedList is implemented as a double linked list. Its performance on add and remove is better than Arraylist, but worse on get and set methods. Vector is similar with ArrayList, but it is synchronized. ArrayList is a better choice if your program is thread-safe. Vector and ArrayList require space as more elements are added. Vector each time doubles its array size, while ArrayList grow 50% of its size each time. LinkedList, however, also implements Queue interface which adds more methods than ArrayList and Vector, such as offer(), peek(), poll(), etc. Note: The default initial capacity of an ArrayList is pretty small. It is a good habit to construct the ArrayList with a higher initial capacity. This can avoid the resizing cost.

Queue methods:

• peek()

• element()

• poll()

• remove()

• The peek() method retrieves the value of the first element of the queue without removing it from the queue. For each invocation of the method we always get the same value and its execution does not affect the size of the queue. If the queue is empty the peek() method returns null.

• The element() method behaves like peek(), so it again retrieves the value of the first element without removing it. Unlike peek ), however, if the list is empty element() throws a NoSuchElementException

• The poll() method retrieves the value of the first element of the queue by removing it from the queue. At each invocation it removes the first element of the list and if the list is already empty it returns null but does not throw any exception

• The remove() method behaves as the poll() method, so it removes the first element of the list and if the list is empty it throws a NoSuchElementException

4.1 Vector

Vector is almost identical to ArrayList, and the difference is that Vector is synchronized. Because of this, it has an overhead than ArrayList. Normally, most Java programmers use ArrayList instead of Vector because they can synchronize explicitly by themselves.

4.2 Performance of ArrayList VS LinkedList

The difference of their performance is obvious. LinkedList is faster in add and remove, but slower in get. Based on the complexity table and testing results, we can figure out when to use ArrayList or LinkedList.

In brief, LinkedList should be preferred if:

• there are no large number of random access of element

• there are a large number of add/remove operations

5. ArrayList VS Vector

1. Synchronization : Vector is synchronized that means at a time only one thread can access the code while arrayList is not synchronized that means multiple threads can work on arrayList at same time. For example, if one thread is performing add operation, then there can be another thread performing remove operation in multithreading environment. If multiple threads access arrayList concurrently then we must synchronize the block of the code which modifies the list either structurally or simple modifies element. Structural modification means addition or deletion of element(s) from the list. Setting the value of an existing element is not a structural modification.

2. Performance: ArrayList is faster as it is non-synchronized while vector operations give slow performance as they are synchronized(thread-safe). If one thread works on vector has acquired lock on it which makes other thread will has to wait till lock is released.

3. Data Growth: ArrayList and Vector both grow and shrink dynamically to maintain optimal use of storage. But the way they resized is different. ArrayList increments 50% of current array size if number of elements exceeds its capacity while vector increments 100% means doubles the current array size.

4. Traversal: Vector can use both Enumeration and Iterator for traversing over elements of vector while ArrayList can only use

   Iterator for traversing.

5.1 How to choose between ArrayList and Vector?

• ArrayList is unsynchronized and not thread safe whereas Vecrors are. Only one thread can call methods on a Vector at a time which is a slight overhead but helpful when safety is a concern. Therefore, in a single threaded case arrayList is an obvious choice but in multithreading vectors can be preferred.

• If we don’t know how much data we are going to have, but know the rate at which it grows, Vector has advantage since we can set the increment value in vectors.

• ArrayList is newer and faster. If we don’t have any explicit requirements for using any of them – we use ArrayList over vector.