Bhavanam Venkata Suresh Reddy

1/20/2024

1
 Bhavanam Venkata Suresh Reddy
Agenda 1/20/2024

✓ Introduction
✓ List
✓ Queue
✓ Set
✓ Iterator and Fail Fast & Fail Safe Collection Framework
✓ Comparable vs Comparator
✓ Map Bhavanam Venkata Suresh Reddy
✓ Generics & Wildcard
✓ BST and AVL Trees
✓ Graphs

2
 Bhavanam Venkata Suresh Reddy
1/20/2024

Introduction
✓Collection is all about storing the data(Large volumes) and processing it.

✓Why the need of Collection?

• Variable

• Array

• Collection

3
 Bhavanam Venkata Suresh Reddy
1/20/2024

Introduction
✓Creator of Collection Framework (V1.2)→ Joshua Bloch

• ArrayList

• LinkedList

• ArrayDeque LinkedHashSet in java V1.5

• PriorityQueue

• HashSet

• TreeSet

4
 Bhavanam Venkata Suresh Reddy
1/20/2024

Introduction
✓Apart from the method the classes inherit, they have their own methods.

✓Collection hierarchy classes → util package

✓Whatever the data we pass to the collection, it will be an Object.

5
 Bhavanam Venkata Suresh Reddy
1/20/2024

List (I)  ArrayList

✓Stores both Homogeneous & Heterogeneous data.

✓Allows INDEX based Accessing.

✓Internally follows Dynamic Array Data structure.

✓Insertion Order is preserved.

✓Duplicates are allowed.

✓By default, data will be added at the rear end.

6
 Bhavanam Venkata Suresh Reddy
1/20/2024

List (I)  ArrayList

✓Rear end → {O(1)}

✓Front end → {O(n)}

✓Middle → {O(n)}

✓Can we perform index based insertion in the ArrayList?

• YES, but not recommended

✓Demands contiguous memory locations

7
 Bhavanam Venkata Suresh Reddy
1/20/2024

List (I) + Dequeue(I)  LinkedList

✓Possess methods from List and Dequeue.

✓Stores both Homogeneous & Heterogeneous data.

✓Allows INDEX based Accessing.

✓Internally follows Double Linked List Data structure.

✓Insertion Order is preserved.

✓Duplicates are allowed.

8
 Bhavanam Venkata Suresh Reddy
1/20/2024

List (I) + Dequeue(I)  LinkedList

✓No demand for Contiguous memory locations.

✓Uses Dispersed memory locations.

✓Rear end → {O(1)}

✓Front end → {O(1)}

✓Middle → {O(1)}

9
 Bhavanam Venkata Suresh Reddy
1/20/2024

List (I) + Dequeue(I)  LinkedList

30
40
3
1
10

0 67

2 insert
45

Front end Middle Rear end

10
 Bhavanam Venkata Suresh Reddy
1/20/2024

Queue(I)  Dequeue(I)  ArrayDequeue

✓Internal DS is Dynamic Array and also Double ended Queue.

✓No index based Accessing.

✓Insertion order is preserved.

✓Duplicates are allowed.

11
 Bhavanam Venkata Suresh Reddy
1/20/2024

Queue(I)  Priorityqueue
✓Whenever we want highest priority element readily available at the front
of the collection, we have to opt for PriorityQueue.

✓Follows min-heap Data structure dynamically.

✓In min-heap DS, the parent node should have high priority data compared
to the child node.

12
 Bhavanam Venkata Suresh Reddy
1/20/2024

Queue(I)  Priorityqueue
✓Duplicates are allowed.

✓No index based operations.

✓100 50 150 25 75 125 175

✓Output : 25 50 125 100 75 150 175 → How it is possible?

13
 Bhavanam Venkata Suresh Reddy
1/20/2024

Set(I)  SortedSet(I)  TreeSet

✓No index based Operations.

✓Follows Binary Search Tree as internal Data structure.

✓Sorted order is preserved.

✓Duplicates are not allowed.

14
 Bhavanam Venkata Suresh Reddy
1/20/2024

Set(I) SortedSet(I)  TreeSet

✓50 100 150 25 75 125 175

✓Output : 25 50 75 100 125 150 175 → How it is possible?

✓For Traversal
• InOrder

• PreOrder

• PostOrder

15
 Bhavanam Venkata Suresh Reddy
1/20/2024

Time Complexity for Searching Operation

✓ArrayList → ?

✓LinkedList → ?

✓ArrayDeque → ? O(n)

✓PriorityQueue → O(n)

✓TreeSet → O(log n) & O(n)

16
 Bhavanam Venkata Suresh Reddy
1/20/2024

Set  HashSet
✓Duplicates not allowed.

✓Insertion Order not preserved.

✓For searching Operation Time Complexity is O(1) for any element.

✓Internal Data structure is Hashing Algorithm.

17
 Bhavanam Venkata Suresh Reddy
1/20/2024

Set(I)
✓ceiling()
✓higher()
✓floor()
✓lower()
✓tailSet()
✓headSet()
✓subset()

18
 Bhavanam Venkata Suresh Reddy
1/20/2024

Set  HashSet
.

Hash Function
100

10

60
0 1 2 3 4 5

Whenever we search, it will check only in a specific bucket instead of going sequentially

19
 Bhavanam Venkata Suresh Reddy
1/20/2024

Set  HashSet
✓Hashing in Java is a technique for mapping data to a secret key, that can be
used as a unique identifier for data.

✓It employs a function that generates those keys from the data and this
function is known as the Hash-function.

✓The output of this function (keys) is known as Hash-values.

20
 Bhavanam Venkata Suresh Reddy
1/20/2024

HashSet  LinkedHashSet
✓Duplicates are not allowed.

✓Insertion Order preserved.

✓For searching Operation Time Complexity is O(1) for any element.

✓Internal Data structure is Hashing Algorithm.

21
 Bhavanam Venkata Suresh Reddy Iterable 1/20/2024
interface
implements
class
extends Collection
Legacy classes

List Queue Set

ArrayList
Dequeue SortedSet
LinkedList HashSet
ArrayDequeue
Vector
TreeSet
PriorityQueue LinkedHashSet
Stack

22
 Bhavanam Venkata Suresh Reddy
1/20/2024

Enumeration Class
✓Enumeration Class is the parent class of all legacy classes like Vector.

✓Vector class contains Enumeration class methods also.

23
 Bhavanam Venkata Suresh Reddy
1/20/2024

Insertion Index based

Internal DS Duplicates Null Values
Order Accessing
ArrayList Dynamic Array
LinkedList DLL
Double ended
ArrayDeque
Queue
PriorityQueue Min-heap
TreeSet BST
HashSet Hashing

LinkedHashSet Hashing

24
 Bhavanam Venkata Suresh Reddy
1/20/2024

ACCESSING
✓Rule 1: Printing is different from Accessing.

✓Collection data can be accessed in multiple ways.

✓Normal for loop

✓Enhanced for loop

✓Iterator

✓ListIterator

25
 Bhavanam Venkata Suresh Reddy
1/20/2024

ACCESSING
✓Normal for loop

• We can traverse a Collection in either directions and also from

middle.

• Using for loop is not recommended → Why?

✓For customised traversing, we can go for foreach loop.

• Using foreach loop is also not recommended → Why?

26
 Bhavanam Venkata Suresh Reddy
1/20/2024

ACCESSING → iterator( )
✓iterator( ) method :

✓Using iterator( ) is recommended while traversing a Collection to fetch

data.

✓Iterating means fetch the data while traversing.

✓Iterator( ) is available in all classes.

27
 Bhavanam Venkata Suresh Reddy
1/20/2024

ACCESSING → iterator( )
✓Iterator itr = list.iterator( );

✓Return type is iterator Object. Will return one iterator object

✓Iterator has 2 methods

• hasNext( )

• next( )

28
 Bhavanam Venkata Suresh Reddy
1/20/2024

ACCESSING → iterator( )
✓Iterator( ) method generates iterator object.

✓next( ) method fetches data using Iterator or Cursor.

✓hasNext( ) checks whether element is present in the successor index or

not.

29
 Bhavanam Venkata Suresh Reddy
1/20/2024

ACCESSING → listIterator( )
✓listIterator( ) method is a overloaded method that traverses in both directions.

✓It has 2 methods for forward traversal and vice-versa:

✓hasNext( )

✓next( ) ListIterator litr = list.listIterator();

✓hasPrevious( )

✓previous( )

30
 Bhavanam Venkata Suresh Reddy
1/20/2024

ACCESSING
✓Whatever the collection that won’t permit index based insertion and
index based accessing is called non-list based Collection.

✓How can I iterate in reverse direction in all non-list based Collection?

• Non-list → List based → Apply listIterator( )

31
 Bhavanam Venkata Suresh Reddy
1/20/2024

ACCESSING → Fail Fast – Fail Safe

✓FFFS is limited to Collection only.

✓Whenever we try to modify a Collection, when it is getting accessed it is

called as Structural Modification or Concurrent Modification.

✓We should not use for loop to access a Collection data due to FFFS. Why?

✓For loop just repeat the task without having the ability to understanding
the situation.

32
 Bhavanam Venkata Suresh Reddy
1/20/2024

ACCESSING → Fail Fast – Fail Safe

✓iterator( ) won’t allow to change the code while getting accessed.

✓ConcurrentModificationException

✓This process is called Fail Fast.

✓Consider the application in runtime environment. What to do if exception

raised during runtime?

✓The application should fail without generating an exception. How?

33
 Bhavanam Venkata Suresh Reddy
1/20/2024

ACCESSING → Fail Fast – Fail Safe

✓To eliminate exception and making the application ConcurrentModification
safely, Go for :

✓CopyOnWriteArrayList class

✓Available in java.util.concurrent package.

34
 Bhavanam Venkata Suresh Reddy
1/20/2024

Enume Normal for

Foreach loop iterator ListIterator
ration loop
ArrayList
LinkedList
ArrayDeque

PriorityQueue
TreeSet
HashSet

LinkedHashSet

35
 Bhavanam Venkata Suresh Reddy
1/20/2024

ForEach( )
Prerequisite → Lambda expression

36
 Bhavanam Venkata Suresh Reddy
1/20/2024

Arrays || ArrayList

✓Which one would you prefer?

• Array OR ArrayList

✓Type of Data and Size of Data

37
 Bhavanam Venkata Suresh Reddy
1/20/2024

Collections(util pkg)

✓Collections is a utility class that performs operations on Collection data.

✓Sort

✓Rotate

✓Shuffle

✓Frequency

✓Reverse ……

38
 Bhavanam Venkata Suresh Reddy
1/20/2024

Complex Sorting
✓How can we sort Custom objects having multiple arguments?

✓It’s not possible to use Collections class directly.

✓This is the mark where we need to opt for Comparable and Comparator
interfaces.

39
 Bhavanam Venkata Suresh Reddy
1/20/2024

Comparable
✓Available in lang package.

✓The only method available in Comparable is compareTo( ).

✓Target class must be accessible and modifiable by us. We need to

implement directly in the target class itself.

40
 Bhavanam Venkata Suresh Reddy
1/20/2024

Comparator
✓Available in util package.

✓The only method available in Comparable is compare( ).

✓Target class need not be accessible and modifiable by us. We can

implement directly without affecting the target class.

41
 Bhavanam Venkata Suresh Reddy
1/20/2024

Comparator Vs Comparable
✓Derive the differences between the two.

✓Collection Vs Collections

42
 Bhavanam Venkata Suresh Reddy
1/20/2024

Generics
✓Generics provide Type Safety that ensures us Runtime exception won’t
occur.

✓We can use Generics:

• Method

• Class

• Interface.

43
 Bhavanam Venkata Suresh Reddy
1/20/2024

Generics
✓Wildcard ( <?> )

✓<?> → Equivalent to not using Generics thus no Type Safety.

✓<?> → means any type that is not known and not fix.

✓<? extends Human> → Upper Bound

✓<? Super Human> → Lower Bound

44
 Bhavanam Venkata Suresh Reddy
1/20/2024

Generics Conclusion
✓Achieving Type Safety.

✓We can have only specific type of data when using Generics in Collection
or Map.

✓All the Collection classes and majority of java inbuilt classes and inbuilt
interfaces are using the concept of Generics behind the scene.

✓To use Generics, class must have type T. If no type, we can’t use Generics.

45
 Bhavanam Venkata Suresh Reddy
1/20/2024

Generics Conclusion
✓If we pass Wildcard in the generics, reference variable of the Collection
having data can refer to any other type of Collection.

✓<? extends Human> → Human should be highest level and other classes
must be its children.

✓<? super Human> → Human class should be the lowest and Object class
should be the highest.

46
 Bhavanam Venkata Suresh Reddy
1/20/2024

Map
✓Map is nowhere related to Collection. Both interfaces are members of
Collection Framework.

✓Map is an Object that maps Keys to Values. eg.:Aadhar

✓Available in util package.

✓public interface Map<K,V>

• K → the type of keys maintained by this map
• V → the type of mapped values.

47
 Bhavanam Venkata Suresh Reddy
1/20/2024

Map
✓Map interface takes the place of the Dictionary class, which was totally
abstract class rather than an interface.

✓ Map interface provides 3 Collection views, which allows map’s content to

be viewed:

• set of Keys → keySet()

• collection of values → values()

• set of key-value mappings → entrySet()

48
 Bhavanam Venkata Suresh Reddy
1/20/2024

Map
✓The order of a map is defined as the order in which the iterators on the
map's collection views return their elements.

✓Dictionary class replaced by Map.

✓Hashtable is a legacy class which extends Dictionary class.

49
 Bhavanam Venkata Suresh Reddy
1/20/2024

Dictionary Map SortedMap

Hashtable HashMap NavigableMap

interface
class

Properties LinkedHashMap TreeMap

50
 Bhavanam Venkata Suresh Reddy
1/20/2024

HashMap (hashing)
✓Duplicate values are allowed but not duplicate Keys.

✓One Null key is allowed. Multiple null values are allowed.

✓Insertion order is not preserved.

✓Key and Value together Called as an Entry.

✓Entry is a sub interface of Map interface.

✓HashMap<K,V> map = new HashMap<>( );

51
 Bhavanam Venkata Suresh Reddy
1/20/2024

LinkedHashMap(Linked list + Hashing)

✓Duplicate values are allowed but not duplicate Keys.

✓One Null key is allowed. Multiple null values are allowed.

✓Insertion order is preserved.

✓Efficient for insertion and retrieval of data.

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

52
 Bhavanam Venkata Suresh Reddy
1/20/2024

TreeMap(Red-Black Trees)
✓Duplicate values are allowed but not duplicate Keys.

✓Null key is not allowed. Null values are allowed.

✓Sorted order is preserved.

✓Efficient for insertion and retrieval of data.

✓TreeMap<K,V> map = new TreeMap<>( );

53
 Bhavanam Venkata Suresh Reddy
1/20/2024

Hashtable(legacy class)
✓Duplicate values are allowed but not duplicate Keys.

✓Null key or Null value is not allowed.

✓Sorted Descending order is preserved.

✓Insertion order is not preserved.

✓Hashtable<K,V> map = new Hashtable<>( );

54
 Bhavanam Venkata Suresh Reddy
1/20/2024

Hashtable(legacy class)
✓HashMap dominates Garbage Collector.

✓Garbage Collector dominates WeakHashMap

55
 Bhavanam Venkata Suresh Reddy
1/20/2024

Brain power
✓Which of the following classes allow adding of null as a key in Map?

✓Apply HashMap knowledge through a scenario → Take id number and

display customer details accordingly from the Hashmap.

✓Implement how a Garbage Collector dominates WeakHashMap and it

being dominated by HashMap.

56
Bhavanam Venkata Suresh Reddy
1/20/2024

57
 Bhavanam Venkata Suresh Reddy
1/20/2024

Inner Classes
Anonymous Inner Class
Types of Interfaces To understand LAmbda

58
 Bhavanam Venkata Suresh Reddy
1/20/2024

Interface Types
1) Normal → more than one method
2) SAM → Single Abstract method (Till V1.7) Functional Interface(From V1.8) → Have
only one method.
3) Marker →No methods

59