ArrayList

1. What is ArrayList?
 Think of it like a dynamic array (it grows/shrinks automatically).
 It allows duplicates.
 Maintains insertion order (elements come out in the same order you put them).
 Allows null values.

2. How it works internally?

 Under the hood, it uses a resizable array.
 Default size = 10.
 If it gets full, it creates a new bigger array (1.5x size) and copies old elements into it.

📌 ArrayList Recap (full theory points)

1. Resizes dynamically (initial capacity 10 → increases by 50% when full).

2. Duplicates allowed, maintains insertion order.
3. Null values allowed.
4. Not synchronized (faster, but not thread-safe).
5. Time Complexity:
o get()/set() → O(1)

o add(E) → O(1) amortized

o add(index, E) or remove(index) → O(n) (because of shifting)

6. Constructors:
o ArrayList() → default size 10

o ArrayList(int capacity) → set initial size

o ArrayList(Collection c) → create from another collection

3. Common Methods (simple words):

 add(E e) → add element
 add(int index, E e) → add at a position
 get(int index) → fetch element
  set(int index, E e) → update element
 remove(int index) / remove(Object o) → delete by index or value
 size() → number of elements
 isEmpty() → check if empty
 contains(Object o) → check if value exists
 clear() → remove all elements
 iterator() → loop using Iterator
 forEach() → loop with lambda
[Link](list);
[Link](list);
int max = [Link](num);
[Link]("Largest element: " + max);

Part 1: Basics & Concepts

1. Main difference between ArrayList and Array in Java
o Array: Fixed size, can store primitives directly, less flexible.

o ArrayList: Dynamic size, can only store objects (no primitives directly), provides many
built-in methods like add(), remove(), contains().
2. Is ArrayList synchronized or unsynchronized?
o Unsynchronized.

o If multiple threads need to access it safely, you can wrap it using:

o List<Integer> syncList = [Link](new ArrayList<>());

3. Can ArrayList store primitive types directly?

o No, it stores objects only.

o Use wrapper classes: Integer for int, Double for double, etc.

o ArrayList<Integer> list = new ArrayList<>();

o [Link](10); // auto-boxed to Integer

4. Default initial capacity of an ArrayList

o 10.

o If elements exceed capacity, it doubles internally (actually: newCapacity = oldCapacity*3/2

+ 1).
5. How ArrayList grows internally when more elements are added beyond capacity
o Creates a new array with larger capacity (1.5× old size + 1).
 o Copies all old elements to the new array.

Part 2: Methods & Operations

6. Difference between add(index, element) and set(index, element)
o add(index, element) → Inserts element at the index, shifts remaining elements.

o set(index, element) → Replaces element at the index, does not shift.

7. What happens if you call get(index) with index > size?

o Throws IndexOutOfBoundsException.

8. How to remove all elements from an ArrayList

o Use clear() method:

o [Link]();

9. Difference between remove(index) and remove(Object o)

o remove(index) → removes element at the given index.

o remove(Object o) → removes the first occurrence of the object o.

10. How to check if ArrayList contains a specific element

o Use contains():

o [Link](10); // true if 10 exists

11. Convert an ArrayList to an array

12. ArrayList<String> list = new ArrayList<>();
13. String[] arr = [Link](new String[0]);
14. Sort an ArrayList of integers in ascending order
15. [Link](list);
16. Reverse an ArrayList
17. [Link](list);

Part 3: Loops & Iteration

14. Loop to print all elements of an ArrayList
15. for(String s : list) {
16. [Link](s);
17. }
18. Difference between for-each loop and Iterator
 for-each: simpler, cannot remove elements while iterating.
 Iterator: allows removing elements safely using [Link]().
 16. How to remove elements safely while iterating
17. Iterator<Integer> itr = [Link]();
18. while([Link]()) {
19. if([Link]() % 2 == 0) {
20. [Link](); // safe removal
21. }
22. }

 Write a Java code snippet to find the largest element in an ArrayList of integers.
 Write a Java code snippet to count the frequency of a specific element in an ArrayList.
 How to merge two ArrayLists into one?
 Write code to remove duplicates from an ArrayList of integers.
 Write code to find the index of the first occurrence of a given element in an ArrayList.
 How to convert an ArrayList of Strings to a single comma-separated String?
 Write code to shift all zeroes to the end of an ArrayList of integers while maintaining the order of non-
zero elements.
 Linked List
1. What is LinkedList?
 LinkedList is a data structure that stores elements as nodes, where each node has:
1. The data
2. A pointer to the next node (and previous node for doubly linked list)
 Unlike ArrayList, it does not store elements in a contiguous memory block.
Key point:
 Fast insertions/deletions anywhere in the list.
 Slow random access (get(index)) compared to ArrayList.
2. LinkedList in Java
 Implements List, Deque, and Queue interfaces.
 Supports:
o List operations: add, remove, get, set

o Queue operations: offer, poll, peek

o Deque operations: addFirst, addLast, removeFirst, removeLast

4. Common Methods
List Methods
 add(element) → adds at end
 add(index, element) → adds at specific position
 set(index, element) → replaces element at index
 get(index) → returns element at index
 remove(index) → removes element at index
 remove(Object o) → removes first occurrence of object
Deque / Queue Methods
 addFirst(element) / addLast(element)
 removeFirst() / removeLast()
 getFirst() / getLast()
 peek(), poll(), offer() (queue operations)
5. When to use LinkedList over ArrayList?
 LinkedList: many insertions/deletions in the middle or start.
 ArrayList: frequent random access (get(index)) is required.
 HashSet
🌱 HashSet Internals

1. Data Structure Used →

o Internally uses a HashMap.

o The elements of the Set are stored as keys in the HashMap.

o Values are just a dummy constant (PRESENT).

2. Null values →
o HashSet → allows only one null (since Set doesn’t allow duplicates).

o LinkedHashSet → also allows one null.

o TreeSet → ❌ No null, because it sorts elements and null cannot be compared.

3. Growth / Resizing →
o Same as HashMap.

o Initial capacity: 16.

o Load factor: 0.75 (means if 75% full, capacity doubles).

o So at 12 elements, it grows to capacity 32, and so on.

4. Performance →
o add, remove, contains → O(1) average (because of hashing).

o TreeSet → O(log n) (because of balanced tree).

add(E e) // add element

addAll(Collection c) // add all elements from another collection
remove(Object o) // remove element
removeAll(Collection c) // remove all elements from another collection
retainAll(Collection c) // keep only common elements (intersection)
clear() // remove all elements
contains(Object o) // check if element exists
containsAll(Collection c)// check if all elements exist
isEmpty() // check if empty
size() // number of elements
iterator() // get iterator for iteration
toArray() // convert to array
equals(Object o) // check equality of sets
hashCode() // get hash code of set

LinkedHashSet
LinkedHashSet in Java
Definition
 LinkedHashSet is a HashSet + LinkedList combination.
 It does not allow duplicates (like HashSet).
 But unlike HashSet, it maintains insertion order using a doubly-linked list.
Key Characteristics
1. Ordering: Maintains insertion order of elements.
2. Duplicates: Not allowed (just like HashSet).
3. Null values: Allows one null element.
4. Performance:
o Same performance as HashSet (O(1) for add, remove, contains).

o Slightly slower than HashSet because it maintains a linked list for order.

5. Internal DS Used:
o HashMap for storage.

o Doubly Linked List to maintain insertion order.

6. Thread Safety:
o Not synchronized.

o Can be synchronized using [Link](new LinkedHashSet<>()).

Constructors
 LinkedHashSet() → Creates empty set with default capacity (16) and load factor (0.75).
 LinkedHashSet(Collection c) → Creates a set containing elements of collection c.
 LinkedHashSet(int capacity) → Creates empty set with given capacity.
 LinkedHashSet(int capacity, float loadFactor) → Creates with specified capacity and load factor.

Common Methods (same as Set)

 add(E e) → Adds element.
  remove(Object o) → Removes element.
 contains(Object o) → Checks if present.
 clear() → Removes all elements.
 size() → Returns number of elements.
 isEmpty() → Checks if empty.
 iterator() → Iterates elements in insertion order.

Example
import [Link].*;

public class LinkedHashSetDemo {

public static void main(String[] args) {
Set<String> lhs = new LinkedHashSet<>();
[Link]("Banana");
[Link]("Apple");
[Link]("Mango");
[Link]("Apple"); // duplicate ignored
[Link](null); // null allowed once

[Link](lhs);
// Output: [Banana, Apple, Mango, null] → maintains order
}
}

When to Use LinkedHashSet?

 When you need:
✅ Unique elements
✅ Fast operations (O(1))
✅ Preserve insertion order

 Example: Cache implementation, maintaining a history list without duplicates, etc.

⚡ Quick comparison:

 ArrayList → Allows duplicates, maintains order.

  HashSet → No duplicates, no order.
 LinkedHashSet → No duplicates, maintains order.

TreeSet
🌳 What is a TreeSet?

 A TreeSet in Java is a class that implements the NavigableSet interface (which extends SortedSet).
 It stores unique elements (like HashSet and LinkedHashSet).
 But unlike them, it maintains elements in sorted (ascending) order automatically.
 Internally, it uses a Red-Black Tree (a type of self-balancing binary search tree).

⚡ Key Points about TreeSet:

1. Order → Elements are stored in sorted order (default = ascending).

2. Duplicates → Not allowed.
3. Null → Only one null is allowed, but not in Java 7+ (throws NullPointerException).
4. Performance →
o Add, remove, search → O(log n) (because of tree structure).

o Slower than HashSet (which is O(1) on average).

5. Implements → NavigableSet, so it has extra methods:

o higher(e) → returns next greater element

o lower(e) → returns next smaller element

o ceiling(e) → smallest element ≥ e

o floor(e) → largest element ≤ e

o headSet(e) → all elements less than e

o tailSet(e) → all elements greater than or equal to e

o subSet(e1, e2) → range between e1 (inclusive) and e2 (exclusive)

✅ Example:

import [Link].*;

public class TreeSetExample {

 public static void main(String[] args) {
TreeSet<Integer> ts = new TreeSet<>();

[Link](50);
[Link](10);
[Link](30);
[Link](20);
[Link](40);

[Link]("TreeSet: " + ts); // Sorted order

[Link]("First: " + [Link]()); // 10

[Link]("Last: " + [Link]()); // 50
[Link]("Higher(25): " + [Link](25)); // 30
[Link]("Lower(25): " + [Link](25)); // 20
[Link]("SubSet(20, 40): " + [Link](20, 40)); // 20,30
}
}
boolean add(E e) // add element
boolean remove(Object o) // remove element
boolean contains(Object o) // check presence
int size() // number of elements
boolean isEmpty() // check empty
void clear() // remove all
Iterator<E> iterator() // get iterator
Spliterator<E> spliterator() // for streams
E first() // smallest element
E last() // largest element
SortedSet<E> headSet(E to) // elements < to
SortedSet<E> tailSet(E from) // elements >= from
SortedSet<E> subSet(E from, E to) // elements in [from, to)
Comparator<? super E> comparator() // comparator used (null if natural order)
E lower(E e) // greatest element < e
E floor(E e) // greatest element <= e
E ceiling(E e) // smallest element >= e
E higher(E e) // smallest element > e

E pollFirst() // remove & return first element

E pollLast() // remove & return last element

NavigableSet<E> descendingSet() // reverse order view

Iterator<E> descendingIterator() // reverse iterator

NavigableSet<E> headSet(E to, boolean inclusive)

NavigableSet<E> tailSet(E from, boolean inclusive)
NavigableSet<E> subSet(E from, boolean fromInclusive, E to, boolean toInclusive)
TreeSet<Integer> ts = new TreeSet<>();
[Link]([Link](10, 5, 20, 15));

[Link]("Original: " + ts); // [5, 10, 15, 20]

[Link]("Reversed: " + [Link]()); // [20, 15, 10, 5]

import [Link].*;

public class Demo {

public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet<>([Link]());
[Link](10);
[Link](5);
[Link](20);

[Link](set); // [20, 10, 5] -> sorted in descending order

}
}
 Map
🔹 What is a Map?

 A Map stores data as key-value pairs.

 Keys are unique (no duplicates).
 Values can be duplicate.
 Examples in real life:
o Student Roll No → Name

o Employee ID → Employee Object

🔹 Important Implementations

1. HashMap
o Stores entries in random order.

o Allows one null key and multiple null values.

o Backed by Hash Table (fast lookups).

2. LinkedHashMap
o Maintains insertion order of keys.

o Slightly slower than HashMap (because of ordering).

3. TreeMap
o Stores keys in sorted order (natural or custom comparator).

o Does not allow null keys.

4. Hashtable
o Legacy class (older version of HashMap).

o Synchronized (thread-safe).

o Does not allow null key/value.

🔹 Common Methods in Map

Here’s a quick cheat sheet:

put(K key, V value) // Insert or update entry
get(Object key) // Get value by key
remove(Object key) // Remove entry by key
containsKey(Object key) // Check if key exists
containsValue(Object v) // Check if value exists
keySet() // Get all keys
values() // Get all values
entrySet() // Get all key-value pairs
size() // Number of entries
clear() // Remove all entries
isEmpty() // Check if map is empty

HashMap
🔹 What is HashMap?

 Stores data in key-value pairs.

 Keys are unique, but values can be duplicate.
 Allows one null key and multiple null values.
 Internally backed by a hash table, so lookup, insert, and delete are generally O(1).

🔹 Key Points

1. No order guaranteed → elements appear in random order.

2. Hashing is used to determine where an entry is stored.
3. Collision: Two keys can have the same hash → handled internally using a linked list / tree.

🔹 Common Methods

Method Purpose

put(K key, V value) Adds or updates a key-value pair

get(Object key) Returns value for a key

remove(Object key) Removes entry by key

containsKey(Object key) Checks if key exists

containsValue(Object value) Checks if value exists

keySet() Returns set of all keys

values() Returns collection of all values

entrySet() Returns set of key-value pairs

size() Returns number of entries

Method Purpose

clear() Removes all entries

isEmpty() Checks if map is empty

🔹 Quick Example

import [Link];
import [Link];

public class DemoHashMap {

public static void main(String[] args) {
Map<Integer, String> map = new HashMap<>();

// Adding entries
[Link](1, "Vignesh");
[Link](2, "Shashi");
[Link](3, "Aravind");
[Link](4, "Malli");
[Link]("HashMap: " + map);
// Get value by key
[Link]("Key 2 value: " + [Link](2));

// Remove entry
[Link](4);
[Link]("After removal: " + map);

// Check keys and values

[Link]("Keys: " + [Link]());
[Link]("Values: " + [Link]());
}
}

LinkedHashMap
Perfect 👍 Let’s move on to LinkedHashMap.
Here’s the complete theory in simple terms:

🔹 LinkedHashMap in Java

 It is a subclass of HashMap.
 Stores key–value pairs just like HashMap.
 Maintains insertion order (unlike HashMap, which is unordered).
 Allows one null key and multiple null values.
 Not thread-safe (like HashMap).

🔹 Internal Working

 Internally uses a hash table + doubly linked list.

o Hash table → for storing key-value entries.

o Doubly linked list → to maintain the insertion order of keys.

🔹 Commonly Used Constructors

LinkedHashMap<K,V> map = new LinkedHashMap<>();

LinkedHashMap<K,V> map = new LinkedHashMap<>(initialCapacity);
LinkedHashMap<K,V> map = new LinkedHashMap<>(initialCapacity, loadFactor);
LinkedHashMap<K,V> map = new LinkedHashMap<>(initialCapacity, loadFactor, accessOrder);
 accessOrder = true → maintains access order (least recently used → most recently used).
 accessOrder = false (default) → maintains insertion order.

🔹 Important Methods

(Same as HashMap)
 put(K key, V value)
 get(Object key)
 remove(Object key)
 containsKey(Object key)
 containsValue(Object value)
 clear()
 size()
 isEmpty()
  entrySet()
 keySet()
 values()

🔹 Example

import [Link].*;

public class LinkedHashMapDemo {

public static void main(String[] args) {
LinkedHashMap<Integer, String> map = new LinkedHashMap<>();

[Link](3, "Three");
[Link](1, "One");
[Link](2, "Two");
[Link](4, "Four");
[Link]("Insertion Order Maintained: " + map);
// Access order demo
LinkedHashMap<Integer, String> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
[Link](1, "One");
[Link](2, "Two");
[Link](3, "Three");

// Access some keys

[Link](1);
[Link](3);

[Link]("Access Order Maintained: " + accessOrderMap);

}
}

TreeMap
TreeMap in Java
 Part of [Link] package.
  Implements Map interface.
 Stores keys in sorted order (ascending by default).
 Uses a Red-Black Tree internally (a type of self-balancing binary search tree).
 Null keys are not allowed (will throw NullPointerException).
 Null values are allowed.

Key Points
1. Automatic Sorting: Keys are sorted in natural order (numbers, strings) or by a custom
comparator.
2. Operations Complexity: O(log n) for most operations (get, put, remove) because it uses a tree.
3. Not Thread-Safe: Use [Link]() if multi-threading is needed.
4. Methods: Most methods are same as HashMap, plus some specific to navigable maps:
o firstKey() – returns smallest key

o lastKey() – returns largest key

o ceilingKey(K key) – least key ≥ given key

o floorKey(K key) – greatest key ≤ given key

o higherKey(K key) – least key > given key

o lowerKey(K key) – greatest key < given key

o subMap(K fromKey, K toKey) – view of portion of map

Example
import [Link];
import [Link];

public class TreeMapDemo {

public static void main(String[] args) {
TreeMap<Integer, String> map = new TreeMap<>();
[Link](50, "Vignesh");
[Link](20, "Aravind");
[Link](70, "Shashi");
[Link](10, "Malli");
[Link](60, "Atish");
 [Link]("TreeMap: " + map);

[Link]("First Key: " + [Link]());

[Link]("Last Key: " + [Link]());
[Link]("Ceiling Key of 25: " + [Link](25));
[Link]("Floor Key of 25: " + [Link](25));
}
}
Output:
TreeMap: {10=Malli, 20=Aravind, 50=Vignesh, 60=Atish, 70=Shashi}
First Key: 10
Last Key: 70
Ceiling Key of 25: 50
Floor Key of 25: 20

🔹 5 HashMap Coding Questions

1. Write a program to count the frequency of each character in a string using HashMap.
2. Given an array of integers, find all pairs whose sum equals a target value using HashMap.
3. Write a program to find the most frequent element in an array using HashMap.
4. Given two arrays, check if one array is a subset of another using HashMap.
5. Write a program to group words by their first letter using HashMap.