Vector vs ArrayList vs LinkedList

• Comparison

Features	Vector	ArrayList	LinkedList
Data structure	Growable array	Dynamic array	Doubly linked list
Increment size	100%	50%	No initial size
Traverse	Uses enumeration	Uses iterator	Uses iterator
Accessibility	Random and fast	Random and fast	Sequential and slow
Order	Insertion order	Insertion order	Insertion order
Duplicates	Allowed	Allowed	Allowed
Insert / Delete	Slow	Slow	Fast
Synchronized	Yes	No	No
Null values	Allowed	Allowed	Allowed

• Time Complexity

	Add	Remove	Get	Contains	Data  Structure
ArrayList	O(1)	O(n)	O(1)	O(n)	Array
LinkedList	O(1)	O(1)	O(n)	O(n)	Linked List

 

ArrayList

1. Implements List -> Collection

2. Insertion order preserved, Allows: Duplicates, Heterogeneous objects & null

3. Default capacity or size is 10, which subsequently increases with formula as 

New Capacity = (Current Capacity * 1.5)+1

4. Constructors: 

1. Default: Creates with size = 10

2. int initialCapacity = Creates with predefined size = initialCapacity

3. Collections C = convert any collection to ArrayList

5. Highly recommended when there are frequent retrieval operations

6. Not recommended when there are frequent random inserts or deletes as it needs
   rearranging the indexes

7. To get synchronized ArrayList following can be done

List nonSyncList = new ArrayList();

List syncList = Collections.synchronizedList(nonSyncList);

8. Similarly, Collections class also provides synchronizedSet & synchronizedMap
   methods, to get a synchronized Set or Map

LinkedList

1. Implements List -> Collection

2. Insertion order preserved, Allows: Duplicates, Heterogeneous objects & null

3. By default LinkedList creates Empty list, memory allocation is done at runtime

4. Constructors

1. Default

2. Collections C = convert any collection to LinkedList

5. Highly recommended when there are frequent random insert or deletes

6. Not recommended when there are frequent retrieval operations as it needs
   rearranging the indexes

7. LinkedList provides a few methods like addFirst, addLast, removeFirst, removeLast,
   getFirst & getLast to support Stack & Queue based implementation using LinkedList

8. Version 1.5 onwards LinkedList also implements Queue interface, such LinkedList
   implementation will always follow FIFO order

Vector

1. Implements List -> Collection

2. It is similar to ArrayList, except Vector is synchronized i.e. Thread safe

3. Insertion order preserved, Allows: Duplicates, Heterogeneous objects & null

4. Default capacity or size is 10, which subsequently doubles

5. So ArrayList is faster than Vector

6. Constructors

1. Default

2. int initialCapacity = Creates with predefined size = initialCapacity

3. int initialCapacity, int incrementalCapacity = Creates with predefined
   size = initialCapacity and grows with incrementalCapacity (instead of double)

4. Collections C = convert any collection to Vector

CopyOnWriteArrayList

1. ThreadSafe version of ArrayList

2. Any number of threads can perform read operations

3. For update/write a clone (copy) of List will be created in which write/updates operations
   will be performed

4. JVM will internally take care of synching these clone copies with list

5. NOT recommended when there are large number of write/update operations

6. Iterator of CopyOnWriteArraList cannot remove the objects, else
   UnsupportedOperationException

7. Constructors

1. Default

2. Collection c

3. Object []

8. Methods

1. All methods from List(Interface) & Collection (Interface), in addition

2. boolean addIfAbsent(Object)

3. int addAllAbsent(Collection)

CopyOnWriteArraySet

1. Underlying implementation is CopyOnWriteArrayList

2. Same as CopyOnWriteArrayList but duplicates are NOT allowed

3. Constructors

1. Default

2. Collections

4. Methods

1. No new methods, ONLY from Set & Collection interface