Introduction
One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.
LinkedHashMap is a Java predefined class similar to HashMap, which contains keys and their respective values. The order of insertion in LinkedHashMap is preserved.
The objective is to retrieve the first and last entries in the LinkedHashMap. The last and first values are obtained by iteration. The first and last entries in LinkedHashMap are the first and last entries that are inserted in the LinkedHashMap, as the insertion order is retained.
Approach and Algorithm 1
This is going to be a Naive approach. We are going to use the for-each loop to iterate over the LinkedHashMap.
We will construct two functions:
getFirst()
- This function will print the first entry of the LinkedHashMap.
- We will traverse the LinkedHashMap and maintain a counter, which will initially be 1 and will be incremented by 1 in every iteration.
- During the traversal, when the counter will be equal to 1, we will print the values, as counter = 1 means that we are standing at the first element.
getLast()
- This function will print the last entry of the LinkedHashMaop.
- We will traverse the LinkedHashMap and maintain a counter, which will initially be 1 and will be incremented by 1 in every iteration.
- During the traversal, when the counter will be equal to the size of the LinkedHashMap, we will print the values, as counter = LinkedHashMap.size() means that we are standing at the last element.
Sample Input
[ [1,2] , [3,4] , [5,6] ]
Sample Output
First Key = 1 , First Value = 2
Last Key = 5 , Second Value = 6
Explanation: As we can see, the first and last key-value pairs have been printed.
Code Implementation
import java.util.*;
import java.io.*;
public class PrepBytes {
// Get the last entry of the map
public static void
getLast(LinkedHashMap LinkedHMap)
{
int count = 1;
for (Map.Entry it :
LinkedHMap.entrySet()) {
if (count == LinkedHMap.size()) {
System.out.println("Last Key-> "+it.getKey());
System.out.println("Last Value-> "+it.getValue());
return;
}
count++;
}
}
// Get the First entry of the map
public static void
getFirst(LinkedHashMap LinkedHMap)
{
int count = 1;
for (Map.Entry it :
LinkedHMap.entrySet()) {
if (count == 1) {
System.out.println("First Key-> "+it.getKey());
System.out.println("First Value-> "+it.getValue());
return;
}
count++;
}
}
public static void main(String[] args)
{
LinkedHashMap LinkedHMap
= new LinkedHashMap<>();
LinkedHMap.put(1, 2);
LinkedHMap.put(3,4);
LinkedHMap.put(5, 6);
getFirst(LinkedHMap);
getLast(LinkedHMap);
}
}
Output
First Key-> 1
First Value-> 2
Last Key-> 5
Last Value-> 6
Time Complexity:
- Getfirst() – O(1), as we only need the first element of the LinkedHashMap
- Getlast() – O(n), as LinkedHashMap traversal is needed.
Space Complexity:
For both the methods, the space complexity is O(1), as no extra space is being used.
Approach and Algorithm 2
- In this approach, we will convert the keys of the LinkedHashMap to an array, with the help LinkedHashMap.keySet().toArray( new Integer[ LinkedHashMap.size()] ) method. This method converts the keys of the LinkedHashMap into an array.
- After converting, we will simply print the key-value pair at the 0-th index, as it will be our first element and print the key-value pair at the keys.length-1 th index as it will be the last key-value pair.
Sample Input
[ [1,2] , [3,4] , [5,6] ]
Sample Output
First Key = 1 , First Value = 2
Last Key = 5 , Second Value = 6
Explanation: As we can see, the first and last key-value pairs have been printed.
Code Implementation
import java.util.*;
import java.io.*;
public class PrepBytes {
public static void main(String[] args)
{
LinkedHashMap LinkedHMap
= new LinkedHashMap<>();
LinkedHMap.put(1, 2);
LinkedHMap.put(3, 4);
LinkedHMap.put(5, 6);
Integer[] keys
= LinkedHMap.keySet().toArray(new Integer[LinkedHMap.size()]);
if (keys.length > 0) {
System.out.println("First key-> " + keys[0]);
System.out.println("First value-> "
+ LinkedHMap.get(keys[0]));
System.out.println("Last key-> "
+ keys[keys.length - 1]);
System.out.println(
"Last value-> "
+ LinkedHMap.get(keys[keys.length - 1]));
}
}
}
Output
First Key-> 1
First Value-> 2
Last Key-> 5
Last Value-> 6
Time Complexity: For both methods, the time complexity is O(1), as we are accessing the elements with the help of indexes.
Space Complexity: For both methods, the space complexity is O(N), as we are creating an array that consists of N keys.
Approach and Algorithm 3
- In this approach, we will convert the keys of the LinkedHashMap to an array with the help of LinkedHashMap.keySet() method. This method converts all the keys to a list like structure – ArrayList or LinkedList.
- After converting, we will simply print the key-value pair at the 0-th index, as it will be our first element and print the key-value pair at the LinkedHashMap.size() -1 index as it will be the last key-value pair.
Sample Input
[ [1,2] , [3,4] , [5,6] ]
Sample Output
First Key = 1, First Value = 2
Last Key = 5, Second Value = 6
Explanation: As we can see, the first and last key-value pairs have been printed.
Code Implementation
import java.util.*;
import java.io.*;
public class PrepBytes {
public static void main(String[] args)
{
LinkedHashMap LinkedHMap
= new LinkedHashMap<>();
LinkedHMap.put(1, 2);
LinkedHMap.put(3, 4);
LinkedHMap.put(5, 6);
List lKeys
= new ArrayList(LinkedHMap.keySet());
if (lKeys.size() > 0) {
System.out.println("First key-> "
+ lKeys.get(0));
System.out.println("First value-> "
+ LinkedHMap.get(lKeys.get(0)));
System.out.println(
"Last key-> " + lKeys.get(lKeys.size() - 1));
System.out.println(
"Last value-> "
+ LinkedHMap.get(lKeys.get(lKeys.size() - 1)));
}
}
}
Output
First Key-> 1
First Value-> 2
Last Key-> 5
Last Value-> 6
Time Complexity: For both methods, the time complexity is O(1), as we are accessing the elements with the help of indexes.
Space Complexity: For both methods, the space complexity is O(N), as we are creating a list-like structure that consists of N keys.
So, in this article, we have tried to explain the most efficient way to get the first or last entry from Java LinkedHashMap. Java Collection Framework is very important when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.