JAVA COLLECTIONS
Feature ArrayList LinkedList Vector
Implementation Resizable array Doubly linked list Resizable array
Contiguous block of Non-contiguous Contiguous block of
Memory Allocation memory memory blocks memory
Slower for Faster for Slower for
inserting/deleting inserting/deleting inserting/deleting
Insertion/Deletion elements in the middle elements in the middle elements in the middle
Random Access O(1) - Constant time O(n) - Linear time O(1) - Constant time
Iteration Faster Slower Faster
Synchronization Not synchronized Not synchronized Synchronized
Allows Null Values Yes Yes Yes
Allows Duplicate
Values Yes Yes Yes
Performance Higher (due to built-in
Overhead Lower Higher synchronization)
Best for random access, Best for frequent Trade-off between
slower for frequent changes, slower for random access and
Efficiency changes random access frequent changes
1. Memory Allocation:
ArrayList and Vector both use a contiguous block of memory, while
LinkedList uses non-contiguous memory blocks due to its nature as a
linked list.
2. Insertion/Deletion:
LinkedList offers faster insertion and deletion operations in the middle
of the list due to its structure. ArrayList and Vector perform slower in
such scenarios as elements might need to be shifted.
3. Random Access:
ArrayList and Vector provide constant-time access to elements by
index, whereas LinkedList requires traversing from the beginning of
the list, resulting in linear time complexity.
4. Synchronization:
Vector is synchronized by default, ensuring thread safety. ArrayList
and LinkedList are not synchronized, requiring manual synchronization
in multi-threaded environments.
5. Allows Null Values:
All three data structures allow null values.
6. Allows Duplicate Values:
All three data structures allow duplicate values.
7. Performance Overhead:
ArrayList generally has lower overhead as it doesn't provide built-in
synchronization. LinkedList and Vector may incur higher overhead,
especially in multi-threaded environments.
8. Efficiency:
The choice between ArrayList, LinkedList, and Vector depends on the
specific use case. ArrayList is efficient for scenarios requiring frequent
random access but slower for frequent insertions/deletions.
LinkedList is efficient for frequent insertions/deletions but slower for
random access. Vector, while providing synchronization, may have
performance drawbacks compared to ArrayList due to its synchronized
nature.
Feature Queue PriorityQueue ArrayDeque
Implementation Typically Implemented as a Resizable array-based
implemented as a
Feature Queue PriorityQueue ArrayDeque
FIFO (First-In-First-
Out) priority heap implementation
FIFO (First-In-First- Based on the priority Can be used as both FIFO and
Ordering Out) of elements LIFO (Last-In-First-Out)
Offers basic Offers operations Offers various operations like
operations such as based on priority such offerFirst, offerLast, pollFirst,
Insertion/Deletion offer, poll, peek as offer, poll, peek pollLast, peekFirst, peekLast
Access to the head Access to the highest Access to both ends of the
Access to elements of the queue priority element deque
Efficient for
Efficient for basic maintaining elements Efficient for adding/removing
Performance queue operations based on priority elements from both ends
Basic FIFO queue Maintaining a priority- General-purpose double-ended
Use Cases operations based queue queue
1. Implementation:
Queue: Typically implemented as a FIFO data structure, where the
first element inserted is the first to be removed.
PriorityQueue: Implemented as a priority heap, where elements are
ordered based on their priority.
ArrayDeque: Implemented as a resizable array-based double-ended
queue, allowing efficient insertion and deletion at both ends.
2. Ordering:
Queue: Maintains elements in the order they were inserted (FIFO).
PriorityQueue: Orders elements based on their priority, with higher
priority elements dequeued first.
ArrayDeque: Can be used as both a FIFO queue and a LIFO (Last-In-
First-Out) stack.
3. Insertion/Deletion:
Queue and PriorityQueue: Offer basic operations such as offer to add
elements, poll to remove and return the head, and peek to view the
head.
ArrayDeque: Offers various operations for adding/removing elements
from both ends, such as offerFirst, offerLast, pollFirst, pollLast,
peekFirst, peekLast.
4. Access to elements:
Queue: Access to the head (first element) of the queue.
PriorityQueue: Access to the element with the highest priority.
ArrayDeque: Access to both ends of the deque.
5. Performance:
Queue: Efficient for basic FIFO operations like enqueueing and
dequeueing.
PriorityQueue: Efficient for maintaining elements based on their
priority, offering logarithmic time complexity for most operations.
ArrayDeque: Efficient for adding/removing elements from both ends,
providing constant-time performance.
6. Use Cases:
Queue: Used for basic FIFO queue operations, such as task scheduling,
message passing, etc.
PriorityQueue: Suitable for maintaining a priority-based queue, such
as task scheduling where tasks have different priorities.
ArrayDeque: Useful as a general-purpose double-ended queue, where
elements may need to be added or removed from both ends
efficiently. It can also be used as a stack when only one end is used for
insertion and deletion (LIFO).
Feature TreeSet HashSet LinkedHashSet
Sorted order (natural
ordering or custom
Ordering comparator) Unordered Ordered (insertion order)
Feature TreeSet HashSet LinkedHashSet
Internal
Implementation Red-Black Tree Hash Table Hash Table + Linked List
Does not allow null
Null Values values Allows one null value Allows one null value
Does not allow duplicate Does not allow Does not allow duplicate
Duplicate Values values duplicate values values
Slower insertion and
removal compared to Faster insertion and Slightly slower insertion
Performance HashSet removal and removal than HashSet
Slightly higher due to
Higher due to Lower due to hash maintaining insertion
Memory Overhead maintaining sorted order table implementation order
When you need
When elements need to predictable iteration
Use Cases be stored in sorted order General-purpose set order
1. TreeSet:
TreeSet is an implementation of the SortedSet interface, maintaining
elements in a sorted order.
It uses a Red-Black Tree internally, which provides guaranteed O(log n)
time cost for basic operations such as add, remove, and contains.
TreeSet does not allow null values and does not permit duplicates.
It's suitable when you need elements to be stored in sorted order
according to their natural ordering or a custom comparator.
2. HashSet:
HashSet is an implementation of the Set interface, using a hash table
to store elements.
It provides constant-time performance for basic operations such as
add, remove, and contains.
HashSet allows one null value and does not permit duplicates.
It's a general-purpose set and suitable for most scenarios where you
don't require sorted order or predictable iteration order.
3. LinkedHashSet:
LinkedHashSet is a subclass of HashSet that maintains a doubly-linked
list running through all of its entries.
It combines the features of a hash table and a linked list, providing
predictable iteration order (order of insertion).
LinkedHashSet allows one null value and does not permit duplicates.
While slightly slower than HashSet due to maintaining insertion order,
LinkedHashSet is useful when you need elements to be stored in the
order they were inserted.
Feature TreeMap HashMap LinkedHashMap Hashtable
Sorted order
(natural ordering or
custom Ordered (insertion
Ordering comparator) Unordered order) Unordered
Internal Hash Table + Linked
Implementation Red-Black Tree Hash Table List Hash Table
Does not allow null Allows one null Does not allow
Null Keys keys key Allows one null key null keys
Allows multiple Allows multiple Allows multiple null Does not allow
Null Values null values null values values null values
Does not allow Does not allow Does not allow Does not allow
Duplicate Keys duplicate keys duplicate keys duplicate keys duplicate keys
Not
Thread Safety Not synchronized synchronized Not synchronized Synchronized
Slower insertion
and removal Slightly slower Slower insertion
compared to Faster insertion insertion and removal and removal than
Performance HashMap and removal than HashMap HashMap
Use Cases When elements General- When you need When you need
Feature TreeMap HashMap LinkedHashMap Hashtable
need to be stored predictable iteration thread-safe
in sorted order purpose map order operations
1. TreeMap:
TreeMap is an implementation of the SortedMap interface, storing
key-value pairs in a sorted order.
It uses a Red-Black Tree internally, which provides guaranteed O(log n)
time cost for basic operations such as put, get, and remove.
TreeMap does not allow null keys and does not permit duplicate keys.
It's suitable when you need elements to be stored in sorted order
according to their natural ordering or a custom comparator.
2. HashMap:
HashMap is an implementation of the Map interface, using a hash
table to store key-value pairs.
It provides constant-time performance for basic operations such as
put, get, and remove.
HashMap allows one null key and multiple null values. It does not
permit duplicate keys.
It's a general-purpose map and suitable for most scenarios where you
don't require sorted order or predictable iteration order.
3. LinkedHashMap:
LinkedHashMap is a subclass of HashMap that maintains a doubly-
linked list running through all of its entries.
It combines the features of a hash table and a linked list, providing
predictable iteration order (order of insertion).
LinkedHashMap allows one null key and multiple null values. It does
not permit duplicate keys.
While slightly slower than HashMap due to maintaining insertion
order, LinkedHashMap is useful when you need elements to be stored
in the order they were inserted.
4. Hashtable:
Hashtable is a legacy class and was part of the original Java Collections
framework.
It is similar to HashMap but is synchronized, making it thread-safe.
Hashtable does not allow null keys or null values, and it does not
permit duplicate keys.
Due to its synchronized nature, Hashtable is slower than HashMap,
and its use is discouraged in favor of ConcurrentHashMap for thread-
safe operations in modern Java applications.