Learning Today,
Leading Tomorrow

Collection framework in Java

It is a combination of classes and interface, which is used to store and manipulate the data in the form of objects. It provides various classes such as ArrayList, Vector, Stack, and HashSet, etc. and interfaces such as Collection, List, Set, Queue etc.

Collection interface: Collection (java.util.Collection) is the primary interface, and every collection must implement this interface.

List interface: List interface extends the Collection interface, and it is an ordered collection of objects. It contains duplicate elements. It also allows random access of elements. Set interface: Set (java.util.Set) interface is a collection which cannot contain duplicate elements. It can only include inherited methods of Collection interface Queue interface: Queue (java.util.Queue) interface defines queue data structure, which stores the elements in the form FIFO (first in first out). Dequeue interface: It is a double-ended-queue. It allows the insertion and removal of elements from both ends. It implants the properties of both Stack and Queue so it can perform LIFO (Last in first out) stack and FIFO (first in first out) queue, operations. Map interface: A Map (java.util.Map) represents a key, value pair storage of elements. Map interface does not implement the Collection interface. It can only contain a unique key but can have duplicate elements. There are two interfaces which implement Map in java that are Map interface and Sorted Map.

ArrayList Class 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. ArrayList is a data structure that can be stretched to accommodate additional elements within itself and shrink back to a smaller size when elements are removed. Technically, the default capacity of a newly created ArrayList is 10. ArrayList is initialized by the size 0. However, the size is increased automatically if the collection grows or shrinks if the objects are removed from the collection. Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. However, Java 8 changed how this initial capacity is used for performance reasons. So, the default capacity of an empty ArrayList is 0 and not 10 in Java 8. Once the first item is added, the DEFAULT_CAPACITY which is 10 is then used. ArrayList is not a legacy class. ArrayList increases its size by 50% of the array size. ArrayList is not thread-safe as it is not synchronized. ArrayList uses a dynamic array to store the element. Manipulation with ArrayList is slow because it internally uses an array. If any element is removed from the array, all the other elements are shifted in memory. ArrayList is better to store and fetch data. ArrayList provides random access. ArrayList takes less memory overhead as it stores only object

ArrayList working

Since ArrayList is a dynamic array and we do not have to specify the size while creating it, the size of the array automatically increases when we dynamically add and remove items. The following is a very basic idea explaining the working of the array when the array becomes full and if we try to add an item:

Creates a bigger sized memory on heap memory (for example memory of double size). Copies the current memory elements to the new memory. New item is added now as there is bigger memory available now. Delete the old memory.

ArrayList is resized by 50% of it’s current size. So, ArrayList will be resized from 10, to 15, to 22, to 33 and so on. ArrayList’s add method internally calls ensureCapacityInternal method, which calls ensureExplicitCapacity method, which calls grow method, grow method > creates new array of higher capacity and copies existing array to new one and return the new array. Default size offers best tradeoff between memory occupied and performance. Keeping ArrayList size very less can be a huge performance set back, because it will be resized very rapidly.

Important Features of ArrayList Java Dynamic Resizing: ArrayList grows dynamically as we add elements to the list or shrinks as we remove elements from the list. Ordered: ArrayList preserves the order of the elements i.e. the order in which the elements were added to the list. Index based: ArrayList in Java supports random access from the list using index positions starting with ‘0’. Object based: ArrayList can store only Objects data types. They cannot be used for primitive data types (int, float, etc). We require a wrapper class in that case. Not Synchronized: ArrayList in Java is not synchronized, we can use the Vector class for the synchronized version. It means ArrayList operations are not thread-safe and multiple threads should not operate on the same ArrayList object at the same time.

Constructors in the ArrayList

ArrayList(): This constructor is used to build an empty array list. If we wish to create an empty ArrayList with the name arr, then, it can be created as: ArrayList arr = new ArrayList();

ArrayList(Collection c): This constructor is used to build an array list initialized with the elements from the collection c. Suppose, we wish to create an arraylist arr which contains the elements present in the collection c, then, it can be created as:ArrayList arr = new ArrayList(c);

ArrayList(int capacity): This constructor is used to build an array list with initial capacity being specified. Suppose we wish to create an ArrayList with the initial size being N, then, it can be created as: ArrayList arr = new ArrayList(N);

add(int index, Object element) | add(Object o) | addAll(Collection C)| addAll(int index, Collection C)| clear() | contains?(Object o) | get?(int index) | indexOf(Object O) |isEmpty?() listIterator?() | remove?(int index) | remove?(Object o) | removeAll?(Collection c) | removeIf?(Predicate filter) | removeRange?(int fromIndex, int toIndex) |size?() toArray()

Vector Class

The Vector class implements a growable array of objects. Vectors fall in legacy classes, but now it is fully compatible with collections. Vector implements a dynamic array which means it can grow or shrink as required. Like an array, it contains components that can be accessed using an integer index. It also maintains an insertion order like an ArrayList. Still, it is rarely used in a non-thread environment as it is synchronized, and due to this, it gives a poor performance in adding, searching, deleting, and updating its elements. If the increment is specified, Vector will expand according to it in each allocation cycle. If the increment is not specified, then the vector’s capacity gets doubled in each allocation cycle. It is recommended to use the Vector class in the thread-safe implementation only. If you don't need to use the thread-safe implementation, you should use the ArrayList, the ArrayList will perform better in such case.

Vector is synchronized. Vector is a legacy class. Vector increases its size by doubling the array size. Vector list is thread-safe as its every method is synchronized.

LinkedList Class

LinkedList is an implementation of the List and Deque interfaces. 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.  When our frequently used operation is adding or removing elements in the middle of the List, LinkedList is the best class to use. Because we don’t need to do more shifts to add or remove elements at the middle of the list. When our frequently used operation is retrieving elements from list, then LinkedList is the worst choice. Because LinkedList supports only sequential access, does NOT support random access.

LinkedList uses a doubly linked list. LinkedList is efficient for manipulation. LinkedList is better to manipulate data. LinkedList does not provide random access. LinkedList takes more memory overhead, as it stores the object as well as the address of that object.

Iterator interface

A Java Cursor is an Iterator, which is used to iterate or traverse or retrieve a Collection or Stream object’s elements one by one. Iterators in Java are used in the Collection framework to retrieve elements one by one. It is a universal iterator as we can apply it to any Collection object. By using Iterator, we can perform both read and remove operations. It is an improved version of Enumeration with the additional functionality of removing an element. Iterator must be used whenever we want to enumerate elements in all Collection framework implemented interfaces like Set, List, Queue, Deque, and all implemented classes of Map interface. The iterator is the only cursor available for the entire collection framework. An iterator object can be created by calling the iterator() method present in the Collection interface. Iterator itr = c.iterator(); 1. hasNext(): Returns true if the iteration has more elements. 2. next(): Returns the next element in the iteration. It throws NoSuchElementException if no more element is present. 3. remove(): Removes the next element in the iteration. This method can be called only once per call to next().

The Iterator traverses the elements in the forward direction only. The Iterator can traverse legacy and non-legacy elements. The Iterator can be used in List, Set, and Queue. The Iterator can only perform remove operation while traversing the collection. The Iterator is fail-fast. The Iterator is slower than Enumeration. The Iterator can perform remove operation while traversing the collection.

ListIterator interface

ListIterator is one of the four java cursors. It is a java iterator that is used to traverse all types of lists including ArrayList, Vector, LinkedList, Stack, etc. There is no current element in ListIterator. Its cursor always lies between the previous and next elements. The previous() will return to the previous elements and the next() will return to the next element. Therefore, for a list of n length, there are n+1 possible cursors.

ListIterator traverses the elements in backward and forward directions both. ListIterator can be used in List only. ListIterator can perform add, remove and set operation while traversing the collection.

Enumeration interfaces

Predefined interfaces, whose object is used for retrieving the data from collections framework variable( like Stack, Vector, HashTable etc.) in a forward direction only and not in the backward direction. This interface has been superceded by an iterator. Enumeration is Synchronized. Enumeration can traverse only legacy elements. Enumeration is not fail-fast. Enumeration is faster than Iterator. It does not support adding, removing, or replacing elements. The Enumeration can perform only traverse operation on the collection.

Stack class

Java Stack class is an important part of the Java Collection framework and is based on the basic principle of last-in-first-out. In other words, the elements are added as well as removed from the rear end. The action of adding an element to a stack is called push while removing an element is referred to as pop. Below are the various methods provided by this class:

A stack is a special area of computer's memory that stores temporary variables created by a function. In stack, variables are declared, stored, and initialized during runtime.

The class is based on the basic principle of last-in-first-out push(Object element) - Adding Elements

peek() - To retrieve or fetch the first element of the Stack or the element present at the top of the Stack. The element retrieved does not get deleted or removed from the Stack.

pop() - To remove element, The element is popped from the top of the stack and is removed from the same. search(Object element) -It determines whether an object exists in the stack. If the element is found, It returns the position of the element from the top of the stack. Else, it returns -1.

empty (): This method finds that whether the stack is empty or not.

search (): This method searches items in the stack.

Queue Interface

Java Queue interface orders the element in FIFO(First In First Out) manner. In FIFO, first element is removed first and last element is removed at last. It is used to keep the elements that are processed in the First In First Out (FIFO) manner. It is an ordered list of objects, where insertion of elements occurs at the end of the list, and removal of elements occur at the beginning of the list. Being an interface, the queue requires, for the declaration, a concrete class, and the most common classes are the LinkedList and PriorityQueue in Java. Implementations done by these classes are not thread safe. If it is required to have a thread safe implementation, PriorityBlockingQueue is an available option.

boolean add(object)-It is used to insert the specified element into this queue and return true upon success.

boolean offer(object)-It is used to insert the specified element into this queue.

Object remove()-It is used to retrieves and removes the head of this queue.

Object poll()-It is used to retrieves and removes the head of this queue, or returns null if this queue is empty.

Object element()-It is used to retrieves, but does not remove, the head of this queue.

Object peek()-It is used to retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

PriorityQueue class

The PriorityQueue class provides the facility of using queue. But it does not orders the elements in FIFO manner. It inherits AbstractQueue class. PriorityQueue is also class that is defined in the collection framework that gives us a way for processing the objects on the basis of priority. It is already described that the insertion and deletion of objects follows FIFO pattern in the Java queue. However, sometimes the elements of the queue are needed to be processed according to the priority, that's where a PriorityQueue comes into action.

BlockingQueue Queue

BlockingQueue Queue is an ordered list of objects where insertions take place at the rear end of the list and deletion of elements takes place from the front end. Therefore, it is also said that Queue is based on FIFO ( First-In-First-Out ) principle.

BlockingQueue is an interface used in Java that can extend the Queue. It provides concurrency in various queue operations like retrieval, insertion, deletion, etc.

BlockingQueue is a queue that additionally supports operations that wait for the queue to become non-empty when we are trying to retrieve an element, and wait for the space to be empty when an element is to be inserted in the queue. 

A BlockingQueue may have a remainingCapacity beyond which we cannot insert any element without blocking.

A BlockingQueue does not accept null elements. If we try to add a null value the implementation throws a NullPointerException.

All the implementations related to the BlockingQueue are thread-safe. All the methods achieve their events using internal locks or other forms of concurrency control.

The syntax of BlockingQueue is: public interface BlockingQueue extends Queue

HashCode

The hashCode() is a method that returns an integer hash code. The hashCode() method returns the same integer number if two keys (by calling equals() method) are identical. However, it is possible that two hash code numbers can have different or the same keys. If two objects do not produce an equal result by using the equals() method, then the hashcode() method will provide the different integer result for both the objects.

Why we override equals() method? The equals method is used to check whether two objects are the same or not. It needs to be overridden if we want to check the objects based on the property.

For example, Employee is a class that has 3 data members: id, name, and salary. However, we want to check the equality of employee object by the salary. Then, we need to override the equals() method.

How to synchronize List, Set and Map elements? public static List synchronizedList(List l){} public static Set synchronizedSet(Set s){} public static SortedSet synchronizedSortedSet(SortedSet s){} public static Map synchronizedMap(Map m){} public static SortedMap synchronizedSortedMap(SortedMap m){}

How to make Java ArrayList Read-Only? We can obtain java ArrayList Read-only by calling the Collections.unmodifiableCollection() method. When we define an ArrayList as Read-only then we cannot perform any modification in the collection through add(), remove() or set() method.

How to remove duplicates from ArrayList?

Using HashSet: By using HashSet we can remove the duplicate element from the ArrayList, but it will not then preserve the insertion order.

Using LinkedHashSet: We can also maintain the insertion order by using LinkedHashSet instead of HashSet. The Process to remove duplicate elements from ArrayList using the LinkedHashSet:

Copy all the elements of ArrayList to LinkedHashSet. Empty the ArrayList using clear() method, which will remove all the elements from the list. Now copy all the elements of LinkedHashset to ArrayList. How to reverse ArrayList? Iterator i2 = list.iterator(); Collections.reverse(list); How to sort ArrayList in descending order? Comparator cmp = Collections.reverseOrder(); Collections.sort(list,cmp);

Why Collection extend the Cloneable and Serializable interfaces? The Collection interface in Java specifies a group of objects called elements. The maintainability and ordering of elements is completely dependent on the concrete implementations provided by each of the Collection. Thus, there is no use of extending the Cloneable and Serializable interfaces.

Why Map doesn’t extend the Collection Interface?

The Map interface in Java follows a key/value pair structure whereas the Collection interface is a collection of objects which are stored in a structured manner with a specified access mechanism. The main reason Map doesn’t extend the Collection interface is that the add(E e) method of the Collection interface doesn’t support the key-value pair like Map interface’s put(K, V) method. It might not extend the Collection interface but still is an integral part of the Java Collections framework.

Use any class as a Map key Yes, any class can be used as Map Key as long as the following points are considered:

The class overriding the equals() method must also override the hashCode() method The class should adhere to the rules associated with equals() and hashCode() for all instances The class field which is not used in the equals() method should not be used in hashCode() method as well The best way to use a user-defined key class is by making it immutable. It helps in caching the hashCode() value for better performance. Also if the class is made immutable it will ensure that the hashCode() and equals() are not changing in the future.

The class must be declared as final (So that child classes can’t be created) Data members in the class must be declared as private (So that direct access is not allowed) Data members in the class must be declared as final (So that we can’t change the value of it after object creation) A parameterized constructor should initialize all the fields performing a deep copy (So that data members can’t be modified with object reference) Deep Copy of objects should be performed in the getter methods (To return a copy rather than returning the actual object reference) No setters (To not have the option to change the value of the instance variable)

Working of HashMap

HashMap contains an array of the nodes, and the node is represented as a class. It uses an array and LinkedList data structure internally for storing Key and Value. There are four fields in HashMap.

int hashvalue key value next

equals(): It checks the equality of two objects. It compares the Key, whether they are equal or not. It is a method of the Object class. It can be overridden. If you override the equals() method, then it is mandatory to override the hashCode() method. hashCode(): This is the method of the object class. It returns the memory reference of the object in integer form. The value received from the method is used as the bucket number. The bucket number is the address of the element inside the map. Hash code of null Key is 0. Buckets: Array of the node is called buckets. Each node has a data structure like a LinkedList. More than one node can share the same bucket. It may be different in capacity.

We use put() method to insert the Key and Value pair in the HashMap. The default size of HashMap is 16 (0 to 15).

When we call the put() method, then it calculates the hash code of the Key . To store the Key in memory, required to calculate the index. Calculating Index Index minimizes the size of the array. The Formula for calculating the index is:

Index = hashcode(Key) & (n-1)

Based on index value where the Key and value will store in HashMap.

Hash Collision This is the case when the calculated index value is the same for two or more Keys. If same index value got

In this case, equals() method check that both Keys are equal or not. If Keys are same, replace the value with the current value. Otherwise, connect this node object to the existing node object through the LinkedList. Hence both Keys will be stored at same index

get() method in HashMap get() method is used to get the value by its Key. It will not fetch the value if you don't know the Key. When get(K Key) method is called, it calculates the hash code of the Key.

It generates the hash code as 2657860. Now calculate the index value of 2657860 by using index formula. The index value will be 4, as we have calculated above. get() method search for the index value 4. It compares the first element Key with the given Key. If both keys are equal, then it returns the value else check for the next element in the node if it exists.

How Initial Capacity And Load Factor Affect Performance Of HashMap? Whenever HashMap reaches its threshold, rehashing takes place. Rehashing is a process where new HashMap object with new capacity is created and all old elements (key-value pairs) are placed into new object after recalculating their hashcode. This process of rehashing is both space and time consuming. So, you must choose the initial capacity, by keeping the number of expected elements (key-value pairs) in mind, so that rehashing process doesn’t occur too frequently.

You also have to be very careful while choosing the load factor. According to HashMap doc, the default load factor of 0.75f always gives best performance in terms of both space and time. For example,

If you choose load factor as 1.0f, then rehashing takes place after filling 100% of the current capacity. This may save the space but it will increase the retrieval time of existing elements. Suppose if you choose load factor as 0.5f, then rehashing takes place after filling 50% of the current capacity. This will increase the number of rehashing operations. This will further degrade the HashMap in terms of both space and time.

So, you have to be very careful while choosing the initial capacity and load factor of an HashMap object. Choose the initial capacity and load factor such that they minimize the number of rehashing operations. Linked List are linear data structures 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. In Java, LinkedList class implements the list interface. In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

What is Node?

The main component of the LinkedList is a Node. In java, internally, java.util.LinkedList class contains a private static class Node.

Structure of Node Class 1. item: to store the value 2. next: reference to the next node. In other words, it stores the address of the next node. 3. previous: reference to the previous node. In other words, it stores the address of the previous node.

*****How add() method works internally in LinkedList?

As we know that elements in LinkedList are added in a sequential manner. There are many overloaded methods of add() method present in the LinkedList class. But we are focusing on one method add(int index, E element). To understand it, first, we need to learn about the linkLast() method that is also present in LinkedList class. *****LinkedList Internal Implementation - first and last Node

There are two different variables first and last in the LinkedList class to hold the reference of the first and last node as shown below.

*****LinkedList Internal Implementation - linkLast() method

linkLast() method is used to add the element at the last position of the list. The last node before the insertion of the new node is now at the second last position after the addition of the new node. As a result, the newly inserted node previous will contain the reference to the second last node whereas the second last node next will contain the reference to the newly inserted last node.

if we insert the very first element in the LinkedList then both the first and last point to the new Node. If LinkedList already contains the elements then a new element is inserted at the end of the list. l will hold the reference to the node that was in the last position before the insertion of the new element.

(last = newNode;) indicates last will now hold the reference to the newly created Node.

(l.next = newNode;) The node that was the last node before inserting the new element at the end, is now at the second last place. Its next will contain the reference to the newly created node i.e last node.

****add(int index, E element) method The add(int index, E element) is used to insert the specified element at the specified position in the list. checkPositionIndex(index) is used to tell if the argument is the index of a valid position for an add operation. If (index == size) then linkLast() method is called.

One of the parameter is node(index) in the method call to linkBefore(element, node(index));. node(index) returns the Node(non-null) at the specified element index.

inkBefore() method code is similar to the linkLast() method. The only difference between them is that we are passing an extra node in the method parameter. Also, we have to adjust the next and previous references accordingly. The code for the linkBefore() method is given below:

****How remove() method works internally in Java?

Similar to the add() method in LinkedList there exists unlinkFirst() and unlinkLast() methods for remove() method. There are many overloaded methods of remove() present in the LinkedList class. But we will look into the simple remove() method as given below:

In the above code, removeFirst() is calling unlinkFirst() method internally. It will assign the null values to the first node next reference and element item. Then the second element becomes the new head. Its previous reference becomes null.

****How get() method works internally in Java?

Similar to the add() method in LinkedList there exists getFirst() and getLast() methods. The get() method code is as follow: Unlike add() or remove() methods there are no overloaded methods for get() in LinkedList class. We have already discussed the node(index) method above. It will return the (non-null) node at the specified element index. item attribute of the Node will be returned by the get(index) method.

https://javahungry.blogspot.com/2021/01/internal-implementation-of-linkedlist.html Working of Linked List Linked List are linear data structures 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. In Java, LinkedList class implements the list interface. In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

The node contains the following properties: 1. item: to store the value 2. next: reference to the next node. In other words, it stores the address of the next node. 3. previous: reference to the previous node. In other words, it stores the address of the previous node.

As we know that elements in LinkedList are added in a sequential manner. There are many overloaded methods of add() method present in the LinkedList class

How add() method works internally in LinkedList?

As we know that elements in LinkedList are added in a sequential manner. There are many overloaded methods of add() method present in the LinkedList class. But we are focusing on one method add(int index, E element). To understand it, first, we need to learn about the linkLast() method that is also present in LinkedList class.

There are two different variables first and last in the LinkedList class to hold the reference of the first and last node as shown below. ------------------------------------------------ LinkedList Internal Implementation - first and last Node There are two different variables first and last in the LinkedList class to hold the reference of the first and last node as

linkLast() method is used to add the element at the last position of the list. The last node before the insertion of the new node is now at the second last position after the addition of the new node. As a result, the newly inserted node previous will contain the reference to the second last node whereas the second last node next will contain the reference to the newly inserted last node.

(last = newNode;) indicates last will now hold the reference to the newly created Node.

(l.next = newNode;) The node that was the last node before inserting the new element at the end, is now at the second last place. Its next will contain the reference to the newly created node i.e last node.

The add(int index, E element) is used to insert the specified element at the specified position in the list. checkPositionIndex(index) is used to tell if the argument is the index of a valid position for an add operation. If (index == size) then linkLast() method is called.

One of the parameter is node(index) in the method call to linkBefore(element, node(index));. node(index) returns the Node(non-null) at the specified element index.

linkBefore() method code is similar to the linkLast() method. The only difference between them is that we are passing an extra node in the method parameter. Also, we have to adjust the next and previous references accordingly. The code for the linkBefore() method is given below:

Similar to the add() method in LinkedList there exists unlinkFirst() and unlinkLast() methods for remove() method. There are many overloaded methods of remove() present in the LinkedList class. But we will look into the simple remove() method as given below:

How remove() method works internally in Java?

In the above code, removeFirst() is calling unlinkFirst() method internally. It will assign the null values to the first node next reference and element item. Then the second element becomes the new head. Its previous reference becomes null.

TreeSet and TreeMap does not allow to insert heterogeneous objects because it must compare objects to determine sort order. TreeSet is not synchronized.