1. Overview of Java Collections Framework
The Java Collections Framework provides a set of classes and interfaces for storing and manipulating data efficiently. It includes:
- Interfaces:
List, Set, Map, Queue, Deque
- Implementations:
ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, PriorityQueue, etc.
2. List
What is a List?
- A
List is an ordered collection that allows duplicate elements.
- Common implementations:
ArrayList: Resizable-array implementation.
LinkedList: Doubly-linked list implementation.
How to Initialize a List?
// ArrayList Initialization
List<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
// LinkedList Initialization
List<Integer> linkedList = new LinkedList<>();
linkedList.add(3);
linkedList.add(4);
Common Functions & Methods (with complexity):
| Method |
ArrayList |
LinkedList |
Description |
| add(E e) |
O(1) amortized |
O(1) |
Append element at end |
| add(int index, E e) |
O(n) |
O(n) |
Insert at index |
| get(int index) |
O(1) |
O(n) |
Get element at index |
| set(int index, E e) |
O(1) |
O(n) |
Replace element at index |
| remove(int index) |
O(n) |
O(n) |
Remove element at index |
| remove(Object o) |
O(n) |
O(n) |
Remove by value |
| contains(Object o) |
O(n) |
O(n) |
Check if element exists |
| size() |
O(1) |
O(1) |
Get number of elements |
| clear() |
O(n) |
O(n) |
Remove all elements |
| indexOf(Object o) |
O(n) |
O(n) |
First index of element |
| lastIndexOf(Object o) |
O(n) |
O(n) |
Last index of element |
| isEmpty() |
O(1) |
O(1) |
Check if list is empty |
| iterator() |
O(1) |
O(1) |
Return iterator |
| toArray() |
O(n) |
O(n) |
Convert to array |
How to Use Common Methods?
arrayList.add(5); // add element
int x = arrayList.get(1); // get element
arrayList.set(2, 100); // update element
arrayList.remove(0); // remove by index
boolean hasVal = arrayList.contains(100); // check contains
int idx = arrayList.indexOf(100); // index of element
arrayList.clear(); // clear all
Time Complexity:
| Operation |
ArrayList |
LinkedList |
| Access (by index) |
O(1) |
O(n) |
| Insert (end) |
O(1) |
O(1) |
| Insert (middle) |
O(n) |
O(1) |
| Delete (end) |
O(1) |
O(1) |
| Delete (middle) |
O(n) |
O(1) |
Space Complexity:
- ArrayList:
O(n) for storage.
- LinkedList:
O(n) for nodes + O(n) pointers.