Java NavigableMap Interface

August 4, 2023

What is Java Navigable Map Interface?

NavigableMap is a sub-interface of the Java Map interface that enables developers to implement sorted maps.

It provides methods for navigating through the collection using the keys and their associated values. The NavigableMap interface was introduced in Java 1.6 as part of the Java Collections Framework.

This article will cover everything you need to know about the Java NavigableMap interface, including its definition, implementation, methods, and use cases.

Definition of NavigableMap Interface

The NavigableMap interface is a subtype of the Map interface that provides a sorted map implementation.
It extends the SortedMap interface and adds several methods that enable developers to navigate through the collection using keys and values.
The NavigableMap interface is a powerful tool for implementing sorted maps in Java. It provides methods for navigating through the collection using keys and values, which is useful in sorting and searching algorithms.

2. Implementation of NavigableMap Interface

Implementation of NavigableMap Interface

To implement the NavigableMap interface, you can use one of the built-in classes in the Java Collections Framework, such as TreeMap or ConcurrentSkipListMap.
- TreeMap is a sorted map implementation that uses a Red-Black tree data structure to store the key-value pairs.
- ConcurrentSkipListMap is also a sorted map implementation that uses a skip list data structure to store the key-value pairs. Both classes implement the NavigableMap interface and provide a similar set of methods for navigating through the collection.

NavigableMap Methods

put() Method: The put() method is used to add a key-value pair to the map. If the key already exists, the value associated with the key is updated. The put() method returns the previous value associated with the key, or null if there was no previous value.

ceilingKey() Method The ceilingKey() method returns the least key greater than or equal to the specified key, or null if there is no such key.

descendingKeySet() Method The descendingKeySet() method returns a reverse order NavigableSet view of the keys contained in the map.

subMap() Method The subMap() method returns a view of the portion of the map whose keys range from the specified fromKey, inclusive, to the specified toKey, exclusive.

higherEntry() Method The higherEntry() method returns the least key-value mapping with a key strictly greater than the given key, or null if there is no such key-value mapping.

Use Cases for NavigableMap Interface

The NavigableMap interface is useful in situations where you need to maintain a sorted map and navigate through the map based on keys or values.

It is commonly used in algorithms that require searching, inserting, or deleting elements in a sorted collection. For example, it can be used in implementing binary search or range queries.

Table Of Content

Definition of NavigableMap Interface

Implementation of NavigableMap Interface

NavigableMap Methods

Use Cases for NavigableMap Interface

Advantages and Disadvantages of NavigableMap Interface

Example : Implementation of NavigableMap in TreeMap Class

Introduction to java

static variable in java

If statement in Java

Switch Statement in Java

Abstraction in Java

Advantages of NavigableMap Interface:

The NavigableMap interface provides several advantages over other map implementations. It enables developers to navigate through the collection using keys or values, which is useful in sorting and searching algorithms. It also provides a sorted view of the map, which can be helpful in situations where a specific order is required.

Disadvantages of NavigableMap Interface:

It requires additional memory to maintain the sorting order of the keys. This can lead to slower performance and increased memory usage compared to other map implementations, especially for larger collections.

The NavigableMap interface is not thread-safe. If multiple threads access the map concurrently, it can lead to race conditions and unexpected behavior.

Example 1: Java Program to Implementation of NavigableMap in TreeMap Class

Run

import java.util.*;

public class Main {
    public static void main(String[] args) {
        
        // Creating a TreeMap
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        
        // Adding elements to the TreeMap
        treeMap.put(1, "One");
        treeMap.put(2, "Two");
        treeMap.put(3, "Three");
        treeMap.put(4, "Four");
        treeMap.put(5, "Five");
        
        // Printing the TreeMap
        System.out.println("TreeMap: " + treeMap);
        
        // Using NavigableMap methods
        
        // ceilingKey(K key) - Returns the least key greater than or equal to the given key, or null if there is no such key.
        System.out.println("ceilingKey(3): " + treeMap.ceilingKey(3));
        
        // floorKey(K key) - Returns the greatest key less than or equal to the given key, or null if there is no such key.
        System.out.println("floorKey(3): " + treeMap.floorKey(3));
        
        // higherKey(K key) - Returns the least key strictly greater than the given key, or null if there is no such key.
        System.out.println("higherKey(3): " + treeMap.higherKey(3));
        
        // lowerKey(K key) - Returns the greatest key strictly less than the given key, or null if there is no such key.
        System.out.println("lowerKey(3): " + treeMap.lowerKey(3));
        
        // descendingMap() - Returns a reverse order view of the mappings contained in this map.
        System.out.println("descendingMap(): " + treeMap.descendingMap());
        
        // pollFirstEntry() - Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.
        System.out.println("pollFirstEntry(): " + treeMap.pollFirstEntry());
        
        // pollLastEntry() - Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
        System.out.println("pollLastEntry(): " + treeMap.pollLastEntry());
        
        // Printing the TreeMap after using NavigableMap methods
        System.out.println("TreeMap after using NavigableMap methods: " + treeMap);
    }
}

Output

TreeMap: {1=One, 2=Two, 3=Three, 4=Four, 5=Five}
ceilingKey(3): 3
floorKey(3): 3
higherKey(3): 4
lowerKey(3): 2
descendingMap(): {5=Five, 4=Four, 3=Three, 2=Two, 1=One}
pollFirstEntry(): 1=One
pollLastEntry(): 5=Five
TreeMap after using NavigableMap methods: {2=Two, 3=Three, 4=Four}

Explanation:

This program creates a TreeMap and adds some elements to it. It then uses various NavigableMap methods like ceilingKey(), floorKey(), higherKey(), lowerKey(), descendingMap(), pollFirstEntry(), and pollLastEntry() to demonstrate their implementation. Finally, it prints the TreeMap after using these methods.

Example 2 : Java Program to Implementation of NavigableMap in TreeMap Class

Run

import java.util.*;

 
public class Main
{
  
public static void main (String[]args)
  {
    
 
      // Creating a TreeMap
      TreeMap < String, Integer > treeMap = new TreeMap <> ();
    
 
      // Adding elements to the TreeMap
      treeMap.put ("John", 10);
    
treeMap.put ("Alex", 20);
    
treeMap.put ("Bob", 30);
    
treeMap.put ("Mike", 40);
    
treeMap.put ("Sam", 50);
    
 
      // Printing the TreeMap
      System.out.println ("TreeMap: " + treeMap);
    
 
      // Using NavigableMap methods
      
      // subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) - Returns a view of the portion of this map whose keys range from fromKey to toKey.
      System.out.println ("subMap(\"Alex\", true, \"Mike\", false): " +
			  treeMap.subMap ("Alex", true, "Mike", false));
    
 
      // headMap(K toKey, boolean inclusive) - Returns a view of the portion of this map whose keys are strictly less than toKey.
      System.out.println ("headMap(\"Bob\", true): " +
			  treeMap.headMap ("Bob", true));
    
 
      // tailMap(K fromKey, boolean inclusive) - Returns a view of the portion of this map whose keys are greater than or equal to fromKey.
      System.out.println ("tailMap(\"Bob\", true): " +
			  treeMap.tailMap ("Bob", true));
    
 
      // Printing the TreeMap after using NavigableMap methods
      System.out.println ("TreeMap after using NavigableMap methods: " +
			  treeMap);

} 
}

Output

TreeMap: {Alex=20, Bob=30, John=10, Mike=40, Sam=50}
subMap("Alex", true, "Mike", false): {Alex=20, Bob=30, John=10}
headMap("Bob", true): {Alex=20, Bob=30}
tailMap("Bob", true): {Bob=30, John=10, Mike=40, Sam=50}
TreeMap after using NavigableMap methods: {Alex=20, Bob=30, John=10, Mike=40, Sam=50}

Explanation:

This program also creates a TreeMap and adds some elements to it. It then uses various NavigableMap methods like subMap(), headMap(), and tailMap() to demonstrate their implementation. Finally, it prints the TreeMap after using these methods.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Most Frequently Asked Questions and Answers

Question 1. What is the difference between compile-time polymorphism and runtime polymorphism?

Explanation

Compile-time polymorphism (also known as method overloading) is when multiple methods with the same name but different parameters are defined in a class. The correct method to be called is determined at compile-time based on the method signature.

Runtime polymorphism (also known as method overriding) is when a subclass provides its own implementation of a method that is already defined in its superclass. The correct method to be called is determined at runtime based on the actual object being referenced.

Question 2. What is the difference between method overloading and method overriding?

Explanation

Method overloading is when multiple methods with the same name but different parameters are defined in a class. The methods can have different return types, access modifiers, and exceptions, but must have a different method signature. Method overloading is determined at compile-time based on the method signature.

Method overriding is when a subclass provides its own implementation of a method that is already defined in its superclass. The method must have the same name, return type, and parameters as the method in the superclass. Method overriding is determined at runtime based on the actual object being referenced.

Question 3. Can a subclass override a static method in its superclass?

Explanation

Yes, a subclass can override a static method in its superclass. However, the method in the subclass is not considered to be an override, but rather a new method that hides the static method in the superclass.

Question 4. Can you give an example of how you would use Polymorphism in a real-world scenario?

Explanation

Polymorphism could be used in a real-world scenario is in a payroll system for a company. Each employee could be represented as an object, with different subclasses for different types of employees, such as full-time, part-time, and contract employees. Each subclass could have its own implementation of the calculatePay() method, using different formulas based on the employee type. The payroll system could then call the calculatePay() method on each employee object, and the correct method would be called based on the actual object being referenced, achieving Polymorphism.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Java NavigableMap Interface

What is Java Navigable Map Interface?

Definition of NavigableMap Interface

Implementation of NavigableMap Interface

NavigableMap Methods

Use Cases for NavigableMap Interface

Table Of Content

Example 1: Java Program to Implementation of NavigableMap in TreeMap Class

Output

Example 2 : Java Program to Implementation of NavigableMap in TreeMap Class

Output

Prime Course Trailer

Related Banners

Get over 200+ course One Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription