Java Data structure

1
What are Data Structures?
• Data structure is a storage that is used to store and organize data.
• It is a way of arranging data on a computer so that it can be accessed
and updated efficiently.
• Depending on your requirement and project, it is important to choose
the right data structure for your project.
• For example, if you want to store data sequentially in the memory,
then you can go for the Array data structure.

2
Java Collections
Framework

3
Java Collections Framework
• The Java collections framework provides a set of interfaces and
classes to implement various data structures and algorithms.
• For example, the LinkedList class of the collections framework
provides the implementation of the doubly-linked list data structure.

4
Interfaces of Collections FrameWork
• The Java collections framework provides various interfaces.
• These interfaces include several methods to perform different
operations on collections.

5
6
Java Collection Interface
• The Collection interface is the root interface of the collections
framework hierarchy.
• Java does not provide direct implementations of the Collection
interface but provides implementations of its subinterfaces like List,
Set, and Queue.

7
Collections Framework Vs. Collection
Interface
• People often get confused between the collections framework and
Collection Interface.
• The Collection interface is the root interface of the collections
framework.
• The framework includes other interfaces as well:
• Map and
• Iterator.
• These interfaces may also have subinterfaces.

8
Subinterfaces of the Collection
Interface
• As mentioned earlier, the Collection interface includes subinterfaces
that are implemented by Java classes.
• All the methods of the Collection interface are also present in its
subinterfaces.
• Here are the subinterfaces of the Collection Interface:
• List Interface
• Set Interface
• Queue Interface

9
Java List

10
Java List
• In Java, the List interface is an ordered collection that allows us to
store and access elements sequentially.
• It extends the Collection interface.

11
Classes that Implement List
• Since List is an interface, we cannot create objects from it.
• In order to use the functionalities of the List interface, we can use
these classes:
• ArrayList
• LinkedList
• Vector
• Stack

12
13
How to use List?
• In Java, we must import java.util.List package in order to use List.

// ArrayList implementation of List

List<String> list1 = new ArrayList<>();

// LinkedList implementation of List

List<String> list2 = new LinkedList<>();

• Here, we have created objects list1 and list2 of classes ArrayList and
LinkedList.
• These objects can use the functionalities of the List interface. 14
Methods of List
• The List interface includes all the methods of the Collection interface.
• Its because Collection is a super interface of List.
• Some of the commonly used methods of the Collection interface
that's also available in the List interface are:
• add() adds an element to a list
• addAll() adds all elements of one list to another
• get() helps to randomly access elements from lists
• set() changes elements of lists
• remove() removes an element from the list
15
Implementation of
ArrayList and
LinkedList

16
Java Set Interface

17
Java Set Interface
• The Set interface of the Java Collections framework provides the
features of the mathematical set in Java.
• It extends the Collection interface.
• Unlike the List interface, sets cannot contain duplicate elements.

18
Classes that implement Set
• Since Set is an interface, we cannot create objects from it.
• In order to use functionalities of the Set interface, we can use these
classes:
• HashSet
• LinkedHashSet
• EnumSet
• TreeSet
• These classes are defined in the Collections framework and
implement the Set interface.

19
20
Interfaces that extend Set
• The Set interface is also extended by these subinterfaces:
• SortedSet
• NavigableSet

21
How to use Set?
• In Java, we must import java.util.Set package in order to use
Set.

// Set implementation using HashSet

Set<String> animals = new HashSet<>();

22
Methods of Set
• The Set interface includes all the methods of the Collection interface.
It's because Collection is a super interface of Set.
• Some of the commonly used methods of the Collection interface
that's also available in the Set interface are:
• add() - adds the specified element to the set
• addAll() - adds all the elements of the specified collection to the set
• remove() - removes the specified element from the set
• removeAll() - removes all the elements from the set that is present in another
specified set
• size() - returns the length (number of elements) of the set

23
Set Operations
• The Java Set interface allows us to perform basic mathematical set
operations like union, intersection, and subset.
• Union - to get the union of two sets x and y, we can use x.addAll(y)
• Intersection - to get the intersection of two sets x and y, we can use
x.retainAll(y)
• Subset - to check if x is a subset of y, we can use y.containsAll(x)

24
Implementation of
HashSet and TreeSet

25
Java Queue Interface

26
Java Queue Interface
• The Queue interface of the Java collections framework provides the
functionality of the queue data structure.
• It extends the Collection interface.

27
Classes that Implement Queue
• Since the Queue is an interface, we cannot provide the direct
implementation of it.
• In order to use the functionalities of Queue, we need to use classes
that implement it:
• ArrayDeque
• LinkedList
• PriorityQueue

28
29
Interfaces that extend Queue
• The Queue interface is also extended by various subinterfaces:
• Deque
• BlockingQueue
• BlockingDeque

30
31
Working of Queue Data Structure
• In queues, elements are stored and accessed in First In, First Out
manner.
• That is, elements are added from the behind and removed from the
front.

32
How to use Queue?
• In Java, we must import java.util.Queue package in order to use Queue.

// LinkedList implementation of Queue

Queue<String> animal1 = new LinkedList<>();

// Array implementation of Queue

Queue<String> animal2 = new ArrayDeque<>();

// Priority Queue implementation of Queue

Queue<String> animal 3 = new PriorityQueue<>();
33
How to use Queue?
• Here, we have created objects animal1, animal2 and animal3 of
classes LinkedList, ArrayDeque and PriorityQueue respectively.
• These objects can use the functionalities of the Queue interface.

34
Methods of Queue
• The Queue interface includes all the methods of the Collection
interface.
• It is because Collection is the super interface of Queue.
• Some of the commonly used methods of the Queue interface are:
• add() - Inserts the specified element into the queue. If the task is
successful, add() returns true, if not it throws an exception.
• offer() - Inserts the specified element into the queue. If the task is
successful, offer() returns true, if not it returns false.

35
Implementation of the
Queue Interface

36
Java Map Interface

37
Java Map Interface
• The Map interface of the Java collections framework provides the
functionality of the map data structure.

38
Working of Map
• In Java, elements of Map are stored in key/value pairs.
• Keys are unique values associated with individual Values.
• A map cannot contain duplicate keys.
• And, each key is associated with a single value.

39
Working of Map
• We can access and modify values using the keys associated with
them.
• In the above diagram, we have values: United States, Brazil, and
Spain.
• And we have corresponding keys: us, br, and es.
• Now, we can access those values using their corresponding keys.

40
Working of Map
• Note: The Map interface maintains 3 different sets:
• the set of keys
• the set of values
• the set of key/value associations (mapping).
• Hence we can access keys, values, and associations individually.

41
Classes that implement Map
• Since Map is an interface, we cannot create objects from it.
• In order to use the functionalities of the Map interface, we can use
these classes:
• HashMap
• EnumMap
• LinkedHashMap
• WeakHashMap
• TreeMap
• These classes are defined in the collections framework and
implemented in the Map interface.
42
43
Interfaces that extend Map
• The Map interface is also extended by these subinterfaces:
• SortedMap
• NavigableMap
• ConcurrentMap

44
How to use Map?
• In Java, we must import the java.util.Map package in order to use
Map.
• Once we import the package, here's how we can create a map.

// Map implementation using HashMap

Map<Key, Value> numbers = new HashMap<>();

• In the above code, we have created a Map named numbers.

• We have used the HashMap class to implement the Map interface.
45
How to use Map?
• Here,
• Key - a unique identifier used to associate each element (value) in
a map
• Value - elements associated by keys in a map

46
Methods of Map
• The Map interface includes all the methods of the Collection
interface.
• It is because Collection is a super interface of Map.
• Besides methods available in the Collection interface, the Map
interface also includes the following methods:
• put(K, V) - Inserts the association of a key K and a value V into the
map. If the key is already present, the new value replaces the old
value.
• putAll() - Inserts all the entries from the specified map to this map.

47
Implementation of the
Map Interface using
HashMap and TreeMap

48
Java Algorithms

49
Java Algorithms
• The Java collections framework provides various algorithms that can
be used to manipulate elements stored in data structures.
• Algorithms in Java are static methods that can be used to perform
various operations on collections.
• Since algorithms can be used on various collections, these are also
known as generic algorithms.
• Let's see the implementation of different methods available in the
collections framework.

50
1. Sorting Using sort()
• The sort() method provided by the collections framework is used to
sort elements.

51
2. Shuffling Using shuffle()
• The shuffle() method of the Java collections framework is used to
destroy any kind of order present in the data structure.
• It does just the opposite of the sorting.

52
3. Routine Data Manipulation
• In Java, the collections framework provides different methods that
can be used to manipulate data.
• reverse() - reverses the order of elements
• fill() - replace every element in a collection with the specified value
• copy() - creates a copy of elements from the specified source to
destination
• swap() - swaps the position of two elements in a collection

53
4. Searching Using binarySearch()
• The binarySearch() method of the Java collections framework
searches for the specified element.
• It returns the position of the element in the specified collections.

54
5. Composition
• frequency() - returns the count of the number of times an element is
present in the collection
• disjoint() - checks if two collections contain some common element

55
6. Finding Extreme Values
• The min() and max() methods of the Java collections framework are
used to find the minimum and the maximum elements, respectively.

56
The End

57