Unit-2.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptx

Unit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptxUnit-3_updated.pptx

1. Subject Title: Advance Java Programming, Code: CSN302 , Credit: 3:0:1:4 Class: B.Tech. 3 rd Year, 5 th Sem Unit II: Java Collections Framework Introduction to Java Collection Classes and Interfaces, Array List, Linked List, Set, Queue, HashMap , TreeMap , Collections class, Iterator interface. DIT University, 10Feb 2023

2. Collections in Java The  Collection in Java  is a framework that provides an architecture to store and manipulate the group of objects. Java Collection means a single unit of objects. Java Collection framework provides many interfaces (Set, List, Queue, Deque ) and classes ( ArrayList , Vector,  LinkedList ,  PriorityQueue , HashSet , LinkedHashSet , TreeSet ). Java Collections can achieve all the operations that you perform on a data such as searching, sorting, insertion, manipulation, and deletion.

3. What is Collection framework The Collection framework represents a unified architecture for storing and manipulating a group of objects. It has: Interfaces and its implementations, i.e., classes Algorithm

4. Hierarchy of Collection Framework Let us see the hierarchy of Collection framework. The  java.util  package contains all the  classes  and  interfaces  for the Collection framework.

5. Why the Collections Framework? The Java collections framework provides various data structures and algorithms that can be used directly. This has two main advantages: We do not have to write code to implement these data structures and algorithms manually. Our code will be much more efficient as the collections framework is highly optimized. Moreover, the collections framework allows us to use a specific data structure for a particular type of data.

6. Advantages of the Java Collection Framework Reusability:  The framework provides a comprehensive set of common classes and utility methods applicable across various types of collections. This feature promotes code reusability, sparing developers the need to write duplicate code for common operations. Quality:  Leveraging the Java Collections Framework elevates the quality of programs. The components within the framework have been extensively tested and are widely used by a vast community of developers, ensuring reliability and stability in your applications. Speed:  Developers often report an increase in development speed when using the Collections Framework. It allows them to concentrate on the core business logic of their applications rather than on implementing generic collection functionalities, thus speeding up the development process. Maintenance:  The open-source nature of the Java Collections Framework, coupled with readily available API documentation, facilitates easier code maintenance. Code written using the framework can be easily understood and taken over by other developers, ensuring continuity and ease of maintenance. Reduces Effort to Design New APIs:  An additional benefit is the reduced necessity for API designers and implementers to create new collection mechanisms for each new API. They can instead rely on the standard collection interfaces provided by the framework, streamlining the API development process and ensuring consistency across Java applications.

7. List Vs Set LIST List is an index based data structure. List can store duplicate elements. List can store any numbers of null values. List follows the insertion order. We can iterate(get) the list elements by Iterator and ListIterator SET It is not index based DS. It stores the data according to the hashcode values. Set does not allow to store duplicate elements. Set can store only one null value. Set does not follows the insertion order. We can iterate the set elements by Iterator.

8. List Interface List interface is the child interface of Collection interface. It inhibits a list type data structure in which we can store the ordered collection of objects. It can have duplicate values. List interface is implemented by the classes ArrayList , LinkedList , Vector, and Stack. To instantiate the List interface, we must use : There are various methods in List interface that can be used to insert, delete, and access the elements from the list.

9. Array List Java  ArrayList  class uses a  dynamic  array  for storing the elements. It is like an array, but there is  no size limit . We can add or remove elements anytime. So, it is much more flexible than the traditional array. It is found in the  java.util  package . The ArrayList in Java can have the duplicate elements also. It implements the List interface so we can use all the methods of the List interface here. The ArrayList maintains the insertion order internally.

10. Difference b/n Built-in Array and ArrayList : The difference between a built-in array and an  ArrayList  in Java is that the size of an array cannot be modified in Built in array. (if you want to add or remove elements to/from an array, you have to create a new one). While elements can be added and removed from an  ArrayList  whenever you want . The syntax is also slightly different: - Create an A rrayList object called cars that will store string values: Syntax:

11. Methods of List Methods Description add() adds an element to a list addAll() adds all elements of one list to another get() helps to randomly access elements from lists iterator() returns iterator object that can be used to sequentially access elements of lists set() changes elements of lists remove() removes an element from the list removeAll() removes all the elements from the list clear() removes all the elements from the list (more efficient than removeAll()) size() returns the length of lists toArray() converts a list into an array contains() returns true if a list contains specific element

12. Add Items- add() Method Example-

13. Access an Item- get() Method

14. Change an Item – set()

15. Remove an Item- remove()

16. Traversing an ArrayList

17. WAP to add numbers in ArrayList and print them

18. Sort an ArrayList (numerically)

19. Sort an ArrayList (alphabetically)

20. Java Vector The Vector class is an implementation of the List interface that allows us to create resizable-arrays similar to the ArrayList class. Java Vector vs. ArrayList In Java, both ArrayList and Vector implements the List interface and provides the same functionalities. However, there exist some differences between them. The Vector class synchronizes each individual operation. This means whenever we want to perform some operation on vectors, the Vector class automatically applies a lock to that operation. It is because when one thread is accessing a vector, and at the same time another thread tries to access it, an exception called ConcurrentModificationException is generated. Hence, this continuous use of lock for each operation makes vectors less efficient. However, in array lists, methods are not synchronized. Instead, it uses the Collections.synchronizedList () method that synchronizes the list as a whole. Note:  It is recommended to use  ArrayList  in place of  Vector  because vectors less efficient.

21. Example of Vector import java.util.Vector ; class Main { public static void main(String[] args ) { Vector<String> mammals= new Vector<>(); // Using the add() method mammals.add ("Dog"); mammals.add ("Horse"); // Using index number mammals.add (2, "Cat"); System.out.println ("Vector: " + mammals); // Using addAll () Vector<String> animals = new Vector<>(); animals.add ("Crocodile"); animals.addAll (mammals); System.out.println ("New Vector: " + animals); } } Add Elements to Vector add(element)  - adds an element to vectors add(index, element)  - adds an element to the specified position addAll (vector)  - adds all elements of a vector to another vector

22. Access Vector Elements get(index)  - returns an element specified by the index iterator()  - returns an  iterator  object to sequentially access vector elements import java.util.Iterator ; import java.util.Vector ; class Main { public static void main(String[] args ) { Vector<String> animals= new Vector<>(); animals.add ("Dog"); animals.add ("Horse"); animals.add ("Cat"); // Using get() String element = animals.get (2); System.out.println ("Element at index 2: " + element); // Using iterator() Iterator<String> iterate = animals.iterator (); System.out.print ("Vector: "); while( iterate.hasNext ()) { System.out.print ( iterate.next ()); System.out.print (", "); } } }

23. Remove Vector Elements remove(index)  - removes an element from specified position removeAll ()  - removes all the elements clear()  - removes all elements. It is more efficient than  removeAll () import java.util.Vector ; class Main { public static void main(String[] args ) { Vector<String> animals= new Vector<>(); animals.add ("Dog"); animals.add ("Horse"); animals.add ("Cat"); System.out.println ("Initial Vector: " + animals); // Using remove() String element = animals.remove (1); System.out.println ("Removed Element: " + element); System.out.println ("New Vector: " + animals); // Using clear() animals.clear (); System.out.println ("Vector after clear(): " + animals); } }

24. Methods Descriptions set() changes an element of the vector size() returns the size of the vector toArray() converts the vector into an array toString() converts the vector into a String contains() searches the vector for specified element and returns a boolean result Others Vector Methods

25. Linked List Java LinkedList class uses a doubly linked list to store the elements. It provides a linked-list data structure. It inherits the AbstractList class and implements List and Deque interfaces. The important points about Java LinkedList are: Java LinkedList class can contain duplicate elements. Java LinkedList class maintains insertion order. Java LinkedList class is non synchronized. In Java LinkedList class, manipulation is fast because no shifting needs to occur. Java LinkedList class can be used as a list, stack or queue.

26. Linked List(cont..) Linked List is a part of the  Collection framework  present in  java.util package . This class is an implementation of the  LinkedList data structure  which is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. The elements are linked using pointers and addresses. Each element is known as a node. 

27. How Does LinkedList work Internally? LinkedList acts as a dynamic array (i.e. No need to specify the size while creating it, the size of the list automatically increases when we dynamically add and remove items) And also, the elements are not stored in a continuous fashion. Therefore, there is no need to increase the size. Internally, the LinkedList is implemented using the  doubly linked list data structure .  The main difference between a normal linked list and a doubly LinkedList is that a doubly linked list contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in the singly linked list. 

28. Doubly Linked list

29. ArrayList vs. LinkedList The  LinkedList  class is a collection which can contain many objects of the same type, just like the  ArrayList . The  LinkedList  class has all of the same methods as the  ArrayList  class because they both implement the  List  interface. This means that you can add items, change items, remove items and clear the list in the same way. However, while the  ArrayList  class and the  LinkedList  class can be used in the same way, they are built very differently.

30. LinkedList object - LinkedList ():  This constructor is used to create an empty linked list. If we wish to create an empty LinkedList with the name LL, then, it can be created as: 

31. Performing Basic Operations on LinkedList : LinkedList  provides various methods that allow us to perform different operations in linked lists. Add elements Access elements Change elements Remove elements

32. WAP to add elements in LinkedList

33. 1. Add elements to a LinkedList We can use the  add()  method to add an element (node) at the end of the LinkedList . For example, import java.util.LinkedList ; class Main { public static void main(String[] args ){ // create linkedlist LinkedList <String> colors = new LinkedList <>(); // add() method without the index parameter colors.add (“red"); colors.add (“green"); colors.add (“white"); System.out.println (" LinkedList : " + colors); / / add() method with the index parameter colors.add (1, “blue"); System.out.println ("Updated LinkedList : " + colors); } }

34. 2. Access LinkedList elements import java.util.LinkedList ; class Main { public static void main(String[] args ) { LinkedList <String> languages = new LinkedList <>(); // add elements in the linked list languages.add ("Python"); languages.add ("Java"); languages.add ("JavaScript"); System.out.println (" LinkedList : " + languages); // get the element from the linked list String str = languages.get (1); System.out.print ("Element at index 1: " + str ); } } The  get()   method of the LinkedList class is used to access an element from the LinkedList . For example In the above example, we have used the  get() method with parameter 1. Here, the method returns the element at index 1. We can also access elements of the LinkedList using the iterator() and the  listIterator () method. ,

35. 3. Change Elements of a LinkedList import java.util.LinkedList ; class Main { public static void main(String[] args ) { LinkedList <String> languages = new LinkedList <>(); // add elements in the linked list languages.add ("Java"); languages.add ("Python"); languages.add ("JavaScript"); languages.add ("Java"); System.out.println (" LinkedList : " + languages); // change elements at index 3 languages.set (3, " Kotlin "); System.out.println ("Updated LinkedList : " + languages); } } Here, the  set()  method changes the element at index  3  to  Kotlin .

36. 4. Remove element from a LinkedList import java.util.LinkedList ; class Main { public static void main(String[] args ) { LinkedList <String> languages = new LinkedList <>(); // add elements in LinkedList languages.add ("Java"); languages.add ("Python"); languages.add ("JavaScript"); languages.add (" Kotlin "); System.out.println (" LinkedList : " + languages); // remove elements from index 1 String str = languages.remove (1); System.out.println ("Removed Element: " + str ); System.out.println ("Updated LinkedList : " + languages); } }

37. Other Methods

38. Iterator interface Iterator interface provides the facility of iterating the elements in a forward direction only. Methods of Iterator interface There are only three methods in the Iterator interface. They are:

39. Iterable Interface The Iterable interface is the root interface for all the collection classes. The Collection interface extends the Iterable interface and therefore all the subclasses of Collection interface also implement the Iterable interface. It contains only one abstract method. i.e., It returns the iterator over the elements of type T.

40. Queue Interface In Java The Queue interface is present in  java.util  package and extends the  Collection interface  , i.e. is used to hold the elements about to be processed in FIFO(First In First Out) order. It is an ordered list of objects with its use limited to inserting elements at the end of the list and deleting elements from the start of the list, (i.e.), it follows the  FIFO  or the First-In-First-Out principle.

41. The Queue interface of the java collections framework provides functionality of the queue data structure. Classes that IMPLEMENT Queue: 1) ArrayDeque 2) LinkedList 3) PriorityQueue .

42. LinkedList as Deque and Queue Since the  LinkedList  class also implements the  Queue  and the  Deque  interface, it can implement methods of these interfaces as well. Here are some of the commonly used methods:

43. Java LinkedList as Queue

44. Java LinkedList as Deque

45. TreeMap Java TreeMap class is a red-black tree based implementation. It provides an efficient means of storing key-value pairs in sorted order. The TreeMap class of the Java collections framework provides the tree data structure implementation. It implements the  NavigableMap interface .

46. Java TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class. Java TreeMap contains only unique elements. Java TreeMap cannot have a null key but can have multiple null values. Java TreeMap is non synchronized. Java TreeMap maintains ascending order.

47. Red-Black Tree A type of balanced binary search tree that use a specific set of rules to ensure that the tree is always balanced. This balance guarantees that the time complexity for operations such as insertion, deletion, and searching is always O(log n), regardless of the initial shape of the tree. Red Black Trees are self-balancing, meaning that the tree adjusts itself automatically after each insertion or deletion operation. It uses a simple but powerful mechanism to maintain balance, by coloring each node in the tree either red or black.

48. Creating a TreeMap Import java.util.TreeMap Package A TreeMap is created named numbers without any arguments. They are naturally sorted. We can also customize sorting using comparator interface. 2 things associated with it: 1) Key: a unique identifier used to associate each element (value) in a map 2) Value: elements associated by keys in a map

49. Methods of TreeMap The Treemap class provides various methods that allow us to perform operations on the map. Insert Elements to TreeMap put() - inserts the specified key/value mapping (entry) to the map. putAll () - inserts all the entries from specified map to this map. putIfAbsent () - inserts the specified key/value mapping to the map if the specified key is not present in the map

50. Access TreeMap Elements 1)Using entrySet (), keySet () and values() entrySet ()- returns a set of all the key/values mapping (entry) of a treemap . keySet ()- returns a set of all the keys of a tree map. values()- returns a set of all the maps of a tree map.

51. 2)Using get() and getOrDefault () get() - Returns the value associated with the specified key. Returns null if the key is not found. getOrDefault () - Returns the value associated with the specified key. Returns the specified default value if the key is not found.

52. Remove TreeMap Elements remove(key)- returns and removes the entry associated with the specified key from a TreeMap . remove(key, value)-  removes the entry from the map only if the specified key is associated with the specified value and returns a boolean value.

53. Methods for Navigation TreeMap class implements NavigableMap , it provides various methods to navigate over the elements of the treemap . 1. First and Last Methods firstKey ()- returns the first key of the map firstEntry () - returns the key/value mapping of the first key of the map lastKey ()- returns the last key of the map lastEntry ()- returns the key/value mapping of the last key of the map

54. 2. Ceiling, Floor, Higher and Lower Methods higherKey ()  - Returns the lowest key among those keys that are greater than the specified key. higherEntry ()  - Returns an entry associated with a key that is lowest among all those keys greater than the specified key. lowerKey ()  - Returns the greatest key among all those keys that are less than the specified key. lowerEntry ()  - Returns an entry associated with a key that is greatest among all those keys that are less than the specified key. ceilingKey ()  - Returns the lowest key among those keys that are greater than the specified key. If the key passed as an argument is present in the map, it returns that key. ceilingEntry ()  - Returns an entry associated with a key that is lowest among those keys that are greater than the specified key. It an entry associated with the key passed an argument is present in the map, it returns the entry associated with that key. floorKey ()  - Returns the greatest key among those keys that are less than the specified key. If the key passed as an argument is present, it returns that key. floorEntry ()  - Returns an entry associated with a key that is greatest among those keys that are less than the specified key. If the key passed as argument is present, it returns that key.

55. HashMap The HashMap class of the Java collections framework provides the functionality of the  hash table data structure . It stores elements in  key/value  pairs. Here,  keys  are unique identifiers used to associate each  value  on a map. The HashMap class implements the  Map  interface.

56. HashTable Representation HashTable is a data structure which allows for fast retrieval of information, at the cost of a little bit of implementation complexity and the need to choose a good hash function for the information you’re storing. Hashing is a technique to convert a range of key values into a range of indexes of an array. We're going to use modulo operator to get a range of key values. Consider an example of hash table of size 20, and the following items are to be stored. Item are in the ( key,value ) format. Sr.No. Key Hash Array Index 1 1 1 % 20 = 1 1

57. Create a HashMap Import java.util.HashMap created a hashmap named numbers, Here,  K  represents the key type and  V  represents the type of values. For example, Here, the type of  keys  is String and type of values is Integer.

58. Create HashMap in Java

59. Basic Operations on Java HashMap The HashMap class provides various methods to perform different operations on hashmaps . Add elements Access elements Change elements Remove elements

60. Add elements to a HashMap

61. 2. Access HashMap Elements

62. Change HashMap Value

63. Remove HashMap Elements

64. Basis HashMap TreeMap Definition Java  HashMap  is a hashtable based implementation of Map interface. Java  TreeMap  is a Tree structure-based implementation of Map interface. Interface Implements HashMap implements  Map, Cloneable , and  Serializable  interface. TreeMap implements  NavigableMap , Cloneable , and  Serializable  interface. Null Keys/ Values HashMap allows a  single  null key and  multiple  null values. TreeMap does not allow  null  keys but can have  multiple  null values. Homogeneous/ Heterogeneous HashMap allows heterogeneous elements because it does not perform sorting on keys. TreeMap allows homogeneous values as a key because of sorting. Performance HashMap is  faster  than TreeMap because it provides constant-time performance that is O(1) for the basic operations like get() and put(). TreeMap is  slow  in comparison to HashMap because it provides the performance of O(log(n)) for most operations like add(), remove() and contains(). Data Structure The HashMap class uses the  hash table . TreeMap internally uses a  Red-Black  tree, which is a self-balancing Binary Search Tree. Order of elements HashMap does not maintain any order. The elements are sorted in  natural order  (ascending). Uses The HashMap should be used when we do not require key-value pair in sorted order. The TreeMap should be used when we require key-value pair in sorted (ascending) order.