Common Methods & Performance of Java Collection Implementations

Java's Collection Framework provides various methods that can be applied to collections, allowing developers to manipulate, query, and interact with the data structures effectively. Understanding the performance implications of these methods is crucial for selecting the right implementation based on use cases.

Here’s an overview of common methods across different collection types and their performance characteristics:

1. Common Methods in Collection Interface

The Collection interface provides several fundamental methods that are inherited by all collection implementations (e.g., List, Set, Queue).

Method	Description	Time Complexity (ArrayList, HashSet)
`add(E e)`	Adds the specified element to the collection.	O(1) (Amortized for ArrayList), O(1) (HashSet)
`remove(Object o)`	Removes the specified element if it exists.	O(n) (ArrayList), O(1) (HashSet)
`contains(Object o)`	Returns `true` if the collection contains the specified element.	O(n) (ArrayList), O(1) (HashSet)
`size()`	Returns the number of elements in the collection.	O(1)
`isEmpty()`	Returns `true` if the collection is empty.	O(1)
`clear()`	Removes all elements from the collection.	O(n)
`iterator()`	Returns an iterator over the elements in the collection.	O(1)

2. List Methods and Performance

The List interface extends the Collection interface and adds methods for positional access and manipulation.

Method	Description	ArrayList Performance	LinkedList Performance
`get(int index)`	Returns the element at the specified position in the list.	O(1)	O(n)
`add(int index, E e)`	Inserts an element at the specified position in the list.	O(n)	O(n) (O(1) for add at ends)
`set(int index, E e)`	Replaces the element at the specified position with the specified element.	O(1)	O(n)
`remove(int index)`	Removes the element at the specified position.	O(n)	O(n) (O(1) for removal at ends)
`indexOf(Object o)`	Returns the index of the first occurrence of the specified element.	O(n)	O(n)
`contains(Object o)`	Returns `true` if the list contains the specified element.	O(n)	O(n)
`size()`	Returns the number of elements in the list.	O(1)	O(1)

Performance Considerations:

ArrayList: Fast random access, slower for adding/removing in the middle.
LinkedList: Better performance for frequent insertions and deletions at the ends (O(1)), but slower for random access (O(n)).

3. Set Methods and Performance

The Set interface extends the Collection interface but prohibits duplicate elements. Here’s the performance for key implementations like HashSet, LinkedHashSet, and TreeSet.

Method	Description	HashSet Performance	TreeSet Performance
`add(E e)`	Adds the specified element to the set if it is not already present.	O(1)	O(log n)
`remove(Object o)`	Removes the specified element if it exists.	O(1)	O(log n)
`contains(Object o)`	Returns `true` if the set contains the specified element.	O(1)	O(log n)
`size()`	Returns the number of elements in the set.	O(1)	O(1)

Performance Considerations:

HashSet: Best for unordered sets with fast lookups and insertions.
TreeSet: Maintains sorted order but has higher time complexity due to tree structure (logarithmic operations).

4. Queue Methods and Performance

The Queue interface extends the Collection interface and focuses on element processing in a FIFO manner.

Method	Description	LinkedList Performance	PriorityQueue Performance
`offer(E e)`	Inserts the specified element into the queue.	O(1)	O(log n)
`poll()`	Retrieves and removes the head of the queue.	O(1)	O(log n)
`peek()`	Retrieves, but does not remove, the head of the queue.	O(1)	O(1)

Performance Considerations:

LinkedList: Efficient for basic FIFO queue operations.
PriorityQueue: Maintains order based on priority, slower insertions and removals (logarithmic operations).

5. Map Methods and Performance

The Map interface manages key-value pairs, where each key is unique.

Method	Description	HashMap Performance	TreeMap Performance
`put(K key, V value)`	Associates the specified value with the specified key.	O(1)	O(log n)
`get(Object key)`	Returns the value to which the specified key is mapped.	O(1)	O(log n)
`remove(Object key)`	Removes the mapping for the specified key.	O(1)	O(log n)
`containsKey(Object key)`	Returns `true` if the map contains a mapping for the specified key.	O(1)	O(log n)
`size()`	Returns the number of key-value mappings.	O(1)	O(1)

Performance Considerations:

HashMap: Efficient for unordered key-value mapping with O(1) performance for most operations.
TreeMap: Maintains keys in sorted order, slower operations due to the tree structure.

Summary of Time Complexity for Common Implementations

Collection Type	Operation	ArrayList	LinkedList	HashSet	TreeSet	HashMap	TreeMap
Add	Adding an element	O(1) (amortized)	O(1) (at ends)	O(1)	O(log n)	O(1)	O(log n)
Remove	Removing an element	O(n)	O(n)	O(1)	O(log n)	O(1)	O(log n)
Get	Accessing an element by index	O(1)	O(n)	N/A	N/A	O(1) (via key)	O(log n)
Contains	Checking if element exists	O(n)	O(n)	O(1)	O(log n)	O(1)	O(log n)
Size	Getting the size of collection	O(1)	O(1)	O(1)	O(1)	O(1)	O(1)

Choosing the Right Collection Based on Performance

If random access is needed:
- Use ArrayList for fast random access (O(1)).
If frequent insertions/removals at ends:
- Use LinkedList (O(1) at ends).
If uniqueness without order is required:
- Use HashSet for fast O(1) performance.
If sorted order is needed:
- Use TreeSet or TreeMap (O(log n) performance).
For key-value pairs without order:
- Use HashMap for O(1) performance in insertions and lookups.
For priority-based queueing:
- Use PriorityQueue with logarithmic operations (O(log n)) for insertion and removal.