Last Updated on March 10, 2022 by Ria Pathak
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.
Poll is a method in Java’s Linked list class that enables Queue Based functioning. This function deletes the elements at the front of the container and returns it, and so it has a wide range of applications in day-to-day problems and competitive programming.
There are 3 different variation of poll() function. We will discuss all of them in detail in this article.
poll() Method
This method deletes the head of the list and returns it.
Syntax: public E poll()
Return Value: This function returns the first element (head) of the linked list if there are elements in the list, and if the list is empty, it returns null.
We will simply call the list. poll() to use this method.
Input: [1 , 2 , 3 ,4 ]
- After using list.poll()
Output: 1 is displayed, and the resultant list is [ 2, 3, 4 ].
Explanation: As we can see, after using list.poll(), the head of the list is displayed and deleted from the list.
Code Implementation
import java.util.*;
public class LinkedListPoll {
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println("The initial Linked List is : " + list);
System.out.println("Head of the list is : " + list.poll());
System.out.println("Linked List after removal of head using poll() : " + list);
}
}
Output
The initial Linked List is : [1, 2, 3, 4]
Head of the list is: 1
Linked List after removal of head using poll() : [2, 3, 4]
Time Complexity: O(1), as we are only accessing the head of the list.
Space Complexity: O(1), as no extra space is required.
pollFirst() Method
The pollFirst() method is very similar to the poll() method. It, too, returns and removes the head (first element) of the list.
Syntax: public E pollFirst()
Return Value: This function returns the first element (head) of the linked list if there are elements in the list, and if the list is empty, it returns null.
We will simply call the list.pollFirst() to use this method.
Input: [1 , 2 , 3 ,4 ]
- After using list.pollFirst().
Output: 1 is displayed, and the resultant list is [ 2, 3, 4 ].
Explanation: As we can see, after using list.pollFirst(), the first element of the list is deleted and returned.
Code Implementation
import java.util.*;
public class LinkedListPoll {
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println("The initial Linked List is : " + list);
System.out.println("Head of the list is : " + list.pollFirst());
System.out.println("Linked List after removal of the head using pollFirst() : " + list);
}
}
Output
The initial Linked List is : [1, 2, 3, 4]
Head element of the list is : 1
Linked List after removal of the head using pollFirst() : [2, 3, 4]
Time Complexity: O(1), as we are only accessing the head of the list.
Space Complexity: O(1), as no extra space is required.
pollLast() Method
This method returns the last element of the LinkedList and also removes it from the list.
Syntax: public E pollLast()
Return Value: The function returns the last element of the list if there are elements in the list, and if the list is empty, it returns null.
We will simply call the list.pollLast() to use this method.
Input: [1 , 2 , 3 ,4 ]
- After using list.pollLast().
Output: 4 is displayed, and the resultant list is [ 1, 2, 3 ].
Explanation: As we can see, after using list.pollLast(), the last element of the list is returned and deleted from the list.
Code Implementation
import java.util.*;
public class LinkedListPoll {
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println("The initial Linked List is : " + list);
System.out.println("Last element of the list is : " + list.pollLast());
System.out.println("Linked List after removal of last elements using pollLast() : " + list);
}
}
Output
The initial Linked List is : [1, 2, 3, 4]
Last element of the list is : 4
Linked List after removal of last element using pollLast() : [ 1, 2, 3 ]
Time Complexity: O(1), as the list is doubly-linked list, and we have direct access to the head and the tail of the list , So, accessing the last element takes O(1).
Space Complexity: O(1), as no extra space is required.
Practical Application
As discussed in the beginning, this method has great usage in queue management systems.
Let us have a look at the example:
Suppose some people are standing in the queue, and we need to find the order of exit of these peoples from the queue.
- So, here with the help of poll() method, we can find the order of exit.
Input: [ "Aman", "Akash", "Sonam" ]
Output: Order of exit: Aman < – Akash < – Sonam
Explanation: As we can see, the order of exit (the order in which people are standing in the queue) has been displayed.
To complete this task, we will simply traverse the list and do a list.poll() in every iteration. By doing this, the 1st person is being displayed and removed from the list, hence fulfilling our criteria.
Code Implementation
import java.util.*;
public class LinkedListPollApp {
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.add("Aman");
list.add("Akash");
list.add("Sonam");
System.out.println("The initial queue is : " + list);
System.out.print("The order of exit is : ");
while (!list.isEmpty()) {
System.out.print(list.poll() + " <-- ");
}
}
}
Output
The initial queue is : [Aman, Akash, Sonam]
The order of exit is: Aman <– Akash <– Sonam <–
Time Complexity: O(N), as we are traversing the list.
[forminator_quiz id=”5350″]
So, in this article, we have tried to explain how to use poll(), pollFirst() and pollLast() methods in Java with examples. The knowledge of different functions of LinkedList class is 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.