Java, being a statically-typed language, often requires explicit type conversions and careful handling of primitive types and their corresponding wrapper classes. However, certain features introduced in later versions of Java, particularly in the java.lang package, aim to simplify the process of working with primitive types and their object counterparts. In this article, we’ll delve into four such features: autoboxing, auto-unboxing, widening, and varargs methods.
Autoboxing and Auto-Unboxing
Autoboxing and auto-unboxing were introduced in Java 5 as a means to automatically convert between primitive types and their corresponding wrapper classes (Integer, Double, Boolean, etc.) without explicit intervention from the programmer.
Autoboxing
Autoboxing refers to the automatic conversion from a primitive type to its corresponding wrapper object by the compiler.
For example, when we write: Integer I = 10, the compiler converts the int to Integer automatically through autoboxing.
After compilation, the above line becomes: Integer I = Integer.valueOf(10);. Internally, autoboxing is always implemented using .valueOf().
So, Integer I = Integer.valueOf(10); is what the compiler executes at the time of autoboxing.
Auto-Unboxing
AutoUnboxing refers to the automatic conversion of a wrapper object to its corresponding primitive type by the compiler.
For example:
Java
IntegerI = newInteger(10);inti = I; // Compiler converts Integer to int automatically by autounboxing
After compilation, the above line becomes:
Java
inti = I.intValue();
Internally, the autounboxing concept is implemented using xxxValue() methods.
The conversion can be summarized as follows:
Primitive value ———– Autoboxing[valueOf()] ——————-> Wrapper object
Wrapper object ————- AutoUnboxing[xxxValue()] —————-> Primitive value
Here’s an example demonstrating autoboxing and autounboxing in code:
Integer X = 10;: This line creates an Integer object X with the value 10.
Integer Y = X;: Here, a reference to the same Integer object that X points to is assigned to Y.
X++;: This increments the value of X by 1. Since Integer objects are immutable, a new Integer object with the value 11 is created, and X now points to this new object.
System.out.println(X);: Prints the value of X, which is 11.
System.out.println(Y);: Prints the value of Y, which still holds the original value of X, i.e., 10.
System.out.println(X == Y);: Compares the references of X and Y, which are pointing to different objects after the increment operation, hence it returns false.
Note: All wrapper classes are immutable, meaning once we create a wrapper object, we cannot modify its value. If we attempt to perform any changes to it, a new object will be created instead. This is why a new Integer object with the value 11 is created when we increment X.
Few more examples:
Example 1
Java
Integerx = newInteger(10); // x => 10Integery = newInteger(10); // y => 10System.out.println(x == y); // Output: false
x and y are referencing different Integer objects, even though they hold the same value 10. Therefore, the comparison using == returns false.
Example 2
Java
Integerx = newInteger(10); // x => 10Integery = 10; // y => 10System.out.println(x == y); // Output: false
x refers to a new Integer object with the value 10, while y refers to an Integer object from the Integer cache. Though they hold the same value, they are different objects, hence false is printed.
Both x and y refer to the same Integer object with the value 10. In this case, they are referencing the same cached object, so the comparison using == returns true.
Similar to the previous case, x and y reference the same Integer object with the value 100, which is within the range of the Integer cache. Hence, true is printed.
Example 5
Java
Integerx = 1000; // x => 1000Integery = 1000; // y => 1000System.out.println(x == y); // Output: false
The values 1000 are outside the range of the Integer cache (-128 to 127), so new Integer objects are created for both x and y, resulting in false when compared using ==.
To facilitate autoboxing, Java internally maintains a buffer of wrapper objects upon the loading of wrapper classes. This buffer strategy optimizes memory usage by reusing existing objects. When an object is required, the JVM checks if it’s already present in the buffer. If so, the existing object is utilized; otherwise, a new object is created.
The buffer concept is available only within specific ranges for each wrapper type:
Byte: Always available.
Short: Ranges from -128 to 127.
Integer: Ranges from -128 to 127.
Long: Ranges from -128 to 127.
Character: Ranges from 0 to 127.
Boolean: Always available.
See below example usage which demonstrating buffer behavior
Let’s delve into overloading with respect to autoboxing, widening, and varargs, but befor that let’s see what is widening exactly.
Widening refers to the automatic conversion of a smaller data type to a larger data type in the hierarchy. In Java, the widening conversion follows the hierarchy: byte -> short -> char -> int -> long -> float -> double.
We have two overloaded methods m1: one accepts an Integer parameter, and the other accepts a long parameter.
In the main method, we have an int variable x.
When we call m1(x), the int value x undergoes widening to match the long parameter, as widening is preferred over autoboxing.
Therefore, the output will be “Widening”.
This happens because widening is applicable from Java 1.0 version and gets priority over autoboxing, which was introduced later in Java 1.5 version.
Varargs Methods
Varargs, short for variable-length arguments, allow methods to accept a variable number of arguments of a specified type. This feature simplifies the creation of methods that operate on a variable number of inputs.
Syntax
The syntax for declaring a varargs parameter is to use an ellipsis (...) after the parameter type.
We have two overloaded methods m1: one accepts a varargs parameter of type Int, and the other accepts an Integer parameter.
In the main method, we have an int variable x.
When we call m1(x), the int value x undergoes autoboxing to match the Integer parameter, as autoboxing is preferred over varargs methods.
Therefore, the output will be “Autoboxing”.
This happens because, while resolving overloaded methods, the compiler gives priority to widening, then autoboxing, and finally varargs methods. Since autoboxing has a higher priority than varargs, it gets selected in this scenario.
Order Priority-> 1. Widening 2. Autoboxing 3. var-arg method
Compilation Error (CE)
In some cases compiler error occurs, Let’s see why we face a compilation error (CE).
Compilation Error: m1(java.lang.Long) in Test cannot be applied to (int)
Here, compiler error occurs because there’s no direct conversion path from int to Long involving both autoboxing and widening.
In the m1 method, the parameter type is Long.
In the main method, an int variable x is declared and initialized with the value 10.
When calling m1(x), the compiler attempts to find a suitable method to match the argument x, which is of type int.
In Java, there are no implicit conversions from int to Long that involve both autoboxing and widening. Although int can be widened to long and then autoboxed to Long, this kind of conversion sequence is not supported by the compiler.
Therefore, the compiler reports a compilation error because there is no suitable overload of m1 that accepts an int argument directly or through a sequence of implicit conversions involving autoboxing and widening.
To resolve the error, you can either change the type of x to Long or provide a suitable overload of m1 that accepts an int argument or its equivalent types.
This limitation arises because after widening, autoboxing is not implemented in Java. However, after autoboxing, widening is internally implemented. This means that widening followed by autoboxing is not supported directly, leading to the compilation error.
The output will be “Object version”. As we know autoboxing then widening is possible in java
Explanation:
The method m1(Object o) expects a parameter of type Object.
In the main method, we have an int variable x.
When m1(x) is called, autoboxing is applied to convert int to Integer.
Then, widening is applied to convert Integer to Object, as widening is applicable in Java.
Therefore, the method m1(Object o) is invoked with the argument Integer, and the output will be “Object Version”.
Additionally, the statements:
Java
Objecto = 10; // is perfectly validNumbern = 10; // is also perfectly valid
These statements are valid because of autoboxing. In Java, autoboxing allows automatic conversion between primitive types and their corresponding wrapper classes (e.g., int to Integer, double to Double, etc.). Since Integer is a subclass of Object, and Integer is a subclass of Number, the assignments Object o = 10; and Number n = 10; are perfectly valid.
Conclusion
Autoboxing, auto-unboxing, widening, and varargs methods are features introduced in Java to simplify the handling of primitive types and method parameterization. They enhance code readability, reduce boilerplate, and provide more flexibility in method invocation. However, it’s essential to understand their implications and usage patterns to leverage them effectively in Java programming.
In Java programming, the java.lang package plays a pivotal role, containing fundamental classes and interfaces that are automatically imported into every Java program. Among these classes, the wrapper classes stand out as essential components that bridge the gap between primitive data types and objects. In this article, we delve into the nuances of wrapper classes, exploring their significance, usage, and practical applications within the Java ecosystem.
What are Wrapper Classes?
In Java, data types can be classified into two categories: primitive types (such as int, double, boolean) and reference types (objects). While primitive types offer efficiency and simplicity, they lack the ability to participate in object-oriented paradigms directly. Wrapper classes address this limitation by providing an object representation for each primitive type, allowing them to be treated as objects.
Imagine a scenario where you need to store primitive data types (like int, char, boolean) within collections, pass them as arguments to methods expecting objects, or perform operations that leverage object-oriented features. This is where wrapper classes come to the rescue! They essentially “wrap” primitive data types into objects, bestowing upon them the power of object-oriented capabilities.
Wrapper classes’ main objective is to wrap primitives into object form so that we can handle primitives just like objects.
Several utility methods are required for primitives.
Almost all wrapper classes contain two constructors: one that can take corresponding primitives as arguments and another one that can take a string as an argument.
Note: If the string argument does not represent a number, then we will get a NumberFormatException. For example, Integer I = new Integer("ten"); will result in a NumberFormatException.
Java
IntegerI = newInteger("ten"); // Resulting in a NumberFormatException
List of Wrapper Classes
Wrapper classes serve the purpose of encapsulating primitive data types into object form, facilitating the handling of primitives as objects. Each wrapper class provides constructors tailored to accept either the corresponding primitive type or a string representation.
Note: Character class contains only one constructor which can take only one argument, that is, char and does not take a String constructor.
Boolean
Constructor Arguments: boolean or String
Boolean class contains two constructors which can take boolean and String arguments, that is, boolean and String constructor. but there are some twists, Let’s see it.
Case 1: When passing boolean primitives, only allowed values are true and false where case is important and content also very important.
Case 2: When passing a String as an argument, case and content both are not important. If the content is a case-insensitive String of “true”, then it is treated as true; otherwise, it is treated as false.
Here’s the breakdown of the utility methods for wrapper classes:
1. valueOf()
Every wrapper class except the Character class contains a public static method valueOf(String s) which can take a String as an argument to create the corresponding wrapper class.
Every integral type wrapper class (Byte, Short, Integer, Long) contains the following valueOf method to create a wrapper object for the specified radix string.
Java
publicstatic wrapper valueOf(String s, int radix);
Note: Radix is the parameter that specifies the number system to be used. For example, binary = 2, octal = 8, hexadecimal = 16, etc. The allowed range of radix is 2 to 36.
Every wrapper class including the Character class contains a public static method valueOf(primitive p) to create a wrapper object for the given primitive.
We can use xxxValue() methods to get the primitive value from a given wrapper object.
Every number type wrapper class (Integer, Byte, Short, Long, Float, Double) contains the following methods to get primitive values for a given wrapper object:
byteValue():
Returns the byte primitive value of the wrapper object.
Method Signature: public byte byteValue()
shortValue():
Returns the short primitive value of the wrapper object.
Method Signature: public short shortValue()
intValue():
Returns the int primitive value of the wrapper object.
Method Signature: public int intValue()
longValue():
Returns the long primitive value of the wrapper object.
Method Signature: public long longValue()
floatValue():
Returns the float primitive value of the wrapper object.
Method Signature: public float floatValue()
doubleValue():
Returns the double primitive value of the wrapper object.
This method allows us to obtain the boolean primitive value from the given Boolean object.
In total, there are 38 (6*6 + 1 + 1) xxxValue() methods present.
Wrapper Object ———————— xxxValue() ———————-> Primitive Value
3. parseXxx()
We can use parseXxx() methods to convert a String to a primitive.
String ——————- parseXxx() ———————-> primitive
Form 1:
Every wrapper class except the Character class contains the following parseXxx() method to find the primitive for the given String object.
Java
publicstatic primitive parseXxx(String s);
Java
inti = Integer.parseInt("10");doubled = Double.parseDouble("10.5");booleanb = Boolean.parseBoolean("true");
Form 2:
Every integer wrapper class (Byte, Short, Integer, Long) contains the following parseXxx() method to convert a specified radix String to a primitive. The allowed range of radix is 2 to 36.
Java
publicstatic primitive parseXxx(String s, int radix);
Java
inti = Integer.parseInt("1111", 2);System.out.println(i); // Output: 15
4. toString()
We can use toString() to convert a wrapper object or primitive to a String.
Form 1
Every wrapper class contains the following toString() method to convert a wrapper object to a String type.
Java
publicStringtoString();
It is an overriding version of the toString() method in the Object class. Whenever we try to print a Wrapper class reference, internally this toString() method will be called.
This method is particularly useful when you need to convert a primitive value to a String without creating an object of the corresponding wrapper class.
Primitive Value ——————- toString() ———————-> String
Form 3
Integer and Long classes contain the following static toString() method to convert a primitive to a radix String.
Java
publicstaticStringtoString(primitive p, int radix);
This method is particularly useful when you need to convert a primitive value to a String representation in a specific radix (base).
Form 4
Integer and Long wrapper classes contain the following toXxxString() methods to convert a primitive to a String in binary, octal, and hexadecimal form.
These methods allow you to obtain a string representation of the given primitive value in binary, octal, or hexadecimal form. They are particularly useful for formatting output or performing bitwise operations.
Using valueOf(): Converts a primitive value to a wrapper object.
Java
Primitive Value ---------------- valueOf() ----------------> WrapperObject
Primitive Value to String:
Using toString(): Converts a primitive value to a String.
Java
Primitive Value ----------------- toString() --------------------> String
Here we saw various conversions between String, Wrapper Object, and Primitive Value in Java. Each step serves a specific purpose and facilitates flexible data manipulation within the Java ecosystem.
Object ──┬─ String ├─ StringBuffer ├─ StringBuilder ├─ Number ──┬─ Byte │ ├─ Short │ ├─ Integer │ ├─ Long │ ├─ Float │ └─ Double ├─ Boolean ├─ Character └─ Void
Conclusions:
Wrapper classes which are not child classes of Number are Boolean and Character.
Wrapper classes which are not direct child classes of Object are Byte, Short, Integer, Long, Float, Double.
Final wrapper classes are String, StringBuffer, and StringBuilder.
In addition to the String class, all wrapper class objects are also immutable.
Sometimes Void class is also considered a wrapper class.
Void class
It is a final class and is the direct child class of Object. It doesn’t contain any methods and contains only one variable, Void.TYPE.
In general, we can use the Void class in reflection to check whether any method return type is void or not.
Java
if(getMethod("m1").getReturnType() == Void.TYPE)
Void is the class representation of the void keyword in Java.
Conclusion
Wrapper classes in the java.lang package play a crucial role in Java programming, providing a bridge between primitive types and objects. They offer a range of features and utilities, including conversion, nullability, and seamless integration with collections and generics. While wrapper classes enhance the flexibility and expressiveness of Java code, developers should be mindful of their performance implications in certain contexts. By understanding the nuances of wrapper classes, developers can leverage them effectively to write robust and maintainable Java applications.
In conclusion, wrapper classes are integral components of the Java language, empowering developers to work with primitive types in an object-oriented manner. Their versatility and utility make them indispensable in various programming scenarios, enriching the Java ecosystem with enhanced expressiveness and functionality.
In the realm of Java programming, the java.lang.Object class holds a position of utmost importance. It serves as the root of the class hierarchy, making it a foundational element of the Java language. Understanding the Object class is crucial for every Java developer, as it forms the basis for many core concepts and functionalities within the language.
Understanding the java.lang Package
For any Java program, the most commonly required classes and interfaces are grouped together into a separate single package known as the java.lang package. We are not required to import the java.lang package because all classes and interfaces in this package are by default available to all Java classes.
Java Object Class (java.lang.Object)
The most commonly required methods for any Java class are grouped into a single class called the Object class. It is also the root class for any Java class. If any Java class does not extend any other Java class, then it is a direct child class of the Object class; otherwise, it is an indirect child class of the Object class. When it is an indirect child of the Object class, it is multi-level inheritance, not multiple inheritance.
For example, class A extends B i.e., A --> B --> Object. This is multilevel inheritance and not multiple inheritance.
Whether directly or indirectly, Java does not support multiple inheritance with respect to Java classes.
The Object class defines the following 11 methods:
public final void wait() throws InterruptedException
public final native void wait(long ms) throws InterruptedException
public final native void wait(long ms, int ns) throws InterruptedException
public native final void notify()
public native final void notifyAll()
Note: The Object class contains a 12th method, but it is for internal purposes for the JVM: private static native void registerNatives.
toString(): This method is used to get the string representation of an object. If our class does not contain toString(), then the toString() method of the Object class will be executed. The Object class toString() method is: public String toString(){return getClass().getName() + "@" + Integer.toHexString(hashCode());}. For example, classname@hashcode-in-hexadecimal-form, i.e., Student@1888759.
Based on our requirement, we can override toString() in any Java class, and it is highly recommended. For example: public String toString(){return name + "..." + rollno;}.
hashCode(): Based on the object’s address, the JVM will generate a unique number called the hash code of that object. It doesn’t mean the object’s address is the hash code of that object. The JVM will generate a hash code for hashing-related data structures like HashTable, HashMap, HashSet to store objects into buckets based on their hash codes so that searching for that object becomes very efficient. As we know, the number one searching algorithm is hashing, and its time complexity is O(1).
Java
publicnativeinthashCode();
We can override the hashCode() method of the Object class according to our requirement. Suppose we want to override hashCode() in the Student class; then, it will return the unique roll number of the student. This is the proper way to implement the hashCode method.
equals(): For example, obj1.equals(obj2).
If our class doesn’t contain equals(), then the equals() method of the Object class will be executed. The equals() method of the Object class is built for reference comparison, not for content comparison.
For example:
Java
Students1 = newStudent("amol", 101); Students2 = newStudent("softAai", 102); Students3 = newStudent("amol", 101); Students4 = s1;System.out.println(s1.equals(s2)); // false, as the Object class equals() is built for reference comparisonSystem.out.println(s1.equals(s3)); // false, even though the content is equal, the references are differentSystem.out.println(s1.equals(s4)); // true, as both references are pointing to the same object, meaning the references are equal
Now, based on our requirement, we can override the equals() method of the Object class for content comparison into our own class. But while doing this, we need to take care of the following things:
Determine whether we are comparing the whole content (student name, roll number) or only specific content (only roll number), and implement our equals() accordingly.
Ensure that if we pass a different object, it will not raise a ClassCastException, and if we pass null, it won’t raise a NullPointerException. In both cases, we need to handle them by returning false.
In the case of Strings
Java
Strings1 = newString("softAai");Strings2 = newString("softAai");System.out.println(s1 == s2); // falseSystem.out.println(s1.equals(s2)); // true// In the case of StringBuffer:StringBuffersb1 = newStringBuffer("softAai");StringBuffersb2 = newStringBuffer("softAai");System.out.println(sb1 == sb2); // falseSystem.out.println(sb1.equals(sb2)); // false
“==” is built for reference comparison. In the case of the String class, the equals() method is overridden for content comparison. Therefore, even though the objects are different, if the content is the same, equals() returns true. However, for StringBuffer, the equals() method is not overridden for content comparison, so if the objects are different, equals() returns false even if the content is the same. Its behavior is like the equals() method of the Object class, built for reference comparison.
getClass() is used to get the runtime class definition of an object so that we can access class-level properties like class name, declared methods, and constructors. The signature is: public final Class getClass(). We can utilize the Reflection API for this purpose from java.lang.reflection.*.
The finalize() method is called just before an Object is destroyed by the garbage collector to perform cleanup activities. Once the finalize method completes, the garbage collector automatically destroys that object.
Other methods likewait(), notify(), and notifyAll() are discussed in more detail in multithreading.
We can use these methods for inter-thread communication. The thread that is expecting an update is responsible for calling wait(), which immediately puts the thread into a waiting state. The thread responsible for performing the update can then call notify(). The waiting thread will receive that notification and continue its execution with those updates.
ay to create string objects from different sources such as literals, StringBuffer objects, char arrays, or byte arrays, offering flexibility in string manipulation and handling in Java.
Conclusion
Empower your Java programming journey by mastering the Object class and its myriad functionalities. With our comprehensive guide, you’ll gain a deeper understanding of Java’s foundational concepts and learn how to harness the full potential of the Object class for building robust and scalable applications. Start exploring today and elevate your Java programming skills to new heights!
The java.lang package forms the core foundation of the Java programming language, encompassing fundamental classes and utilities essential for Java development. Within this package, crucial classes like String, StringBuffer, StringBuilder, and various primitive data types reside, offering robust functionalities for string manipulation, mathematical operations, and more. Understanding the nuances of these classes, including their differences, constructors, methods, and best practices, is vital for every Java developer. Moreover, delving into concepts such as immutability, synchronization, and method chaining within the java.lang package provides insights into efficient coding practices and performance optimization strategies.
java.lang packageString Basic Concept in Java
In Java, strings are immutable. Once a string object is created, any attempt to modify it actually results in the creation of a new string object. This immutability means that the original object remains unchanged. Let’s dive into the distinction between immutable and mutable objects.
s ---> softAai | ----> softAaiApps // Here, a new object will be created with those changes, but it doesn't hold any reference in this case. So, by default, it is eligible for garbage collection.
Here clearly shows that, once we create a string object, we can’t perform any changes to the existing object. If we try to perform any change, a new object will be created with those changes. This non-changeable behavior is known as the immutability of strings.
Mutable Objects: StringBuffer
Let’s examine another scenario involving a mutable object, StringBuffer:
Unlike strings, StringBuffer objects in Java are mutable. This means that modifications can be made directly to the existing object without creating new ones.
Here’s what happens:
Initially, sb references the StringBuffer object containing “softAai”.
Upon calling sb.append("Apps"), the content of sb is modified to “softAaiApps” in place.
As a result, when we print sb, it displays “softAaiApps”, reflecting the changes made directly to the original object.
This mutability allows for efficient manipulation of StringBuffer objects, as they can be altered without the overhead of creating new objects.
Understanding “==” Vs .equals() in Java Strings
Let’s explore the comparison between “==” and .equals() methods in Java strings:
//Note: This not outputs1 --> softAais2 --> softAai
In the String class, .equals() is overridden for content comparison. Hence, even though the objects are different, if the content is the same, .equals() returns true.
Here’s what’s happening:
Initially, s1 and s2 both reference separate String objects with the content “softAai”.
When we use “==” to compare s1 and s2, it checks whether they reference the same object in memory. Since s1 and s2 are distinct objects, the result is false.
However, when we use .equals(), it compares the content of the strings. In the case of String objects, the .equals() method is overridden to compare the content of the strings rather than their references. Since the content of s1 and s2 is the same, .equals() returns true.
This distinction is important: “==” checks for reference equality, while .equals() checks for content equality. In the context of strings, .equals() is typically used to compare their actual values.
Exploring “==” vs. .equals() in StringBuffer
By the way, what will happen in StringBuffer? 🤔
Let’s analyze the behavior of “==” and .equals() methods when used with StringBuffer objects:
In Java, “==” compares references, while .equals() typically compares content, but in the case of StringBuffer, .equals() does not compare content; instead, it defers to the default implementation of the equals() method in the Object class, which checks for reference equality.
Here’s what’s happening:
Initially, sb1 and sb2 reference separate StringBuffer objects with the content “durga”.
When we use “==” to compare sb1 and sb2, it checks whether they reference the same object in memory. Since sb1 and sb2 are distinct objects, the result is false.
Similarly, when we use .equals(), it compares the references of sb1 and sb2, not their content. Since they are distinct objects, .equals() returns false.
In StringBuffer, .equals() doesn’t override the behavior inherited from the Object class, so it performs reference comparison rather than content comparison. Thus, even though the content of sb1 and sb2 is the same, .equals() returns false because they refer to different objects in memory.
Understanding the String Constant Pool (SCP)
The String Constant Pool (SCP) in Java is a special memory area within the Java Virtual Machine (JVM) that stores unique string literals (sequence of characters enclosed in double quotation marks (")). When you create a string using double quotes (e.g., "softAai"), Java checks if a string with the same value already exists in the SCP. If it does, the existing string reference is returned; otherwise, a new string is created and added to the SCP.
This behavior helps to conserve memory by avoiding the creation of duplicate string objects with the same value. However, it’s important to note that string objects created using the new keyword (e.g., new String("softAai")) are not added to the SCP, even if they have the same value as existing literals.
Case1: String Created Using ‘new’ Keyword
Java
Strings = newString("softAai");
In this case, two objects are created: one in the heap area and the other in the SCP area. The variable s always points to the object in the heap.
Here’s the breakdown:
In the heap area, a new String object is created with the content “softAai”, and s references this object.
Java
s ==> softAai
In the SCP area, another String object with the content “softAai” is created. However, this object isn’t pointed to by any reference; it exists solely in the SCP.
Java
StringConstantPool (SCP)--------------------------| "softAai" |-------------------------- // not pointing to any reference
So,
In the heap area: s points to the String object containing “softAai”. In the SCP area: There’s a String object with the content “softAai”, but it’s not referenced by any variable.
Case2: String Created Using String Literal (“”)
Java
Strings = "softAai";
In this case, only one object is created in the SCP area, and s is always pointing to that object.
In the heap area, nothing is created.
In the SCP area:
Java
StringConstantPool (SCP)--------------------------| "softAai" |--------------------------s ==> softAai // here 's' points to the String object containing "softAai"
A String object with the content “softAai” is created. s directly references this object.
In the heap area: No new objects are created because string literals (here “softAai”) are directly stored in the SCP. Therefore, there’s no need for a separate object in the heap.
Understanding Object Creation in SCP and Heap
Object creation in the SCP is optional. First, it will check if any object is present in SCP with the required content. If an object is already present, the existing object will be reused. If an existing object is not available, then a new object will be created. However, this rule is applicable only for SCP and not for the heap.
GC is not allowed to access the SCP area. Hence, even though an object doesn’t contain a reference variable, it is not eligible for GC if it is present in the SCP area. All SCP objects will be destroyed at the time of JVM shutdown.
Let’s explore the nuances of object creation in the String Constant Pool (SCP) and the heap, along with garbage collection considerations:
s1 and s2 refer to separate String objects with the content “softAai”.
In the SCP area:
Java
s3, s4 ==> softAai
s3 and s4 both refer to the same String object containing “softAai”
Here Total 3 objects created (2 in heap, 1 in SCP)
Note: Whenever we use the new operator, a new object will be created in the heap area. Hence, there may be existing two objects in the heap area but not in SCP. That means duplicate objects are possible in the heap area but not in SCP.
s1 ==> softAai // With the new operator, a new object will be created in the heap area and one in SCP. ==> softAaiApps // Due to runtime change like .concat(), a new object will be created with those new changes.s2 ==> softAaiBlogss1 ==> softAaiJobs // As reference reassignment.
s1 initially refers to a String object with the content “softAai”.
After s1.concat("Apps"), a new object “softAaiApps” is created due to the immutable nature of strings.
s2 refers to a String object “softAaiBlogs” created by concatenating “softAai” with “Blogs”.
Finally, s1 is reassigned to a new object “softAaiJobs” after concatenating “Jobs”.
In the SCP area:
Java
==> softAai // With the new operator, a new object will be created in the heap area and one in SCP, not holding any reference here.==> Apps // This is a string constant, thus created in SCP.==> Blogs==> Jobs
Objects “softAai”, “Apps”, “Blogs”, and “Jobs” are created due to string literals and stored in the SCP.
Total 8 objects are created (4 in heap and 4 in SCP).
Note: For every string constant, one object will be placed in the SCP area. If an object is required to be created due to some runtime operation, that object will be placed only in the heap area, not in SCP.
Understanding String Constructors
Let’s explore the various constructors available in the String class in Java:
String s = new String();
This constructor creates an empty string object with a size of zero.
Example: String s = "";
String s = new String(String literal);
This constructor creates a string object in the heap for the given string literal.
Example: String s = new String("softAai");
String s = new String(StringBuffer sb);
This constructor creates a string object for an equivalent StringBuffer object.
This constructor creates an equivalent string object for the given byte array.
Example:
Java
byte[] b = {100, 101, 102, 103};Strings = newString(b);System.out.println(s); // Output: defg (as a-97, b-98, c-99, d-100, similarly for e, f, g)
Output – defg –> as ASCII Code a corresponds to 97, b corresponds to 98, c corresponds to 99, and d corresponds to 10.
Here, each constructor provides a way to create string objects from different sources such as literals, StringBuffer objects, char arrays, or byte arrays, offering flexibility in string manipulation and handling in Java.
Important Methods of the String Class
Let’s delve into some essential methods provided by the String class in Java:
public char charAt(int index);
This method returns the character at the specified index in the given string.
Note: In general, we can use the equalsIgnoreCase method to validate usernames where case is not important, whereas we can use the equals method to validate passwords where case is important.
public String substring(int begin);
This method returns a substring starting from the specified begin index to the end of the original string.
Note: The length variable is applicable for arrays but not for strings, whereas the length() method is applicable for string objects but not for arrays.
public String replace(char oldCh, char newCh);
This method replaces all occurrences of a specified character oldCh in the string with a new character newCh and returns the resulting string.
In this example, s.indexOf('a') returns 0 because ‘a’ first occurs at index 0 in the string “ababa”. Similarly, s.lastIndexOf('a') returns 4 because ‘a’ last occurs at index 4.
String Object Operations& Memory Allocation
Let’s see how string object operations affect memory allocation in Java:
s1, s3 => softaai -> s1 and s3 both refer to the same String object with the content “softaai”.
s2 => SOFTAAI -> s2 refers to a new String object with the content “SOFTAAI”, as it is generated by the toUpperCase() method.
In the SCP area:
softaai -> Only string literal “softaai” exists
Note: Because of runtime operations, if there is a change in content, then a new object will be created in the heap. If there is no change, then the existing object will be used, and no new object will be created. Whether the object is present in the heap or SCP, the rule is the same for both.
s4 => softaai -> s4 refers to a new String object with the content “softaai”, as it is generated by the toLowerCase() method./h2
s5 => SOFTAAI -> s5 refers to a new String object with the content “SOFTAAI”, as it is generated by the toUpperCase() method.
In short:
String objects in the heap are created dynamically based on operations performed on existing strings.
String objects in the SCP are reused if the content remains the same, but new objects are created if the content changes.
This example demonstrates how string operations can lead to the creation of new string objects in the heap, while the SCP is utilized for storing string literals and reusing existing strings when possible.
String Literal Operations & Memory Allocation
Now, Let’s understand how string literal operations impact memory allocation in Java:
s1, s2, s3 => softaai -> s1, s2, and s3 all refer to the same String object with the content “softaai”.
Because of runtime operations, new objects will be created in the heap area:
In the heap area:
s4 => SOFTAAI -> s4 refers to a new String object with the content “SOFTAAI”, created by the toUpperCase() method.
s5 => softaai -> s5 refers to a new String object with the content “softaai”, created by the toLowerCase() method applied to s4.
In short:
String objects in the SCP are reused if their content remains the same, even when calling toString() on them.
However, runtime operations like toUpperCase() and toLowerCase() create new string objects in the heap, even if the content remains the same.
When comparing strings, using == checks for reference equality, which in this case returns true because s1 and s2 refer to the same string object.
How to Create Our Own Immutable Class
We can create our own immutable class in Java by following principles.
Once we create an object, we can’t perform any changes to that object. If we try to perform any change and there is a change in content, then a new object will be created. If there is no change in the content, then the existing object will be reused. This behavior is known as immutability.
Java
finalpublicclassTest {privatefinalinti;publicTest(inti) {this.i = i; }publicTestmodify(inti) {if (this.i == i) {returnthis; // If content remains the same, return existing object } else {returnnewTest(i); // If content changes, create a new object } }publicintgetValue() {return i; }}//UsageTestt1 = newTest(10);Testt2 = t1.modify(100);Testt3 = t1.modify(10);
In the heap area:
t1, t3 => object(i=10) -> t1 and t3 reference the same object with the value 10.
t2 => object(i=100) -> t2 references a new object with the value 100, as it was modified.
So, once we create a Test object, we can’t perform any changes to the existing object. If we try to perform any change and there is a change in content, then a new object will be created. If there is no change in the content, then the existing object will be reused.
Final vs. Immutability
It’s important to differentiate between the concepts of final and immutability in Java:
final is applicable for variables but not for objects, whereas immutability is applicable for objects but not for variables. By declaring a reference variable as final, we won’t get any immutability nature. Even though the reference variable is final, we can perform any type of change on the corresponding objects, but we can’t perform reassignment for that variable. Hence, final and immutability are different concepts.
Let’s illustrate the difference with an example:
Java
finalStringBuffersb = newStringBuffer("softAai");sb.append("Apps");System.out.println(sb); // Output: softAaiAppssb = newStringBuffer("Blogs"); // Compilation Error: cannot assign a value to final variable sb
Here,
We declare sb as a final variable, so we cannot reassign it to a new object after initialization. However, we can modify the state of the object it references, as StringBuffer objects are mutable.
Although sb is final, the StringBuffer object it references is not immutable. Therefore, appending “Apps” to the StringBuffer is allowed, but reassigning sb to a new StringBuffer object is not.
In conclusion:
Final variable => Valid
Immutable variable => Invalid
Final object => Invalid
Immutable object => Valid
StringBuffer
If content is fixed and won’t change frequently, then it is recommended to use String. If content is not fixed and keeps changing frequently, then it is not recommended to use String because for every change, a new object will be created, and in this case, performance-wise, String is not a good option. To overcome this problem, it is better to use StringBuffer. The main advantage of StringBuffer over String is that all required changes are performed on the existing object only.
Constructors
StringBuffer sb = new StringBuffer();
– Creates an empty string object with a default capacity of 16. When StringBuffer reaches its maximum capacity, then a new StringBuffer object will be created with a newCapacity = (currentCapacity + 1) * 2.
In this example, sb is initialized with the String “softAai”, and its capacity is determined as the length of the String plus 16.
Important Methods of StringBuffer
public int length();
This method returns the number of characters present in the StringBuffer.
public int capacity();
This method returns the total capacity of the StringBuffer, i.e., how many characters it can accommodate.
public char charAt(int index);
This method returns the character located at the specified index in the StringBuffer.
Java
StringBuffersb = newStringBuffer("softAai");System.out.println(sb.charAt(3)); // Output: t
public void setCharAt(int index, char ch);
This method replaces the character located at the specified index with the provided character.
public StringBuffer append(…);
public StringBuffer append(int i)
public StringBuffer append(long l)
public StringBuffer append(char ch)
public StringBuffer append(boolean b)
Here, all above methods are overloaded.
These overloaded methods append various data types or strings to the end of the StringBuffer.
Java
StringBuffersb = newStringBuffer();sb.append("PI Value is : ");sb.append(3.14);sb.append(" It is exactly : ");sb.append(true);System.out.println(sb); // Output: PI Value is : 3.14 It is exactly : true
public StringBuffer insert(int index, ...);
public StringBuffer insert(int index, String s)
public StringBuffer insert(int index, int i)
public StringBuffer insert(int index, double d)
public StringBuffer insert(int index, char ch)
public StringBuffer insert(int index, boolean b)
Here, all methods are overloaded. In the append method, characters are added at the end, whereas in the insert method, characters are added at the specified index.
These overloaded methods insert various data types or strings at the specified index in the StringBuffer.
Every method present in StringBuffer is synchronized, hence only one thread is allowed to operate on a StringBuffer object at a time, which may cause performance problems. To handle this issue, the concept of StringBuilder was introduced in version 1.5.
StringBuffer vs StringBuilder
StringBuilder
Non-Synchronized: Unlike StringBuffer, StringBuilder methods are not synchronized, allowing multiple threads to operate simultaneously on StringBuilder objects.
Not Thread-Safe: Because of its non-synchronized nature, StringBuilder is not inherently thread-safe.
Lower Thread Waiting Time: The absence of synchronization leads to lower thread waiting time, enhancing performance.
Introduced in Java 1.5: StringBuilder was introduced in Java version 1.5.
StringBuffer
Synchronized: StringBuffer methods are synchronized, meaning only one thread is allowed to operate on a StringBuffer object at a time, ensuring thread safety.
Thread-Safe: Due to its synchronized nature, StringBuffer is thread-safe.
Higher Thread Waiting Time: Synchronization can lead to higher thread waiting time, potentially impacting performance.
Introduced in Java 1.0: StringBuffer has been present since the initial release of Java.
It’s essential to note that everything, including methods and constructors, is the same in StringBuffer and StringBuilder, except for the synchronization aspect. StringBuffer has synchronized methods, while StringBuilder does not. This distinction provides developers with options based on their specific requirements: StringBuffer for thread-safe operations and StringBuilder for improved performance in scenarios where thread safety is not a concern.
String vs StringBuffer vs StringBuilder
If the content is fixed and won’t change frequently, then we use the String concept.
If the content is not fixed and keeps changing frequently, and we need thread safety, then we use the StringBuffer concept.
If the content is not fixed and keeps changing frequently, and we don’t need thread safety, then we use the StringBuilder concept.
Method Chaining
Method chaining allows consecutive method calls on an object, where each method call returns the object itself or another object of the same type, enabling a fluent and concise style of coding. This concept is widely used in classes like String, StringBuffer, and StringBuilder, where many methods return the same type as the object. call another method, which forms method chaining. In method chaining, all method calls are executed from left to right.
append("softAai"): The StringBuilder now contains “softAai”.
append("Apps"): “Apps” is appended to the StringBuilder, resulting in “softAaiApps”.
append("Blogs"): “Blogs” is appended, resulting in “softAaiAppsBlogs”.
insert(2,"xyz"): “xyz” is inserted at index 2, resulting in “soxyzftAaiAppsBlogs”.
reverse(): The content of the StringBuilder is reversed, resulting in “sgolBsppAiaAtfzyxos”.
delete(2,10): Characters from index 2 to index 9 (10 is exclusive) are deleted, resulting in “sgaAtfzyxos”.
Finally, this resulting content is printed.
Conclusion
In conclusion, the java.lang package serves as the cornerstone of Java programming, housing indispensable classes and utilities pivotal for everyday development tasks. Mastery of classes like String, StringBuffer, and StringBuilder, coupled with a deep understanding of immutability, synchronization, and method chaining, empowers developers to write efficient, concise, and robust Java code. By leveraging the capabilities offered by the java.lang package and adhering to best practices outlined herein, developers can enhance their productivity, optimize application performance, and craft software solutions that stand the test of time.
Java interfaces are an essential aspect of the Java programming language. They provide a way to achieve abstraction, multiple inheritance, and polymorphism in Java. In this comprehensive guide, we will delve into the intricacies of Java interfaces, covering their definition, purpose, usage, best practices, and examples.
What is a Java Interface?
Any Service Requirement Specification (SRS) is considered an interface. For example, the JDBC API acts as a requirement specification to develop database drivers, and database vendors are responsible for implementing this JDBC API. Servlet API is an SRS, and web server vendors implement it.
From the client’s point of view, an interface is a set of services that are expected. From the service provider’s perspective, an interface is the set of services offered to the client. Hence, an interface is a contract between the client and the service provider. For instance, the Bank ATM GUI Screen serves as a contract between the bank and the customer, with services like withdrawal, mini-statement, and balance inquiry.
Inside an interface, every method is always abstract whether we declare it explicitly or not. Therefore, an interface is considered a 100% pure abstract class. Whenever we implement an interface, we must provide implementations for every method in the java interface. If we are unable to do so, we declare the implementing class as abstract since it doesn’t contain all method implementations. Additionally, we need to define methods as public so that the next level child class can provide implementations for those methods.
Defining a Java Interface
Java interfaces are defined using the interface keyword followed by the interface name. Here’s an example of a simple interface declaration:
Java
interfaceAnimal {voideat();voidsleep();}
In this example, the Animal interface defines two abstract methods: eat() and sleep(). Any class that implements the Animal interface must provide implementations for these methods.
Implementing Java Interface
To implement an interface in Java, a class uses the implements keyword followed by the name of the interface. Here’s an example of a class implementing the Animal interface:
Java
classDogimplementsAnimal {publicvoideat() {System.out.println("Dog is eating"); }publicvoidsleep() {System.out.println("Dog is sleeping"); }}
In this example, the Dog class implements the Animal interface by providing implementations for the eat() and sleep() methods.
When comparing “extends” and “implements”:
a) A class can extend only one class at a time, but an interface can extend any number of interfaces. For example:
Java
interfaceA {}interfaceB {}interfaceCextendsA, B {}
b) A class can extend another class and implement any number of interfaces. For instance:
Java
classAextendsBimplementsC, D, E {}
c) An interface never implements another interface or interfaces; it only extends interfaces. Therefore, the statement “interface A implements B” is incorrect.
Consider the following scenarios:
X extends Y: Both X and Y can be either classes or interfaces.
X extends Y, Z: X, Y, and Z should be interfaces.
X implements Y, Z: X should be a class, and Y, Z should be interfaces.
X extends Y implements Z: X and Y are classes, and Z is an interface.
X implements Y extends Z: This would result in a compile error because “extends” must be specified before “implements.”
Java Interface Methods
Every method present in java interface is always public and abstract, whether declared explicitly or not. Hence, inside an interface, the following method declarations are equivalent:
To define constant values at the requirement level, we use variables inside an interface. Every variable inside an interface is always public, static, and final, regardless of whether we explicitly declare these modifiers.
public: This modifier is used to make the variable available to every implementation class.
static: This modifier allows access to the variable without needing an existing object of the implementing class.
final: This modifier ensures that if one implementation class changes the value, all other implementation classes will be affected. To prevent this, every interface variable is declared as final.
Hence, the following declarations are equivalent inside an interface:
As every interface variable is public, static, and final, we cannot declare interface variables with the following modifiers:
private, protected, transient, volatile.
It is mandatory to initialize interface variables at the time of declaration; otherwise, we will encounter a compilation error. For example:
Java
interfaceInterf {intx; // CE: = expected.}
Inside a class implementing an interface, we can access interface variables, but we cannot modify them. Attempting to do so will result in a compilation error. For example:
Java
interfaceInterf {intx = 10;}classTestimplementsInterf {publicstaticvoidmain(Stringargs[]) { x = 777; // CE: cannot assign a value to final variable xSystem.out.println(x); }}
However, if we declare int x = 777; instead of x = 777;, it is perfectly valid because it acts like a local variable and not an interface variable.
Java Interface Naming Conflicts
Method Naming Conflicts:
When dealing with method naming conflicts in interfaces, the resolution depends on various factors including method signature, return type, and argument types.
Same Signature, Same Return Type
If two interfaces contain methods with the same signature and return type, then in the implementing class, we have to provide implementation for only one method.
Java
interfaceLeft {publicvoidm1();}interfaceRight {publicvoidm1();}classTestimplementsLeft, Right {publicvoidm1() {}}
Same Name, Different Argument Types (Overloaded Methods)
If two interfaces contain methods with the same name but different argument types, then in the implementation class, we have to provide implementation for both methods, and these methods act as overloaded methods.
If two interfaces contain methods with the same method signature but different return types, then it is impossible to implement both interfaces simultaneously. However, in the case of general or covariant return types, it is possible.
Java
interfaceLeft {publicvoidm1();}interfaceRight {publicintm1();}// It is impossible to implement both interfaces having the same method signature but different return types.// In the case of general or covariant return types, it is possible.classTestimplementsLeft, Right {publicvoidm1() {} // Impossiblepublicintm1() {} // Impossible}
When facing method naming conflicts in interface implementation, understanding the differences in method signatures, return types, and argument types helps determine the appropriate approach for implementation.
Java Interface Variable Naming Conflicts
When dealing with variable naming conflicts in java interfaces, if two interfaces contain variables with the same names, attempting to use the variable directly inside an implementing class can lead to a naming conflict error, resulting in a compilation error.
Java
interfaceLeft {intx = 777;}interfaceRight {intx = 888;}classTestimplementsLeft, Right {publicstaticvoidmain(String[] args) {System.out.println(x); // Compilation Error: reference to x is ambiguous// Solution: Resolve naming conflict using interface namesSystem.out.println(Left.x); // Output: 777System.out.println(Right.x); // Output: 888 }}
To resolve this issue, you can specify the interface name along with the variable name to uniquely identify which interface’s variable you are referring to. By doing so, you can access the variables without ambiguity and prevent compilation errors.
Marker Interface
Definition and Purpose
A marker interface, also known as an ability interface or tag interface, is an interface that does not contain any methods. Instead, it serves as a marker or tag to indicate that objects implementing the interface possess certain abilities or characteristics.
Examples of marker interfaces in Java include Serializable, Cloneable, RandomAccess, and SingleThreadModel. These interfaces indicate that objects implementing them have specific abilities or properties related to serialization, cloning, random access, or single-threaded access.
Java
interfaceSerializable {}
Mechanism(Without having any methods how marker interface provide some ability?)
Even though marker interfaces do not declare any methods, they provide some ability to objects by relying on the internal mechanisms of the Java Virtual Machine (JVM). When an object implements a marker interface, the JVM recognizes this during runtime and provides the associated ability or behavior to that object.
Role of JVM(Why does the JVM provide this ability?)
The JVM is responsible for providing or enabling the abilities associated with marker interfaces. This is done to simplify programming and make Java language usage more straightforward for developers. By delegating certain responsibilities to the JVM, Java programs become more concise, easier to maintain, and less prone to errors.
Custom Marker Interfaces
Yes, we can create our own marker interface, but to do that, we would need to create our own JVM that supports all existing JVM features as well as any additional features we want to implement.
Adapter Class
An adapter class is a simple Java class that implements an java interface but provides empty implementations for all the methods in the interface.
When we implement an interface, we are required to provide implementations for every method in the interface, whether it’s required or not. This can increase the length of code unnecessarily.
Java
classTestimplementsX {publicvoidm3() {// We only want to implement this method }// However, we need to implement all methods in the interface,// which increases the length of code unnecessarilypublicvoidm1() {}publicvoidm2() {}publicvoidm4() {}// ...publicvoidm1000() {}}
The problem with the above approach is that it increases the length of code and reduces readability. We can solve this problem by extending the Adapter class. This way, we only need to provide implementations for the required methods, and we are not responsible for implementing every method present in the interface, reducing the length of code.
Java
classTestextendsAdapterX {publicvoidm3() {// Provide implementation for only this method }}classSampleextendsAdapterX {publicvoidm7() {// Provide implementation for only this method }}classDemoextendsAdapterX {publicvoidm1000() {// Provide implementation for only this method }}
The concept of marker interfaces and adapter classes simplifies the complexity of programming. They are powerful utilities for programmers, making their lives simpler.
Java Interface vs Abstract Class vs Concrete Class
Java Interface:
Definition: An interface in Java is a blueprint of a class that defines a set of abstract methods without providing any implementation.
Usage: Java Interfaces are used when we have a requirement specification without any knowledge of implementation details. For example, in Java servlets, the Servlet interface is used to define the methods that all servlets must implement.
Characteristics:
Contains only method declarations, without any implementation.
Provides a contract that concrete classes must adhere to.
Supports multiple inheritance.
Cannot contain constructors.
Abstract Class:
Definition: An abstract class in Java is a class that cannot be instantiated and may contain both abstract and concrete methods.
Usage: Abstract classes are used when we have some knowledge about implementation, but the implementation is not complete. They serve as a partial blueprint for concrete classes. For Example, GenericServlet and HttpServlet in Java servlets. These classes provide partial implementations of the Servlet interface, leaving some methods abstract for subclasses to implement.
Characteristics:
Can contain both abstract and concrete methods.
May include instance variables.
Cannot be instantiated directly, but can be subclassed.
Used to define common behavior for subclasses.
Concrete Class:
Definition: A concrete class in Java is a class that provides complete implementation for all its methods and can be instantiated directly.
Usage: Concrete classes are used when we have a complete understanding of implementation details and are ready to use them in the application.For Example, A custom servlet class (MyOwnServlet) that extends HttpServlet. This class provides complete implementations for all methods required by the servlet interface and can be directly instantiated for use in a web application.
Characteristics:
Provides complete implementation for all methods defined in its parent classes or interfaces.
Can be instantiated directly using the new keyword.
Can be subclassed further.
Typically used to create objects and perform specific tasks in the application.
Difference Between Interface and Abstract Class
Java Interface:
If we lack knowledge about implementation and possess only the requirement specification, we opt for an interface.
Inside an interface, every method is inherently public and abstract, whether explicitly declared or not. Hence, an interface is considered a 100% pure abstract class.
Since every interface method is always public and abstract, we cannot declare them with the modifiers private, protected, final, static, synchronized, native, and strictfp.
Every variable inside an interface is always public, static, and final, whether explicitly declared as such or not.
As every interface variable is always public, static, and final, we cannot declare them with the modifiers private, protected, volatile, and transient.
For interface variables, it is compulsory to perform initialization at the time of variable declaration; otherwise, a compilation error will occur.
Inside an interface, we cannot declare static and instance blocks.
Inside an interface, we cannot declare constructors.
Abstract class:
If we discuss implementation but not completely (partial implementation), we should use an abstract class.
Not every method inside an abstract class needs to be public and abstract; concrete methods are also allowed.
There are no restrictions on the modifiers of methods in an abstract class.
Not every variable inside an abstract class needs to be public, static, and final.
There are no restrictions on the modifiers of variables in an abstract class.
For variables in an abstract class, there’s no requirement to perform initialization at the time of declaration, so there are no restrictions on variable declaration.
Inside an abstract class, we can declare static and instance blocks.
Inside an abstract class, we can declare constructors.
Loopholes
As an abstract class cannot create an object and still contains a constructor, what is the need for a constructor in an abstract class?
The constructor in an abstract class will be executed whenever a child class object is created to perform initialization of child class objects only. Some properties inherited from the parent abstract class require initialization, necessitating the presence of an abstract class constructor. Its main advantage lies in writing less code and achieving code reusability. Although we cannot create an object directly or indirectly for an abstract class, we can still perform initialization of variables.
Anyway, we can’t create objects for abstract classes and interfaces. However, an abstract class can contain a constructor, whereas an interface does not. What is the reason for this?
The main purpose of a constructor is to perform initialization of instance variables. An abstract class can contain instance variables that are required for child objects, necessitating the presence of a constructor for the abstract class. However, every variable present inside an interface is always public static final, whether explicitly declared or not. Therefore, there is no chance of existing instance variables inside an interface, and the concept of a constructor is not required.
Whenever we create a child class object, the parent class object won’t be created; instead, the parent class constructor will be executed for the child object’s purpose only.
As an interface contains only abstract methods, and even in an abstract class, we can have only abstract methods, what is the difference between them? Can we replace an interface with an abstract class?
Yes, we can replace an interface with an abstract class, but it is not considered good programming practice. This is akin to recruiting an IAS officer for a sweeping activity. However, if everything is abstract, it is highly recommended to use an interface instead. Why?
Approach 1: Abstract Class
Inheritance Constraint: While extending an abstract class, it’s not possible to extend any other class, limiting the inheritance concept.
Object Creation Overhead: Object creation for classes extending an abstract class might be relatively more time-consuming due to the complexity of initialization logic.
Java
// Abstract class approachabstractclassX {}// 1) While extending an abstract class, we are unable to extend any other class, thus missing out on the inheritance concept.classTestextendsX {}// 2) In this case, object creation is costly.Testt = newTest(); // Takes 2 minutes to create an object
Approach 2: Interface
Inheritance Flexibility: Implementing an interface doesn’t restrict the ability to extend other classes, allowing more flexibility in inheritance.
Object Creation Efficiency: Object creation for classes implementing an interface tends to be more efficient, as there is no overhead of initializing shared properties.
Java
// Interface approachinterfaceX {}// 1) While implementing an interface, we are able to extend some other class happily, thus not missing out on the inheritance concept.classTestimplementsX {}// 2) In this case, object creation is not costly.Testt = newTest(); // Takes 2 seconds to create an object
In short:
When using an abstract class, we cannot extend any other class while extending the abstract class itself, leading to a limitation in inheritance.
Object creation with abstract classes might be costly.
Conversely, with interfaces, we can happily implement them along with extending other classes, maintaining the inheritance concept intact.
Object creation with interfaces is typically not costly.
Conclusion
Java interfaces are a powerful feature of the Java programming language, allowing for abstraction, multiple inheritance, and polymorphism. By defining contracts that classes must adhere to, interfaces enable flexible and modular code design. Understanding how to define, implement, and use interfaces is essential for Java developers to write clean, maintainable, and extensible code.
In this guide, we’ve covered the basics of Java interfaces, including their definition, purpose, usage, best practices, and examples. With this knowledge, you should be well-equipped to leverage interfaces effectively in your Java projects.
In the world of Java programming, understanding modifiers is crucial for writing efficient and secure code. Modifiers provide additional information about classes, methods, and variables, influencing their behavior and accessibility within the program. From controlling access levels to enforcing specific characteristics, modifiers play a vital role in shaping the structure and functionality of Java applications.
In this blog, we’ll delve into the various types of modifiers in Java, exploring their uses, syntax, and best practices. Whether you’re a beginner looking to grasp the basics or an experienced developer aiming to refine your skills, this comprehensive guide will serve as a valuable resource for mastering Java modifiers.
Class Level Modifiers
When writing our own class in Java, we need to provide some extra information to the JVM, such as whether the class is accessible everywhere, if child class creation is allowed, or whether object creation is possible or not, by using appropriate modifiers.
There are a total of 12 modifiers in Java:
public
private
<default>
protected
final
abstract
static
synchronized
native
strictfp
transient
volatile
Among them, there are 8 class-level modifiers:
For top-level classes, only five are allowed: public, <default>, final, abstract, and strictfp .
For inner classes, top-level modifiers along with private, protected, and static are permissible.
For Example:
Java
privateclassTest {}
Results in a compilation error: “Modifier ‘private’ not allowed here.”
Java
publicclassTest {privateclassTest { }}
Compiles without issues because private and static are allowed for inner classes.
Java
privateclassTest {// CE: modifier 'private' not allowed here.}publicclassTest {privateclassTest {// code compiler without any problem because 'private' and 'static' are allowed for inner classes. }staticclassTest {// code compiler without any problem because 'static' is allowed for inner classes. }}
Similarly, this compiles fine since static is permitted for inner classes.
Access Specifiers and Modifiers in Java
In C and C++ languages, public, protected, <default>, and private are considered access specifiers, while all other modifiers are regarded as access modifiers. However, this distinction does not apply to Java, where all modifiers are considered as access modifiers.
public: Accessible everywhere within packages; even outside packages can access it.
<default>: Accessible everywhere within the current package; from outside the package, it cannot be accessed. Also known as package-level access.
protected: Enables access within the same package and subclasses, even if they are outside the package.
private: Restricts access to within the class where it’s declared, preventing access from other classes.
final modifiers: Applicable for classes, methods, and variables.
Final method: Method implementation is final, not allowed to change in a child class. Compiler Error: Child class cannot override overridden method declared as final in parent.Final class: If a class is final, it cannot be extended, meaning the whole implementation cannot be changed. Inheritance is not possible.Final variable: If a variable is final, its value cannot be changed, acting as a constant.
Note: Every method in a final class is, by default, final implicitly, but not every variable in a final class needs to be final because non-final variables can be changed.
Advantages and Disadvantagesof Final Modifiers:
Advantages of using final modifiers include enhanced security and ensuring a unique implementation of a class. However, there are disadvantages such as limitations on key Object-Oriented Programming (OOP) features like inheritance (due to final classes) and polymorphism (due to final methods). Thus, it’s generally not recommended to use the final keyword unless specific requirements necessitate its usage.
Before proceeding, a very silly but extremely important question regarding these concepts comes to my mind,
What are access specifiers and access modifiers in Java, and what is the difference between them?
In Java, access specifiers and access modifiers are used to control the visibility and accessibility of classes, methods, and variables within a program. These modifiers determine which parts of a program can access a particular member (class, method, or variable) and from where.
So,
Access Specifiers: Access specifiers define the scope of a class, method, or variable.
and,
Access Modifiers: Access modifiers are a subset of access specifiers that specifically modify the behavior of classes and members. Let’s take simple example, The final modifier can be applied to classes, methods, and variables. When applied to a class, it means that the class cannot be subclassed. When applied to a method, it means that the method cannot be overridden by subclasses. When applied to a variable, it means that the variable’s value cannot be changed once initialized.
Difference between Access Specifiers and Access Modifiers:
Access specifiers define the visibility of a class, method, or variable (e.g., public, protected, default, private).
Access modifiers are a subset of access specifiers and further modify the behavior of classes and members (e.g., final, abstract).
In short, accesAbstract Classs specifiers define where a class, method, or variable can be accessed from, while access modifiers modify the behavior of classes and members. However, it’s important to note that in Java, all of these are considered as access modifiers only.
Abstract Modifier in Java
In Java, the abstract modifier is applicable only to classes and methods, not to variables.
Abstract Method
Only declaration is available but no implementation is provided for that method. Hence, abstract methods end with a semicolon (;).
Example:
Java
publicabstractintgetNoOfWheels();
The child class is responsible for providing an implementation for the parent class’s abstract method.
If a class contains any abstract method, then it is compulsory for that class to be declared as abstract.
The main advantage of declaring abstract methods in a parent class is that every child class is compulsory to implement that abstract method.
It’s crucial to note that abstract methods are solely about declaration and lack implementation. Attempting to combine abstract with modifiers that imply implementation leads to a compilation error. These illegal combinations include final, native, synchronized, static, private, and strictfp. For instance:
Java
abstractfinalvoidm1()// Results in a compilation error: "Illegal combination of modifiers 'abstract' and 'final'"
Means, abstract methods never deal with implementation. If any modifier pertains to implementation, then such modifier combinations with abstract are illegal. We get the same Compiler Error (CE).
Abstract Class
An abstract class is used for any Java class where object creation is not allowed due to partial implementation. Such types of classes are declared with abstract methods. Instantiation of an abstract class is not possible; we cannot create an object of an abstract class. If attempted, a Compiler Error (CE) is raised: “class is abstract, cannot be instantiated.”
If a class contains at least one abstract method, then it must be declared as abstract, otherwise, a Compiler Error will be encountered. Why? Because if a class contains at least one abstract method, its implementation is not complete, and it’s not recommended to create an object of such a class. To restrict object instantiation, it’s compulsory to declare the class as abstract. Even if a class contains zero abstract methods, we can still declare the class as abstract if we don’t want object creation of that class. For example, HttpServlet is abstract but doesn’t contain any abstract methods. Similarly, every adapter class is abstract but doesn’t contain any abstract methods.
When extending an abstract class, it’s necessary to implement each and every method present in the abstract class in the child class. If this is not possible, then the child class must be declared as abstract. In such cases, the next level child class is responsible for providing the implementation.
Abstract vs. Final
Abstract method: Compulsory to override in child class to provide implementation. Final method cannot be overridden; hence, the combination of final and abstract is illegal for methods.
For final classes, we cannot create a child class, whereas for abstract classes, we should create a child class to provide implementation. Hence, the combination of final and abstract is illegal for classes.
An abstract class can contain a final method, whereas a final class cannot contain an abstract method.
This is allowed, as an abstract class can contain final methods.
Java
finalclassTest {publicabstractvoidm1(); // Not allowed}
This is not allowed, as a final class cannot contain abstract methods.
It is highly recommended to use the abstract modifier in our day-to-day programming as it promotes several Object-Oriented Programming (OOP) features like polymorphism (method overriding) and inheritance (creating child classes). However, the final modifier suppresses OOP features, so it is not recommended to use it.
strictfp (strict floating point) Modifier
The strictfp modifier can be used with classes and methods but not for variables. Usually, floating-point results vary from platform to platform, and if we want platform-independent results, we use the strictfp modifier. A strictfp method needs to follow IEEE 754 standards to achieve platform-independent results. Since strictfp always pertains to implementation and abstract doesn’t, the combination of both modifiers is illegal.
strictfp at the Class Level
If every concrete method inside a class needs to follow IEEE 754 standards when using floating point, we declare that class as strictfp. However, if the class contains some abstract methods, then that class needs to be defined as abstract. Hence, the combination of strictfp and abstract is legal at the class level but illegal at the method level.
Member-Level Modifiers (Method or Variable Level Modifiers)
In Java, member-level modifiers are used to control access to methods or variables within classes. Here’s a breakdown of the commonly used member-level modifiers:
public member: If a member is declared as public, it can be accessed from anywhere, but the corresponding class should be visible. Before checking member visibility, class visibility must be considered. This means that both the class and member need to be public for access from outside the package.
default member: If a member is default, it can be accessed within the current package, but it cannot be accessed from outside the package. Hence, it is also known as package-level access.
private member: If a member is private, it can be accessed only within the current class; outside the class, it cannot be accessed. Abstract methods are available to child classes for providing implementation, whereas private methods are not available to child classes for implementation. Therefore, the combination of abstract and private is illegal.
protected member: If a member is protected, it can be accessed within the current package and also by child classes outside the package. It is one of the most misunderstood modifiers in Java. Protected access is equivalent to default access plus access for child classes.
We can access protected members within the current package anywhere using either parent reference or child reference. However, outside the package, we can access them only using child reference. If attempted to access using parent reference, a Compiler Error (CE) will be raised: “member has protected access in that class”.
Visibility rules for member-level modifiers
Within the same class: All access modifiers (private, <default>, protected, public) are allowed.
From child classes of the same package: <default>, protected, and public are allowed, but private is not.
From non-child classes of the same package: <default>, protected, and public are allowed, but private is not.
From child classes of outside packages: protected is accessible using child class references only, public is allowed, and others are not.
From non-child classes of outside packages: Only public access is allowed; others are not.
Final Variables
In Java, final variables are those whose values cannot be changed once they are assigned. Here’s a breakdown of final variables, let’s first focusing on final instance variables:
Final instance variable
The value of a variable that varies from object to object is called an instance variable or object-level variable. For every object, a separate instance variable copy is created. For instance variables, we don’t require explicit initialization because the JVM always provides default values. However, in the case of final instance variables, the JVM won’t provide a default value. We need to provide initialization explicitly whether it’s used or not; otherwise, we will encounter a Compiler Error (CE): “variable might not have been initialized”.
There are rules for initializing final instance variables:
Rule – Before constructor completion:
Case 1: At the time of declaration:
Java
classTest {finalintx = 10;}
Case 2: Inside an instance block:
Java
classTest {finalintx; { x = 10; }}
Case 3: Inside a constructor:
Java
classTest {finalintx = 10;Test() { x = 10; // CE: Cannot assign value to final variable }}
Note: If we try to initialize it in any method, we’ll get a CE: “cannot assign value to final variable”.
Final Static Variable
A final static variable is used when the value of the variable does not vary from object to object. Such a variable is called a static variable or class-level variable and is not recommended to be declared as an instance variable. It needs to be declared as static, and only a single copy exists at the class level, shared by every object.
In a static variable, the JVM always provides a default value at the time of initialization. We don’t need to do it explicitly. However, in the case of a final static variable, we must perform initialization explicitly; otherwise, we’ll encounter a Compiler Error (CE): “variable might not have been initialized”.
Rule: Before class loading completion, we need to perform initialization.
Case 1: At the time of declaration:
Java
classTest {finalstaticintx = 10;}
Case 2: Inside a static block:
Java
classTest {finalstaticintx;static { x = 10; }}
Note: We cannot initialize a final static variable inside a method; otherwise, we will get a CE: “cannot assign value to final variable”.
Final Local Variable
In Java, a final local variable is a variable declared within a method, block, or constructor, and its value remains constant once initialized. These variables are temporary and are stored on the stack, such variables are called local or temporary or stack or automatic variables.
Key points about final local variables:
JVM does not provide a default value for local variables. They must be explicitly initialized before use.
Even if a local variable is declared as final, initialization is only required if the variable is used. Unused final local variables do not need initialization.
The only applicable modifier for local variables is final. Attempting to use any other modifiers like public, private, protected, static, transient, or volatile will result in a compilation error.
Formal parameters of a method act as local variables within that method. They can also be declared as final, in which case, reassignment within the method is not allowed.
Example of declaring a final local variable:
Java
voidmyMethod() {finalintx = 10; // Declaring and initializing a final local variable// Other code using variable x}
Formal parameter example:
Java
voidmyMethod(finalint param) {// param acts as a final local variable within this method// Reassignment of param is not allowed within this method}
Note: The only applicable modifier for a local variable is final. If we try to use any other modifier like public, private, protected, static, transient, or volatile, we will encounter a Compiler Error (CE): “illegal start of expression”. If no modifier is declared, by default, it is <default>, but this rule applies only to instance and static variables, not for local variables.
Aso, formal parameters of a method simply act as local variables of that method. Formal parameters can be declared as final. If a formal parameter is declared as final, reassignment within the method is not permitted.
Static Modifiers
Static modifiers are applicable only for methods and variables and not for top-level classes. However, in static nested inner classes, it is applicable.
Instance Variable: A separate copy is created for every variable. In static variables, only one copy is created at the class level and shared by every object of the class.
Instance Variable vs. Static Variable: Instance variables can be accessed only from the instance area and cannot be accessed directly from the static area. However, static variables can be accessed from anywhere.
Consider the following declarations and let’s determine the correct combination:
I. int x = 10;
II. static int x = 10;
III. public void m1() { System.out.println(x); }
IV. public static void m1() { System.out.println(x); }
Correct Combinations:
I and III: Correct. Instance variable x is accessed within an instance method. (Instance variable and instance method)
II and III: Correct. Static variable x is accessed within an instance method. (Static variable and instance method)
II and IV: Correct. Static variable x is accessed within an static method. (Static variable and static method)
Incorrect Combinations:
I and IV: Incorrect. Compiler Error (CE): “non-static variable x cannot be referenced from a static context.”
I and II: Incorrect. Duplicate variable x declaration within the same class.
III and IV: Incorrect. Duplicate method m1() declaration within the same class.
Regarding the main method overloading
If both public static void main(String[] args) and public static void main(int[] args) are present in the same class, and sop("String[]") is called, the output will be "String[]". This is because both methods are overloaded, and the class entry point is public static void main(String[] args).
Inheritance and Static Methods
The inheritance concept is applicable to static methods, including the main method. Hence, while executing a child class, if the child class doesn’t contain any main method, then the parent class’s main method will be executed.
In this case, it is method hiding but not method overriding. So, when we run P.java, the output will be “Parent main”, and when we run C.java, the output will be “Child main”.
When to Use Static and Instance Methods:
Use instance methods when at least a single instance variable is being used.
Use static methods when no instance variable is being used, regardless of whether static variables are being used or not.
Abstract Static Combination:
The combination of abstract and static is illegal for methods because abstract means only declaration without implementation, while static means only implementation.
Synchronized Modifiers
In Java, the synchronized modifier is applicable only to methods and blocks but not to variables or classes.
Key points about the synchronized modifier:
It is used to prevent data inconsistency problems, such as race conditions, that may occur when multiple threads operate simultaneously on the same Java object.
When a method or block is declared as synchronized, only one thread is allowed to execute that method or block on the given object at a time, ensuring data consistency.
However, using synchronized can lead to increased waiting time for threads and performance issues. Therefore, it’s not recommended to use it unless there is a specific requirement to do so.
Combining synchronized with abstract is illegal for methods because:
abstract methods lack implementation and only provide a declaration.
synchronized methods require implementation to specify the synchronized behavior.
Combining these modifiers is contradictory, as abstract implies a lack of implementation while synchronized implies specific implementation details.
Therefore, synchronized abstract is not allowed for methods.
Native Modifiers
The native modifier is applicable only for methods and cannot be applied anywhere else.
Methods that are implemented in non-Java languages, mostly C and C++, are called native methods or foreign methods. Native methods are used when performance is critical. For example, the hashCode method in Java is implemented using native code.
For Java, native method implementations are already available in other old languages like C and C++. Therefore, we are not responsible for providing the implementation, and hence native methods end with a semicolon (;).
Java
publicnativevoidm1(); // CE: Native methods cannot have a body
The combination of native and abstract is illegal for methods because native methods already have implementation in old languages like C/C++, while abstract methods don’t have.
The combination of native and strictfp is also illegal for methods because strictfp follows IEEE 754 standards, but there is no guarantee that native methods, which are implemented in C/C++, adhere to IEEE 754 standards.
The main advantage of using native methods is improved performance, but the main disadvantage is that it introduces Java dependency as we completely depend on other language implementations.
Transient Modifiers
In Java, the transient modifier is applicable only to variables and is commonly used in the context of serialization.
Key points about the transient modifier:
It is used to indicate that a variable should not be serialized.
When an object is serialized, all of its non-transient instance variables are saved to a file or sent over a network. However, transient variables are excluded from this process.
Transient variables are useful when there are sensitive or unnecessary fields that should not be saved during serialization. For example, fields containing passwords or temporary data.
When an object is deserialized, transient variables will be initialized to their default values (e.g., null for objects, 0 for numeric types).
Using transient achieves better security by preventing certain data from being persisted or transmitted.
Transient variables are typically declared as private, though this modifier is not strictly necessary for serialization purposes.
Example usage:
Java
import java.io.Serializable;classMyClassimplementsSerializable {privatetransientStringsensitiveData; // This variable will not be serialized// Other non-transient variables and methods}
In this example, the sensitiveData variable will not be included in the serialization process, ensuring that sensitive information is not persisted or transmitted.
Volatile Modifiers
The volatile modifier is applicable only for variables and not for anywhere else.
If the value of a variable keeps changing in multiple threads, there may be a chance of a data inconsistency problem. We can solve this problem using the volatile keyword.
When a variable is declared as volatile, JVM will create a separate copy of that variable for each thread. Any modification performed by any thread is on its own copy, ensuring that it will not affect the value seen by any other thread.
The combination of final and volatile is illegal for variables because final implies that the value never changes, while volatile implies that the value keeps on changing.
Advantage: Overcoming data inconsistency problems.
Disadvantage: Creating and maintaining separate copies of variables, leading to reduced performance and increased memory usage. Therefore, volatile is deprecated and not recommended for use.
Short Modifiers Summary:
Here’s a brief revision of the modifiers mentioned:
Local Variable: Only applicable modifier is final.
Constructor: Applicable modifiers are public, private, protected, and <default>.
Methods: Only applicable modifier is native.
Variables: Applicable modifiers are volatile and transient.
Class (not for interface): Only applicable modifier is final.
Class (not for enum): Applicable modifiers are final and abstract.
Conclusion
Java modifiers serve as powerful tools for developers to enhance the functionality, security, and performance of their applications. By understanding the nuances of each modifier type and applying them appropriately, programmers can write more robust and maintainable code.
From controlling access levels with keywords like public, private, protected, and <default>, to managing synchronization and serialization with volatile and transient, modifiers offer a wide range of capabilities to meet various programming needs.
As you continue your journey in Java development, remember to leverage modifiers effectively, striking the right balance between accessibility, security, and performance. With practice and a solid understanding of modifiers, you’ll be well-equipped to tackle complex programming challenges and build successful Java applications.
Any Java class can contain any number of Java classes, and we can give any name to it, whether it is the containing class name or any other user-defined name. For example:
Java
classA {// Class A implementation}classB {// Class B implementation}classC {// Class C implementation}
Case 1: Here we can take any name like A.java, B.java, C.java, or amol.java, so there are no restrictions.
Case 2: If we declare a class with the public modifier, then the class name should match that of the file. For instance, in the above example, if public class B is declared, then the class name should be B.java; otherwise, we will get a compilation error: “class B is public, should be declared file name as B.java.”
Case 3: If a class contains multiple public classes, then at most one public class name should match the file name. For example, if public class B and public class C are present in the above code, then the file name should be C.java. Otherwise, we will get a compilation error: “class C is public, declare file name as C.java.”
Execution Behavior
In Java, a single source file can accommodate multiple classes, each with its main method. For example:
Java
classA {publicstaticvoidmain(Stringargs[]) {System.out.println("A class main"); }}classB {publicstaticvoidmain(Stringargs[]) {System.out.println("B class main"); }}classC {publicstaticvoidmain(Stringargs[]) {System.out.println("C class main"); }}classD {}
When running Java programs with multiple classes, the behavior varies based on the class invoked:
If the above class is named “amol.java,” it compiles with that name, but different source files are generated for each class name, such as A.java, B.java, C.java, and D.java. However, when we run with different class names, we get different output:
java A –> output: A class main
java B –> output: B class main
java C –> output: C class main
java D –> Runtime Error: NoSuchMethodError exception
java amol –> Runtime Error: NoClassDefFoundError
It is highly recommended to have only one class per source file and name the program the same as the class name. This practice improves readability and maintainability. This practice also aids in avoiding issues like the one encountered with java D. Additionally, importing statements in the class should be written so that there is no need to write the fully qualified name.
Import Statements
Import statements in Java facilitate the use of classes and packages within the code. There are two types of import statements:
Explicit Import: Imports a specific class or interface -> import java.util.ArrayList;
Implicit Import: Imports all classes within a package -> import java.util.*;
Resolving Class Names
While resolving class names, the compiler always gives precedence in the following manner:
Explicit class import take precedence
Classes present in the current working directory (default package) are considered next.
Implicit class import are checked last.
We don’t require import statements for the java.lang package and the default package (CWD – current working directory).
Static Import Statements
Import statements are a concept at the compiler level and have no effect on execution time.
A key difference between the #include statement in C and the import statement in Java is their behavior:
The #include statement in C is a static include type, loading all required classes at the beginning, which can lead to unnecessary memory usage and reduced performance.
The import statement in Java is a dynamic include type, loading classes on demand or “on the fly,” reducing memory usage and improving performance.
According to Sun Microsystems, static import statements reduce code length and enhance code readability. However, some programmers argue that it decreases readability and increases complexity.
In Java, without static imports, we can use class names with static methods like Math.sqrt() and Math.random(). With static imports, we can directly use methods without the class name, by using the import static statement. For instance, import static java.lang.Math.sqrt; allows us to use sqrt(10) directly without the class name.
Static import statements provide a way to access static members of a class directly without qualifying the class name. This can enhance code readability but may increase complexity.
System.out.println()
The System.out.println() method in Java can be dissected as follows:
System: This is a class present in the java.lang package.
out: It’s a static variable within the System class, of the type PrintStream.
println(): This is a method present in the PrintStream class.
While resolving static members, in the case of static statements, the compiler will always consider the following order:
Current class static members
Explicit static import
Implicit static import.
Also,
There are two types of static import:
Explicit static import
Implicit static import.
Java Package
In Java, a package is a group of interrelated classes and interfaces bundled into a single unit. The structure of a Java source file typically includes:
Package statement: This appears at most once and defines the package of the file’s contents.
Import statements: Any number of import statements can be included to import classes from other packages.
Class, interface, or enum declarations: There can be any number of these declarations within the source file.
Conclusion
Understanding Java class structure and import statements is crucial for writing efficient and maintainable code. By organizing classes logically and utilizing import statements effectively, developers can improve code readability and performance in Java applications.
Sorting algorithms are fundamental tools in computer science used to organize data efficiently. Sorting algorithms are techniques used to rearrange elements in a list or array in a specific order. The order could be ascending or descending based on certain criteria, such as numerical value or alphabetical order. Sorting algorithms play a crucial role in various applications, including databases, search algorithms, and more.
In Java, sorting algorithms can be implemented using various approaches, each with its unique characteristics and performance implications. In Java, there are various sorting algorithms, each with its advantages and disadvantages. In this guide, we’ll explore some of the most commonly used sorting algorithms, including their implementations, complexities, and use cases.
Sorting algorithms in Java : Insertion Sort
Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the input array, removing one element per iteration and then finding its correct position in the sorted array.
Java
publicint[] insertionSort(int[] list) {inti; // Counter for outer loopintj; // Counter for inner loopintkey; // To hold the key value purpose we use it inttemp; // It will be helpful while swapping values for(i = 1; i < list.length; i++) {// Outer for loop starts with 1 and checks till the end value.// Here we consider the 0th element is already sorted that's why we start from 1 key = list[i]; // It is our key value which is list[i] for every iteration j = i - 1; // It will start point of comparison moving downwards till 0 // We end the while loop when j value reaches 0 or when the key value is no longer smaller than the valuewhile(j >= 0 && key < list[j]) {// Swap the values using the temp variable and arrange them in increasing order temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp; j--; // Decreasing j by 1 as we move towards the left } }return list;}
This insertionSort method implements the insertion sort algorithm for sorting an array of integers in increasing order. It iterates through the array, considering each element as a key and inserting it into the correct position in the sorted subarray to its left. The inner loop compares the key with the elements to its left and swaps them if necessary to maintain the sorted order. Finally, it returns the sorted array.
Explanation
Given an array of integers, sort them in increasing order using insertion sort:
Initial array: 5, 8, 1, 3, 9, 6
Definition of sorted: All items to the left are smaller. For example, 5 is already considered sorted as there are no elements to its left.
So, we start our insertion sort process from index 1:
Key (k) = 8. Compare k < 5? No. So, 8’s position is correct. Consider 5 and 8 as sorted.
Next, at index 2:
Key (k) = 1.
Compare k < 8? Yes, swap: 5, 1, 8, 3, 9, 6.
Compare k < 5? Yes, swap: 1, 5, 8, 3, 9, 6.
Element till index 2 is sorted.
Start at index 3:
Key (k) = 3.
Compare k < 8? Yes, swap: 1, 5, 3, 8, 9, 6.
Compare k < 5? Yes, swap: 1, 3, 5, 8, 9, 6.
Compare k < 1? No, no swap.
Elements till index 3 are now sorted.
Start at index 4:
Key (k) = 9.
Compare k < 8? No, no swap. Also, all elements left of 8 are sorted, indicating 9’s position is correct.
Elements till index 4 are also sorted.
Start at index 5:
Key (k) = 6.
Compare k < 9? Yes, swap: 1, 3, 5, 8, 6, 9.
Compare k < 8? Yes, swap: 1, 3, 5, 6, 8, 9.
Compare k < 5? No, no swap. End of loop.
Finally, we obtain the sorted list using insertion sort. Final array: {1, 3, 5, 6, 8, 9}
Note: Insertion Sort is not a fast sorting algorithm as it uses nested loops to shift items into place. It is useful only for small datasets. It runs in O(n^2) time complexity and O(1) space complexity.
Selection Sort
Selection Sort is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted part of the array and moves it to the beginning. This process continues until the entire array is sorted.
Java
publicint[] selectionSort(int[] list) {inti; // Outer loop counterintj; // Inner loop counterintminValue; // To track minimum valueintminIndex; // To track the index of the minimum value in the arrayinttemp = 0; // For swapping purposes// Let's consider this array: 7, 8, 5, 4, 9, 2// Outer loop should iterate from 0 to 5 (i.e., 6 iterations)// So the outer loop should be: for i = 0 to 5for (i = 0; i < list.length; i++) {// Initialize minValue and minIndex to the first unsorted item each time through the outer loop minValue = list[i]; minIndex = i;// Inner loop starts at the first unsorted item and continues through the last item in the list// So the inner loop should be: for j = i to 5for (j = i; j < list.length; j++) {// Inside the inner loop, if the list item is less than the current minValue,// update minValue and store its index in minIndexif (list[j] < minValue) { minValue = list[j]; minIndex = j; } }// After that, we check if the minValue is less than the value at the current index of the outer loop// If yes, then swap that value with the value at minIndexif (minValue < list[i]) { temp = list[i]; list[i] = list[minIndex]; list[minIndex] = temp; } }return list;}
This selectionSort method implements the selection sort algorithm for sorting an array of integers in increasing order. It iterates through the array, finding the minimum element in the unsorted part of the array and swapping it with the first unsorted element. This process repeats until the entire array is sorted. Finally, it returns the sorted array.
Explanation
Selection Sort: It finds the smallest item from the unsorted part of the list and moves it to the first element of the list while performing selection sort.
Consider this array: 7, 8, 5, 4, 9, 2 // also imagine indices from 0 to 5.
So initially, our minValue is 7 and minIndex is 0.
Now, comparison:
Is 8 < minValue (7)? No.
Is 5 < minValue (7)? Yes, the new minValue is 5 and minIndex is 2.
Is 4 < minValue (5)? Yes, the new minValue is 4 and minIndex is 3.
Is 9 < minValue (4)? No. Is 2 < minValue (4)? Yes, the new minValue is 2 and minIndex is 5.
We found our first smallest element, so we swap that element with the first element ==> 2, 8, 5, 4, 9, 7.
Our second iteration starts with index 1, so our first element is 8, and minValue is 8, with minIndex as 1. Now, start comparison toward the right side of 8.
Is 5 < minValue (8)? Yes, the new minValue is 5, and minIndex is 2.
Is 4 < minValue (5)? Yes, the new minValue is 4, and minIndex is 3.
Is 9 < minValue (4)? No.
Is 7 < minValue (4)? No.
We found our smallest element for the second iteration, so we swap it with the first element ==> 2, 4, 5, 8, 9, 7.
Now, start comparison towards the right side of 5, and we see that 5 is the smallest element among them, so there’s no need to swap.
Again, we start comparison towards the right side of 8. So, minValue is 8, and minIndex is 3.
Is 9 < minValue (8)? No.
Is 7 < minValue (8)? Yes, the new minValue is 7, and minIndex is 5.
So, swap ==> 2, 4, 5, 7, 9, 8.
Now, for the next iteration, minValue is 9, and minIndex is 4.
Is 8 < minValue (9)? Yes, the new minValue is 8, and minIndex is 5.
So, swap ==> 2, 4, 5, 7, 8, 9.
Note: Selection Sort is not a fast sorting algorithm because it uses nested loops to sort. It is useful only for small datasets means suitable for small arrays or when auxiliary memory is limited. It runs in O(n^2) time complexity and O(1) space complexity.
Bubble Sort
Bubble Sort is another simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Java
publicint[] bubbleSort(int[] list) {inti; // outer loop counterintj; // inner loop counterinttemp = 0; // for swapping purposefor (i = 0; i < list.length - 1; i++) { // outer loop iterate till the endfor (j = 0; j < list.length - 1 - i; j++) { // inner loop iterate till the end where already sorted element bubbled at the endif (list[j] > list[j + 1]) { // if we consider two adjacent values then previous value greater means we need to swap them with next value temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp; } } }return list;}
This bubbleSort method implements the bubble sort algorithm for sorting an array of integers in increasing order. It iterates through the array multiple times, comparing adjacent elements and swapping them if they are in the wrong order. This process repeats until the array is sorted. Finally, it returns the sorted array.
Explanation
Bubble Sort: It is a simple sorting algorithm that repeatedly compares adjacent elements in the list and swaps them if they are in the wrong order. This process continues until the list is sorted.
Unsorted list: 5, 8, 1, 6, 9, 2 // Imagine indices from 0 to 5.
So, what is bubble sort?
In bubble sort, we repeatedly compare adjacent items, for example, 5 and 8, so that with every iteration, larger items “bubble” to the right side.
First iteration:
Is 5 > 8? No.
Is 8 > 1? Yes ==> Swap ==> 5, 1, 8, 6, 9, 2
Is 8 > 6? Yes ==> Swap ==> 5, 1, 6, 8, 9, 2
Is 8 > 9? No.
Is 9 > 2? Yes ==> Swap ==> 5, 1, 6, 8, 2, 9
Second iteration:
Is 5 > 1? Yes ==> Swap ==> 1, 5, 6, 8, 2, 9
Is 5 > 6? No.
Is 6 > 8? No.
Is 8 > 2? Yes ==> Swap ==> 1, 5, 6, 2, 8, 9
Third iteration:
Is 1 > 5? No.
Is 5 > 6? No.
Is 6 > 2? Yes ==> Swap ==> 1, 5, 2, 6, 8, 9
Is 6 > 8? No.
Is 8 > 9? No.
Fourth Iteration:
Is 1 > 5? No.
Is 5 > 2? Yes ==> Swap ==> 1, 2, 5, 6, 8, 9
Is 5 > 6? No.
Is 6 > 8? No.
Is 8 > 9? No.
Fifth Iteration:
All elements are in sorted order; no need to do any swapping.
Final sorted list: 1, 2, 5, 6, 8, 9
Note: Bubble Sort is not an efficient sorting algorithm because it uses nested loops. It is useful only for small data sets. It runs in O(n^2) and O(1) space complexity.
Merge Sort
Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, sorts each half separately, and then merges the sorted halves.
Java
// passing low and high index to this function// e.g 38,27,43,3,9,82,10 ==> low -> 0 and high -> 6 (size - 1)th indexprivatevoidmergeSort(int low, int high) {if (low < high) // base condition {intmid = low + (high - low) / 2; // we need to find mid (it is 3 here)// perform recursive division into low to mid and then mid + 1 to highmergeSort(low, mid); // 38,27,43,3 ===for next recursive call ===> 38,27 and 43,3 === next recursive call ==> 38 and 27 | 43 and 3 here as we reached base condition where low and high are equal and return back and execute remaining codemergeSort(mid + 1, high); // we start when the above statement executed completely and reached the base case, so now 9,82,10 === for the next recursive call ===> 9,82 and 10 ==== for the next call ===> 9 and 82 | 10 here also we reached the base condition so go back nowmerge(low, mid, high); // it will just merge the elements according to the sorting order }}// we pass low, mid, and high valueprivatevoidmerge(int low, int mid, int high) {// for copying purposes means we copy number values to helper[] from low to till highfor (inti = low; i <= high; i++) { helper[i] = numbers[i]; }inti = low;intj = mid + 1;intk = low;// we tried to sort the numbers[] element and placed them in exact same orderwhile (i <= mid && j <= high) {if (helper[i] <= helper[j]) { numbers[k] = helper[i]; i++; } else { numbers[k] = helper[j]; j++; } k++; }// if still some values remain to be placed in sorted order in numbers[] we will do that herewhile (i <= mid) { numbers[k] = helper[i]; k++; i++; }}
These methods implement the merge sort algorithm. mergeSort is a recursive method that divides the array into two halves and recursively calls itself on each half until it reaches the base case where low is no longer less than high. Then, the merge method merges the two sorted halves into a single sorted array.
Explanation
Merge Sort is a divide and conquer algorithm. It divides the input array into two halves, recursively calls itself for the two halves, and then merges the two sorted halves.
For example, with an input array like 38, 27, 43, 3, 9, 82, 10:
First, we call mergeSort(0, 6) as the initial entry point.
In mergeSort:
We find the mid index (low + (high – low) / 2) to split the array into two halves.
Then, we recursively call mergeSort for the left half (low to mid) and the right half (mid + 1 to high).
Finally, we merge the sorted halves using the merge function.
In merge:
We create a helper array to copy elements from the original array.
We iterate through the two halves, comparing elements and merging them into the original array in sorted order.
If any elements remain in the left half after merging, we copy them back to the original array.
Let’s go through the merge sort algorithm step by step:
Initial array: {38, 27, 43, 3, 9, 82, 10}
Initial call to mergeSort(0, 6):
Since low (0) is less than high (6), we proceed.
Calculate mid = 0 + (6 – 0) / 2 = 3
Recursive call 1: mergeSort(0, 3)
Since low (0) is less than high (3), we proceed.
Calculate mid = 0 + (3 – 0) / 2 = 1
Recursive call 2a: mergeSort(0, 1)
Since low (0) is less than high (1), we proceed.
Calculate mid = 0 + (1 – 0) / 2 = 0
Recursive call 2b: mergeSort(1, 3)
Since low (1) is less than high (3), we proceed.
Calculate mid = 1 + (3 – 1) / 2 = 2
Recursive call 3: mergeSort(1, 2)
Since low (1) is less than high (2), we proceed.
Calculate mid = 1 + (2 – 1) / 2 = 1
Recursive call 4: mergeSort(2, 3)
Since low (2) is less than high (3), we proceed.
Calculate mid = 2 + (3 – 2) / 2 = 2
Back to Recursive call 4: merge(1, 1, 2)
Helper array: {27, 43, 43, 3, 9, 82, 10}
i = 1, j = 2, k = 1
Compare helper[i] (27) with helper[j] (43), place the smaller one (27) in numbers[k] (numbers[1]), increment i and k.
numbers: {38, 27, 43, 3, 9, 82, 10}
Increment k to 2 and i to 2.
Back to Recursive call 3: merge(1, 1, 3)
Helper array: {27, 38, 43, 3, 9, 82, 10}
i = 1, j = 3, k = 1
Compare helper[i] (27) with helper[j] (3), place the smaller one (3) in numbers[k] (numbers[1]), increment j and k.
numbers: {38, 3, 43, 3, 9, 82, 10}
Increment k to 2 and j to 4.
Compare helper[i] (27) with helper[j] (9), place the smaller one (9) in numbers[k] (numbers[2]), increment j and k.
numbers: {38, 3, 9, 3, 9, 82, 10}
Increment k to 3 and j to 5.
Compare helper[i] (27) with helper[j] (82), place the smaller one (27) in numbers[k] (numbers[3]), increment i and k.
numbers: {38, 3, 9, 27, 9, 82, 10}
Increment k to 4 and i to 2.
Back to Recursive call 2a: merge(0, 0, 1)
Helper array: {38, 38, 9, 27, 9, 82, 10}
i = 0, j = 1, k = 0
Compare helper[i] (38) with helper[j] (3), place the smaller one (3) in numbers[k] (numbers[0]), increment j and k.
numbers: {3, 3, 9, 27, 9, 82, 10}
Increment k to 1 and j to 2.
Compare helper[i] (38) with helper[j] (9), place the smaller one (9) in numbers[k] (numbers[1]), increment j and k.
numbers: {3, 9, 9, 27, 9, 82, 10}
Increment k to 2 and j to 3.
Compare helper[i] (38) with helper[j] (27), place the smaller one (27) in numbers[k] (numbers[2]), increment i and k.
numbers: {3, 9, 27, 27, 9, 82, 10}
Increment k to 3 and i to 1.
Back to Recursive call 1: merge(0, 1, 3)
Helper array: {3, 9, 27, 38, 9, 82, 10}
i = 0, j = 2, k = 0
Compare helper[i] (3) with helper[j] (9), place the smaller one (3) in numbers[k] (numbers[0]), increment i and k.
numbers: {3, 9, 27, 38, 9, 82, 10}
Increment k to 1 and i to 1.
Compare helper[i] (9) with helper[j] (27), place the smaller one (9) in numbers[k] (numbers[1]), increment i and k.
numbers: {3, 9, 27, 38, 9, 82, 10}
Increment k to 2 and i to 2.
Compare helper[i] (27) with helper[j] (38), place the smaller one (27) in numbers[k] (numbers[2]), increment j and k.
numbers: {3, 9, 27, 38, 9, 82, 10}
Increment k to 3 and j to 3.
Final array: {3, 9, 27, 38, 9, 82, 10}
This process continues until the entire array is sorted. The merge sort algorithm effectively divides the array into smaller segments, sorts them individually, and then merges them back together in sorted order.
Note: Merge Sort has a time complexity of O(n log n) in the average and worst cases, and O(n) in the best case, making it efficient for large datasets and O(n) space complexity.
Quick Sort
Quick Sort is another divide-and-conquer algorithm that picks an element as a pivot and partitions the array around the pivot. It then recursively sorts the subarrays.
Java
privatevoidquickSort(int low, int high) {inti = low, j = high;intpivot = numbers[low + (high - low) / 2]; // Choosing the pivot element// Partitioning the arraywhile (i <= j) {// Finding element on the left side that should be on the rightwhile (numbers[i] < pivot) { i++; }// Finding element on the right side that should be on the leftwhile (numbers[j] > pivot) { j--; }// If we found a value on the left that should be on the right and vice versa, swap themif (i <= j) {exchange(i, j); i++; j--; } }// Recursively sort the left and right partitionsif (low < j) {quickSort(low, j); }if (i < high) {quickSort(i, high); }}
This quickSort method implements the Quick Sort algorithm. It chooses a pivot element (here, the middle element) and partitions the array into two sub-arrays such that elements less than the pivot are on the left, and elements greater than the pivot are on the right. It then recursively sorts the sub-arrays until the entire array is sorted. The exchange method is assumed to swap the values at two indices in the array.
Explanation
Quick Sort is a divide and conquer algorithm. In this algorithm, the original data is divided into two parts, sorted individually, and then combined.
suppose
{6,4,2,1,5,3} is an array where low is pointing to 0th index and high is pointing to last index.
means,
Set low to 0 and high to array.length - 1, then pass these values to quickSort(low, high).
Assign low to i, which is the left side counter of the pivot, and assign high to j, which is the right side counter of the pivot.
Find the pivot. What is a pivot? A pivot is a point we consider while sorting. We arrange smaller values than the pivot to its left side and greater values to its right side. We can take any value as the pivot, but it’s best to take it randomly. Here, we use the middle element as the pivot.
We will check i <= j. If low becomes greater than high, we stop our following checks: i) First, we check the left side of the pivot to find any greater value than the pivot. If we find such a value, we terminate the while loop. Otherwise, we iterate until we reach the pivot. Since we don’t have any problem with values smaller than the pivot (as those should be on the left side), we increment i and move towards the pivot to check the next value. ii) After completing the left side (either by complete check or finding a greater value, terminating the while loop), we look at the right side of the pivot. We apply the same logic: while(any value > pivot). If true, we decrement j. If we find any smaller value than the pivot, the while loop terminates. iii) So, in the above two cases, we find whether the left side of the pivot will contain any greater value than the pivot or whether the right side of the pivot will contain any smaller value than the pivot. Because we sort the values according to the pivot, if we find a smaller value to the right and a larger value to the left, we need to place them on their respective sides. For this purpose, we use another if() condition: if i is not greater than j, then only do we exchange the values. Finally, we increment i and decrement j.
As we perform sorting according to the pivot, only small values are placed on the left side of the pivot and large values are placed on the right side. However, we notice that neither the left side nor the right side is sorted.
For example, with an array like 6, 4, 2, 1, 5, 3:
We call quickSort(0, 5) initially, where low = 0 and high = 5.
We select a pivot element, here we choose the middle element, which is 2.
We partition the array around the pivot, ensuring that elements less than the pivot are on the left and elements greater than the pivot are on the right.
We recursively call quickSort for the left and right partitions, ensuring that all elements are sorted individually.
We repeat this process until the entire array is sorted.
Let’s go through the Quick Sort algorithm step by step:
Initial array: {6, 4, 2, 1, 5, 3}
Initial call to quickSort(0, 5):
i = 0, j = 5
Pivot = numbers[0 + (5 – 0) / 2] = numbers[2] = 2
While loop (i=0, j=5):
i moves from left to right until it finds a value greater than or equal to the pivot. (i stops at 4)
j moves from right to left until it finds a value less than or equal to the pivot. (j stops at 3)
Since i <= j, exchange(numbers[i], numbers[j]) is performed.
After exchange, array becomes {3, 4, 2, 1, 5, 6}
Increment i and decrement j (i = 1, j = 4)
While loop (i=1, j=4):
i moves until it finds a value greater than or equal to the pivot. (i stops at 4)
j moves until it finds a value less than or equal to the pivot. (j stops at 1)
Since i <= j, exchange(numbers[i], numbers[j]) is performed.
After exchange, array becomes {3, 1, 2, 4, 5, 6}
Increment i and decrement j (i = 2, j = 3)
While loop (i=2, j=3):
i moves until it finds a value greater than or equal to the pivot. (i stops at 2)
j moves until it finds a value less than or equal to the pivot. (j stops at 2)
Since i <= j, exchange(numbers[i], numbers[j]) is performed.
After exchange, array remains {3, 1, 2, 4, 5, 6}
Increment i and decrement j (i = 3, j = 1)
While loop termination (i=3, j=1):
i > j, so the while loop terminates.
Recursive call 1: quickSort(0, 1)
This is the left side partition.
i = 0, j = 1
Subarray: {3, 1}
Pivot = numbers[0] = 3
While loop terminates immediately as i > j.
Recursive call 2: quickSort(3, 5)
This is the right side partition.
i = 3, j = 5
Subarray: {4, 5, 6}
Pivot = numbers[3] = 4
While loop terminates immediately as i > j.
Final sorted array: {1, 2, 3, 4, 5, 6}
This process continues recursively until all partitions have size 1 or less, meaning the array is sorted. The Quick Sort algorithm effectively divides the array into smaller partitions, sorts them individually, and then combines them to get the sorted array.
Note: Quick Sort has a time complexity of O(n log n) in the average and best cases, and O(n^2) in the worst case. However, its average case performance is typically much better than other O(n^2) algorithms like Bubble Sort and Selection Sort. It has space complexity O(log n) to O(n). Also, Quick Sort is efficient and widely used, but it has a higher worst-case time complexity compared to Merge Sort.
Conclusion
In this guide, we’ve covered several sorting algorithms in Java, including Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, and Quick Sort. Each algorithm has its advantages and disadvantages, and the choice of algorithm depends on factors such as the size of the dataset, memory constraints, and desired performance characteristics. By understanding these sorting algorithms, you can choose the most appropriate one for your specific use case and optimize the efficiency of your Java applications.
Graphs are fundamental data structures in computer science and are widely used to model complex relationships between entities. They are versatile and can represent a variety of real-world scenarios such as social networks, transportation networks, and computer networks. In this blog post, we’ll delve into some essential graph algorithms implemented in Java, covering Depth-First Search (DFS), Breadth-First Search (BFS), Dijkstra’s Shortest Path Algorithm, detecting cycles in a directed graph, and performing a topological sort.
Understanding Graphs
Before diving into the algorithms, let’s briefly review what graphs are. We know that data arranged in a linear manner is called linear data structures, such as Arrays, LinkedLists, Stacks, and Queues. Whereas, when data is stored non-linearly, it is referred to as non-linear data structures, such as Trees and Graphs. A graph consists of a set of vertices (nodes) and a set of edges (connections) that establish relationships between these vertices. Edges can be directed or undirected, depending on whether they have a specific direction or not. Graphs can also be weighted, where each edge has an associated weight or cost.
A graph is a powerful non-linear data structure consisting of two components:
Vertices (nodes): Represent individual entities or data points. Think of them as points on a map.
Edges: Represent connections between vertices, indicating relationships or interactions. Edges can be bidirectional (undirected) or unidirectional (directed), like arrows showing one-way relationships.
A graph G is an ordered pair consisting of a set V of vertices and a set E of edges.
G = (V,E)
In an ordered pair, (a,b) is not equivalent to (b,a) if a ≠b.
In an unordered pair, {a,b} equals {b,a}.
Edges:
Directed: (u,v) i.e., u → v
Undirected: {u,v} i.e., u — v
Example:
V = {v1, v2, v3, v4, v5, v6, v7, v8} // Set of vertices
Consider a social network like Facebook. Users are represented as vertices, and friendships are represented as edges. If A and B are friends, we can have either a directed edge A -> B (meaning A follows B) or an undirected edge {A, B} (meaning they follow each other).
Common Graphs Examples
Maps: Represent cities as vertices and roads as edges (weighted to denote distance).
World Wide Web: Represent web pages as vertices and hyperlinks as directed edges pointing from source pages to destination pages.
File systems: Represent directories as vertices and subdirectory/file connections as edges.
Graph Representations:
Adjacency Matrix: Square matrix, where (i,j) reflects the edge weight between vertices i and j. Suitable for dense graphs with many edges.
Adjacency List: Array or list of lists, where each index stores connections for a specific vertex. More efficient for sparse graphs with fewer edges.
Implementing Graphs in Java
To start, we’ll implement a simple graph representation in Java. We’ll use an adjacency list to store the graph, which is a list of lists where each list represents the neighbors of a particular vertex.
Java
import java.util.*;classGraph {privateintV; // Number of verticesprivateLinkedList<Integer> adjList[]; // Adjacency list representation// ConstructorGraph(intv) { V = v; adjList = newLinkedList[v];for (inti = 0; i < v; ++i) adjList[i] = newLinkedList<>(); }// Function to add an edge to the graphvoidaddEdge(intv, intw) { adjList[v].add(w); }// Getter for the adjacency list of a vertexLinkedList<Integer> getAdjList(intv) {return adjList[v]; }publicstaticvoidmain(String[] args) {Graphgraph = newGraph(4);graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(2, 0);graph.addEdge(2, 3);graph.addEdge(3, 3);for (inti = 0; i < graph.V; i++) {LinkedList<Integer> list = graph.getAdjList(i);System.out.print("Adjacency list of vertex " + i + ": ");for (Integernode: list) {System.out.print(node + " "); }System.out.println(); } }}
This Graph class represents an undirected graph using an adjacency list representation. It has a constructor to initialize the graph with a given number of vertices. The addEdge method adds an edge between two vertices. The getAdjList method returns the adjacency list of a specified vertex.
The main method demonstrates how to use the Graph class by creating a graph with 4 vertices and adding some edges. Then, it prints the adjacency list of each vertex.
Common Types of Graphs
Here are some common types of graphs and their java implementations:
Directed Graphs (Digraphs)
Directed graphs, also known as digraphs, are graphs in which edges have a direction associated with them. This means that the relationship between nodes is one-way. They are used to model relationships like dependencies, flows, or hierarchical structures.
Java
A ↗ ↘BC ↘ ↗D
Vertices are represented by letters: A, B, C, D.
Arrows indicate the direction of the edges.
Arrows point from the source vertex to the destination vertex, representing a directed edge from the source to the destination.
Implementation: In Java, you can implement a directed graph using adjacency lists or adjacency matrices. Here’s a basic example of implementing a directed graph using adjacency lists:
Undirected graphs are graphs in which edges do not have any direction associated with them. The relationship between nodes is bidirectional. They are used to model symmetric relationships, such as friendships in social networks or connections in a network.
Java
A / \ / \B --- C \ / \ /D
Vertices are represented by letters: A, B, C, D.
Edges are represented by lines connecting the vertices.
Each line connects two vertices, representing an undirected edge between them.
Implementation: Similar to directed graphs, undirected graphs can be implemented using adjacency lists or adjacency matrices. Here’s a basic example of implementing an undirected graph using adjacency lists:
Weighted graphs are graphs in which each edge has an associated weight or cost. They are used to model scenarios where the relationship between nodes has a numerical value associated with it, such as distances between cities or costs of transportation.
Java
A2/ \4/ \B--5-- C\13/ \ /D
Vertices are represented by letters: A, B, C, D.
Edges are represented by lines connecting the vertices.
Each line connecting two vertices represents an edge.
Beside each edge, there is a number indicating the weight of that edge.
For example, the edge between vertices A and B has a weight of 2, the edge between vertices B and D has a weight of 1, etc.
Implementation: Weighted graphs can be implemented similarly to undirected or directed graphs, with the addition of storing weights along with edges. Here’s an example of implementing a weighted graph using adjacency lists:
Now that we have our graph implementation ready, let’s explore some fundamental graph algorithms.
Depth-First Search (DFS)Traversal Algorithm
DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to keep track of vertices to visit next.
This DFS class contains methods for performing a Depth-First Search (DFS) traversal on a graph. The dfsUtil method is a recursive utility function that performs DFS traversal starting from a specified vertex (v). It marks the vertex as visited, prints its value, and then recursively visits its unvisited neighbors. The dfs method initializes an array to track visited vertices and calls dfsUtil to start the DFS traversal from a specified vertex.
The main method demonstrates how to use the DFS class by creating a graph with 4 vertices and adding some edges. Then, it performs a DFS traversal starting from vertex 2 and prints the traversal result.
Breadth-First Search (BFS) Traversal Algorithm
BFS is another traversal algorithm that explores all the neighboring nodes at the present depth prior to moving on to the nodes at the next depth level.
This BFS class contains a method for performing a Breadth-First Search (BFS) traversal on a graph. The bfs method initializes a boolean array to track visited vertices and a queue to store vertices for traversal. It starts the traversal from a specified vertex (v), marks it as visited, and adds it to the queue. Then, it repeatedly dequeues vertices from the queue, prints them, and adds their unvisited neighbors to the queue.
The main method demonstrates how to use the BFS class by creating a graph with 4 vertices and adding some edges. Then, it performs a BFS traversal starting from vertex 2 and prints the traversal result.
Dijkstra’s Shortest Path Algorithm
Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph. It maintains a priority queue to continuously select the vertex with the smallest distance from the source.
This Dijkstra class contains a method for finding the shortest path distances from a source vertex to all other vertices in a graph using Dijkstra’s algorithm. The dijkstra method initializes an array to store shortest distances (dist), initializes all distances to infinity except for the source vertex distance which is set to 0. It then uses a priority queue (pq) to greedily select the vertex with the shortest distance and updates the distances to its neighbors if a shorter path is found. Finally, it prints the shortest distances from the source vertex to all other vertices.
The main method demonstrates how to use the Dijkstra class by creating a graph with 6 vertices and adding some edges. Then, it performs Dijkstra’s algorithm starting from a specified source vertex and prints the shortest distances to all other vertices.
Detecting Cycles in a Directed Graph
Detecting cycles in a directed graph is crucial in various applications such as deadlock detection and task scheduling. We’ll use a modified DFS approach to detect cycles.
This CycleDetection class contains methods to detect cycles in a graph using depth-first search (DFS). The isCyclicUtil method recursively checks if there is a cycle starting from a given vertex (v) by maintaining a boolean array (recStack) to keep track of the vertices in the current recursion stack. If a vertex is visited and also present in the recursion stack, it indicates the presence of a cycle. The isCyclic method iterates through all vertices in the graph and calls isCyclicUtil for each vertex to check for cycles.
The main method demonstrates how to use the CycleDetection class by creating a graph with 4 vertices and adding some edges. Then, it checks if the graph contains a cycle and prints the result.
Topological Sorting of a Graph
Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before vertex v in the ordering.
This TopologicalSort class contains methods to perform topological sorting on a directed acyclic graph (DAG) using depth-first search (DFS). The topologicalSortUtil method recursively traverses the graph, marking visited vertices and pushing them onto a stack after visiting all of their neighbors. The topologicalSort method initiates DFS traversal for each vertex and then prints the topological order by popping vertices from the stack.
The main method demonstrates how to use the TopologicalSort class by creating a graph with 6 vertices and adding directed edges between them. Then, it performs topological sorting and prints the topological order.
Conclusion
In this blog post, we explored several essential graph algorithms implemented in Java, including DFS, BFS, Dijkstra’s Shortest Path Algorithm, cycle detection in directed graphs, and topological sorting. Understanding these algorithms is crucial for tackling a wide range of graph-related problems efficiently. Feel free to experiment with these implementations and explore further applications in your projects. Happy coding!
Binary trees are a fundamental data structure in computer science, widely used for representing hierarchical data. In this blog post, we will delve into the concept of binary trees, their implementation in Java, traversal algorithms, and some common operations associated with them.
Understanding Binary Trees
What is a Tree?
A tree is a non-linear data structure used for storing data. It is comprised of nodes and edges without any cycles. Each node in a tree can point to n number of other nodes within the tree. It serves as a way to represent hierarchical structures, with a parent node called the root and multiple levels of additional nodes.
It’s a non-linear data structure used for storing data
It is made up of nodes and edges without having any cycle. // its so important
Each node in a tree can point to n number of nodes in a tree
It is a way of representing a hierarchical structure with a parent node called a root and many levels of additional nodes
What is a Binary Tree?
A binary tree is a hierarchical data structure composed of nodes, where each node has at most two children, referred to as the left child and the right child. The topmost node of the tree is called the root node. Each node contains a data element and references to its left and right children (or null if the child does not exist).
In simple words, A tree is called a binary tree if each node has zero, one, or two children.
Java
1 / \23 / \45
Binary trees are commonly used in various applications such as expression trees, binary search trees, and more.
How to represent a Binary Tree in java?
TreeNode Representation:
Java
null<-----|left|data|right|------>null
Structure of TreeNode in a Binary Tree:
To represent a binary tree in Java, we can create a TreeNode class to define the structure of each node in the tree. Here’s how we can do it:
Java
publicclassTreeNode {privateintdata; // Data of the nodeprivateTreeNodeleft; // Pointer to the left child nodeprivateTreeNoderight; // Pointer to the right child node// Constructor to initialize the node with datapublicTreeNode(intdata) {this.data = data;this.left = null;this.right = null; }// Getters and setters for the data, left, and right pointerspublicintgetData() {return data; }publicvoidsetData(intdata) {this.data = data; }publicTreeNodegetLeft() {return left; }publicvoidsetLeft(TreeNodeleft) {this.left = left; }publicTreeNodegetRight() {return right; }publicvoidsetRight(TreeNoderight) {this.right = right; }}
In this TreeNode class:
Each node has a data field to store the value of the node.
Each node has a left field to store a reference to its left child node.
Each node has a right field to store a reference to its right child node.
The constructor initializes the node with the given data and sets both left and right pointers to null initially.
With this TreeNode class, you can create instances of the TreeNode class to represent each node in the binary tree. You can then use these instances to build the binary tree by setting the left and right pointers of each node accordingly. The root of the binary tree is typically represented by a reference to the topmost node in the tree. Initially, if the tree is empty, the root reference is set to null. As you add nodes to the tree, you update the root reference accordingly.
In simple words, Initially, the root node points to null. When we create any temporary node to insert into the tree, such as a temporary node with 15 as its data and left and right node pointers pointing to null, we can then add more nodes to the left or right.
How to implement a binary tree in java?
Let’s start by implementing a basic binary tree structure in Java:
This BinaryTree class represents a simple binary tree. It has a nested class TreeNode which represents each node in the binary tree. The createBinaryTree method initializes the tree structure by creating nodes and linking them appropriately. Finally, the main method demonstrates creating an instance of BinaryTree and initializing it.
Traversal Algorithms
Traversal is the process of visiting all the nodes in a tree in a specific order. There are three common methods for traversing binary trees:
In-order traversal: Visit the left subtree, then the root, and finally the right subtree.
Pre-order traversal: Visit the root, then the left subtree, and finally the right subtree.
Post-order traversal: Visit the left subtree, then the right subtree, and finally the root.
Let’s implement these traversal algorithms in Java.
Pre-Order Traversal Of Binary Tree in Java
Visit the root node.
Traverse the left subtree in pre-order fashion.
Traverse the right subtree in pre-order fashion.
Recursive Pre-Order Traversal
It recursively traverses the tree in the following order: root, left subtree, right subtree.
If the root is null, indicating an empty subtree, the method returns.
If the root is not null, it prints the data of the current node, traverses the left subtree recursively, and then traverses the right subtree recursively.
Consider the following binary tree:
Java
1 / \23 / \45
In pre-order traversal, the order of node visits would be: 1, 2, 4, 5, 3.
Here’s how the execution progresses:
pre_order_traversal(1) – Visit root node 1.
pre_order_traversal(2) – Visit root node 2.
pre_order_traversal(4) – Visit root node 4.
pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(4)), finish left subtree traversal.
pre_order_traversal(5) – Visit root node 5.
pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(5)), finish left subtree traversal.
pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(2)), finish left subtree traversal.
pre_order_traversal(3) – Visit root node 3.
pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(3)), finish right subtree traversal.
pre_order_traversal(None) – Backtrack to the previous call (pre_order_traversal(1)), finish right subtree traversal.
And the output of the traversal will be:
Java
Pre-order traversal:12453
In this execution, we maintain a call stack. For each method call, we track the line number and the root node being passed to that method. When we reach the base condition, we backtrack to the previous calls and execute the next steps.
Iterative Pre-Order Traversal Of Binary Tree
Iterative pre-order traversal is a way to traverse a binary tree iteratively, without using recursion. we utilize the stack data structure. Initially, we push the root node onto the stack. While the stack is not empty, we iterate using a while loop and perform pre-order traversal operations. As long as the stack is not empty, we pop the top node from the stack and assign it to the temp node. We then print its data. Since in pre-order traversal, we first visit the left node and then the right node, while pushing nodes into the stack, we need to push the right node first and then the left node so that we process the left node first (due to LIFO).
This method iterativePreOrder performs an iterative pre-order traversal of the binary tree. It starts from the root node and uses a stack to keep track of nodes to be visited. It prints the data of each node as it visits them. If a node has a right child, it is pushed onto the stack first so that it is visited after the left child (since pre-order traversal visits the left subtree before the right subtree). Finally, the method returns once all nodes have been visited.
Consider the following binary tree:
Java
1 / \23 / \45
The iterative pre-order traversal will visit the nodes in the order: 1, 2, 4, 5, 3.
Here’s how the execution goes step by step:
Start with an empty stack and initialize the current node as the root.
Push the root node onto the stack.
While the stack is not empty, do the following:
a. Pop the top node from the stack and process it (print its value or perform any other desired operation).
b. Push the right child onto the stack if it exists.
c. Push the left child onto the stack if it exists.
Let’s execute the algorithm step by step:
Start with an empty stack: Stack = []
Push the root node (1) onto the stack: Stack = [1]
Pop the top node from the stack (1), process it: Output = [1], Stack = []
Push the right child (3) onto the stack: Stack = [3]
Push the left child (2) onto the stack: Stack = [3, 2]
Pop the top node from the stack (2), process it: Output = [1, 2], Stack = [3]
Push the right child (5) onto the stack: Stack = [3, 5]
Push the left child (4) onto the stack: Stack = [3, 5, 4]
Pop the top node from the stack (4), process it: Output = [1, 2, 4], Stack = [3, 5]
There’s no left or right child for node 4, so proceed.
Pop the top node from the stack (5), process it: Output = [1, 2, 4, 5], Stack = [3]
There’s no left or right child for node 5, so proceed.
Pop the top node from the stack (3), process it: Output = [1, 2, 4, 5, 3], Stack = []
The stack is empty, so the traversal is complete.
The output of the iterative traversal is: [1, 2, 4, 5, 3], which is the pre-order traversal of the given binary tree.
During the execution of iterative pre-order traversal, we follow the described algorithm. We push the root node onto the stack initially. Then, as long as the stack is not empty, we pop nodes from the stack, print their data, and push their right and left children onto the stack accordingly.
In Order Binary Tree traversal
Traverse the left subtree in In-order fashion.
Visit the root node.
Traverse the right subtree in In-order fashion.
In-order traversal of a binary tree involves visiting the left subtree in in-order fashion, then visiting the root node, and finally traversing the right subtree in in-order fashion.
Recursive In-Order Binary Tree Traversal
In Recursive In-order traversal, we visit each node in the tree in the following order:
If the root is null, indicating an empty subtree, the method returns.
If the root is not null, it recursively traverses the left subtree, then prints the data of the current node, and finally recursively traverses the right subtree.
This process effectively traverses the tree in an in-order sequence.
Consider the same binary tree:
Java
1 / \23 / \45
In in-order traversal, the order of node visits would be: 4, 2, 5, 1, 3.
Here’s how the execution progresses:
in_order_traversal(1) – Traverse left subtree.
in_order_traversal(2) – Traverse left subtree.
in_order_traversal(4) – Visit root node 4.
in_order_traversal(None) – Backtrack to the previous call (in_order_traversal(4)), finish left subtree traversal.
Print root node 2.
in_order_traversal(5) – Visit root node 5.
in_order_traversal(None) – Backtrack to the previous call (in_order_traversal(5)), finish left subtree traversal.
Print root node 1.
in_order_traversal(3) – Traverse right subtree.
Print root node 3.
in_order_traversal(None) – Backtrack to the previous call (in_order_traversal(1)), finish right subtree traversal.
And the output of the traversal will be:
Java
In-order traversal:42513
During the execution of recursive in-order traversal, we maintain a method call stack. For each method call, we keep track of the line number and the root node being passed to that method. Initially, we pass the root node to this method. Then, we visit the left subtree of the root node, print the root node’s data, and finally visit the right subtree of the root node. This tracking of each recursive method call, line number, and root node helps during backtracking.
Iterative In Order Traversal of binary tree in java
In iterative in-order traversal, we visit the left node first, then perform in-order traversal for that node, come back to print the root node’s data, and finally visit the right node to perform its in-order traversal.
To achieve this, we create a stack of TreeNodes and initialize a temp node with the root node. We traverse the tree until the stack is not empty or temp is not null (indicating there are nodes to traverse or backtrack).
If temp is not null, we push it onto the stack and move to its left child. If temp is null, indicating we have reached a leaf node, we pop the top node from the stack, print its data, and move to its right child. This process continues until all nodes are traversed.
This method iterativeInOrderTraversal performs an iterative in-order traversal of the binary tree. It starts from the root node and uses a stack to keep track of nodes to be visited. It traverses the left subtree first, then visits the current node, and finally traverses the right subtree. If a node has a left child, it is pushed onto the stack and the left child becomes the current node. If a node does not have a left child or has already been visited, it is popped from the stack, its data is printed, and its right child becomes the current node. The traversal continues until all nodes have been visited and the stack is empty.
Consider the same binary tree:
Java
1 / \23 / \45
The iterative in-order traversal will visit the nodes in the order: 4, 2, 5, 1, 3.
Here’s how the execution goes step by step:
Start with an empty stack and initialize the current node as the root.
Push the root node onto the stack and move to the left child until reaching a null node.
When a null node is reached, pop the top node from the stack, process it (print its value or perform any other desired operation), and move to its right child.
Let’s execute the algorithm step by step:
Start with an empty stack: Stack = []
Push the root node (1) onto the stack and move to the left child: Stack = [1], Current Node = 1
Move to the left child of 1 (2) and push it onto the stack: Stack = [1, 2], Current Node = 2
Move to the left child of 2 (4) and push it onto the stack: Stack = [1, 2, 4], Current Node = 4
The left child of 4 is null, so pop 4 from the stack, process it: Output = [4], Stack = [1, 2], Current Node = 2
Move to the right child of 4 (null), so no action needed: Output = [4], Stack = [1, 2], Current Node = 2
Process node 2: Output = [4, 2], Stack = [1], Current Node = 2
Move to the right child of 2 (5) and push it onto the stack: Stack = [1, 5], Current Node = 5
The left child of 5 is null, so process node 5: Output = [4, 2, 5], Stack = [1], Current Node = 5
Move to the right child of 5 (null), so no action needed: Output = [4, 2, 5], Stack = [1], Current Node = 5
Process node 1: Output = [4, 2, 5, 1], Stack = [], Current Node = 1
Move to the right child of 1 (3) and push it onto the stack: Stack = [3], Current Node = 3
The left child of 3 is null, so process node 3: Output = [4, 2, 5, 1, 3], Stack = [], Current Node = 3
Move to the right child of 3 (null), so no action needed: Output = [4, 2, 5, 1, 3], Stack = [], Current Node = 3
The stack is empty, so the traversal is complete.
The output of the traversal is: [4, 2, 5, 1, 3], which is the in-order traversal of the given binary tree.
Post Order traversal of Binary Tree
Traverse the left subtree in Post-order fashion.
Traverse the right subtree in Post-order fashion.
Visit the root node.
Recursive Post-Order Traversal of Binary Tree
In recursive post-order traversal, we visit each node in the tree in the following order:
Recursively traverse the left subtree.
Recursively traverse the right subtree.
Visit the root node.
Java
1 / \23 / \45
In post-order traversal, the order of node visits would be: 4, 5, 2, 3, 1.
If the root is null, indicating an empty subtree, the method returns.
If the root is not null, it recursively traverses the left subtree, then recursively traverses the right subtree, and finally prints the data of the current node.
This process effectively traverses the tree in a post-order sequence.
Here’s how the execution progresses:
post_order_traversal(1) – Traverse left subtree.
post_order_traversal(2) – Traverse left subtree.
post_order_traversal(4) – Visit root node 4.
post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(4)), finish left subtree traversal.
post_order_traversal(5) – Visit root node 5.
post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(5)), finish left subtree traversal.
Print root node 2.
post_order_traversal(3) – Traverse right subtree.
Print root node 3.
post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(3)), finish right subtree traversal.
Print root node 1.
post_order_traversal(None) – Backtrack to the previous call (post_order_traversal(1)), finish right subtree traversal.
And the output of the traversal will be:
Java
Post-order traversal:45231
In recursive post-order traversal, we utilize a method call stack. For each recursive call, we visit the left and right nodes respectively, and then print the data of the root node.
To illustrate this, we maintain a method call stack where we track the line number and the root node being passed to that method. This approach ensures that we visit the left and right subtrees first before printing the data of the root node.
Iterative post-order traversal of a binary tree
Iterative post-order traversal is a bit more complex compared to pre-order and in-order traversals because you need to ensure that you visit the left and right subtrees before processing the root node. One common approach to achieve this iteratively is to use two stacks.
This method iterativePostOrderTraversal performs an iterative post-order traversal of the binary tree. It starts from the root node and uses two stacks to keep track of nodes to be visited. It pushes nodes onto stack2 in a pre-order traversal (root, right, left) using stack1. After traversing all nodes, it pops nodes from stack2 to print their data, resulting in a post-order traversal (left, right, root). The traversal continues until all nodes have been visited and both stacks are empty.
Here’s how the execution goes step by step:
Start with two empty stacks: Stack1 and Stack2. Initialize the current node as the root.
Push the root node onto Stack1.
While Stack1 is not empty, do the following: a. Pop the top node from Stack1 and push it onto Stack2. b. Push the left child onto Stack1 if it exists. c. Push the right child onto Stack1 if it exists.
Once Stack1 is empty, all nodes have been pushed onto Stack2. Pop nodes from Stack2 to get the post-order traversal.
Let’s execute the algorithm step by step:
Start with two empty stacks: Stack1 = [], Stack2 = [].
Push the root node (1) onto Stack1: Stack1 = [1].
Pop the top node from Stack1 (1) and push it onto Stack2: Stack2 = [1].
Push the right child (3) onto Stack1: Stack1 = [3].
Push the left child (2) onto Stack1: Stack1 = [3, 2].
Pop the top node from Stack1 (2) and push it onto Stack2: Stack2 = [1, 2].
Push the right child (5) onto Stack1: Stack1 = [3, 5].
Push the left child (4) onto Stack1: Stack1 = [3, 5, 4].
Pop the top node from Stack1 (4) and push it onto Stack2: Stack2 = [1, 2, 4].
Pop the top node from Stack1 (5) and push it onto Stack2: Stack2 = [1, 2, 4, 5].
Pop the top node from Stack1 (3) and push it onto Stack2: Stack2 = [1, 2, 4, 5, 3].
All nodes have been processed and pushed onto Stack2.
Pop nodes from Stack2 to get the post-order traversal: Output = [4, 5, 2, 3, 1].
The output of the traversal is: [4, 5, 2, 3, 1], which is the post-order traversal of the given binary tree.
Level order traversal of a Binary Tree in Java
In level order traversal, also known as breadth-first traversal, we visit each node level by level. To achieve this, we use a queue data structure. Initially, we add the root node to the queue. Then, we iterate while the queue is not empty.
During each iteration, we dequeue a node from the queue and assign it to the temp node. We print the data of this node. If the temp node has left and/or right children, we enqueue them into the queue. This ensures that we traverse the tree level by level, visiting each node before moving on to its children.
This approach is useful for applications like level-wise printing of a binary tree or finding the shortest path in a graph represented as a tree.
This code performs a level-order traversal of the binary tree using a queue. It starts from the root node and adds it to the queue. Then, it repeatedly dequeues nodes from the queue, prints their data, and enqueues their left and right children if they exist. This process continues until all nodes in the tree have been visited.
Bonus: Binary Search in Java
Binary search in Java is a searching algorithm commonly applied to arrays or lists. It is used to find the position of a target value within a sorted array or list.
Binary trees, on the other hand, are a data structure consisting of nodes in a hierarchy, where each node has at most two children, referred to as the left and right child. Binary search trees (BSTs) are a specific type of binary tree where the values are stored in a sorted order, and each node’s value is greater than all values in its left subtree and less than all values in its right subtree.
While binary search and binary trees share the term “binary,” they are distinct concepts and are not directly related in terms of implementation. However, binary search trees leverage the principles of binary search to efficiently search, insert, and delete elements. The property of binary search trees ensures that searching for a value can be performed efficiently, similar to binary search in sorted arrays.
Here’s the explanation and execution of the binary search algorithm in Java
In binary search, we look into the array until the low index becomes greater than the high index. We iterate until this condition holds true.
First, we find the mid index of the array using the formula (high + low) / 2.
If we find the key at the exact mid position, we return that mid index.
If the key is less than the value at the mid index, it means our key is in the first half of the array. So, we update high to mid - 1 and continue searching in that half.
If the key is greater than the value at the mid index, it means our key is in the right side of the array. So, we update low to mid + 1 and continue searching in that half.
If we don’t find the key in the array, we return -1, indicating that the key is not present in the array.
Let’s execute the algorithm step by step:
Java
nums[]:1, 10, 20, 47, 59, 65, 75, 88, 99key:65low = 0, high = 8Iteration 1: mid = (0 + 8) / 2 = 4 nums[mid] = 59Sincekey (65) > nums[mid], update low = mid + 1 = 4 + 1 = 5low = 5, high = 8Iteration 2: mid = (5 + 8) / 2 = 6 nums[mid] = 75Sincekey (65) < nums[mid], update high = mid - 1 = 6 - 1 = 5low = 5, high = 5Iteration 3: mid = (5 + 5) / 2 = 5 nums[mid] = 65Sincekey (65) == nums[mid], return mid = 5 (key found at index 5)Key 65 found at index 5 in the array.
This BinarySearch class implements the binary search algorithm to find the index of a key in a sorted array. The binarySearch method takes an array of integers (nums) and a key to search for. It initializes the low and high pointers to the start and end indices of the array, respectively. Then, it iteratively calculates the mid index, compares the key with the element at the mid index, and updates the low and high pointers accordingly based on whether the key is smaller or larger than the mid element. If the key is found, the method returns the index of the key; otherwise, it returns -1. The main method demonstrates how to use the binarySearch method to search for a key in a sorted array and prints the index of the key.
Conclusion
Binary trees are powerful data structures that offer efficient storage and retrieval of hierarchical data. Understanding their implementation and traversal algorithms is crucial for any Java programmer. By mastering binary trees, you’ll be equipped to tackle a wide range of programming challenges that involve hierarchical data representation and manipulation.