In this post, we are going to discuss the get(), getFirst() and getLast() method of the LinkedList class. A linked list doesn’t allow random access to the elements, but it provides us with certain methods to access the elements of a list. Below are some of these methods
Let’s look at them one by one.
public E get(int index)
- What does it do? It will retrieve the element present at the specified index. Remember, here, the indexing is 0-based, which means to fetch the second element, we have to pass 1 as an index in the function‘s argument.
- What does it return? It will return the element present at the given index. If the index exceeds the linked list’s size, it will throw an IndexOutOfBoundsException.
Code Example
import java.util.LinkedList;
public class Codekru {
public static void main(String[] args) {
LinkedList<Object> linkedList = new LinkedList<>();
// adding into the linked list
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
System.out.println(linkedList.get(1)); // fetching second element by passing 1 in the function
}
}
Output –
second
get() method tries to retrieve the index in the best possible way means if the index is in the first half, it will retrieve it using the first(head) node, and if not, it will retrieve the element using the last node.
The time complexity of the get() method
- Best case time complexity – Best case scenario would be when we have to get the first or the last index, and the time complexity would be O(1)
- Worst case time complexity – Worst case scenario would be when we have to get the middle element of the linked list, and in that case, the time complexity would be O(n/2)
So, the average time complexity of the get() method would be O(n/2).
What if we passed an index >= array’s length into the get() function argument?
We will get IndexOutOfBoundsException as shown in the below program, so we don’t recommend doing it 😛
public class Codekru {
public static void main(String[] args) {
LinkedList<Object> linkedList = new LinkedList<>();
// adding into the linked list
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
System.out.println(linkedList.get(4)); // passed 4 in the function which is greater than array's length(3)
}
}
Output –
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 4, Size: 3
at java.base/java.util.LinkedList.checkElementIndex(LinkedList.java:559)
at java.base/java.util.LinkedList.get(LinkedList.java:480)
What if we try to use the get() function on a null LinkedList?
public class Codekru {
public static void main(String[] args) {
LinkedList<Object> linkedList = new LinkedList<>();
System.out.println(linkedList.get(1));
}
}
Output –
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 0
at java.base/java.util.LinkedList.checkElementIndex(LinkedList.java:559)
at java.base/java.util.LinkedList.get(LinkedList.java:480)
public E getFirst()
It will return the first element present in the linked list, and if the linked list is empty, it will throw a NoSuchElementException.
import java.util.LinkedList;
public class Codekru {
public static void main(String[] args) {
LinkedList<Object> linkedList = new LinkedList<>();
// adding into the linked list
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
System.out.println("First element of the linked list is: "+linkedList.getFirst()); // getting the first element present in the linked list
}
}
Output –
First element of the linked list is: first
Internal implementation of the getFirst() method
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
As we can see here, the getFirst() is just returning the value present at the first(head) node itself.
The time complexity of the getFirst() method
The time complexity of the getFirst() method would be O(1) as we are just fetching the value from the first node.
What if we try to use the getFirst() method on a null LinkedList?
In this scenario, we will get the NoSuchElementException as shown using the below program.
public class Codekru {
public static void main(String[] args) {
LinkedList<Object> linkedList = new LinkedList<>();
System.out.println("first element of the linked list is: " + linkedList.getFirst());
}
}
Output –
Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.LinkedList.getFirst(LinkedList.java:248)
public E getLast()
It will return the last element present in the linked list, and if the linked list is empty, it will throw a NoSuchElementException.
import java.util.LinkedList;
public class Codekru {
public static void main(String[] args) {
LinkedList<Object> linkedList = new LinkedList<>();
// adding into the linked list
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
System.out.println("Last element of the linked list is: " + linkedList.getLast()); // getting the last element
// present in the linked list
}
}
Output –
Last element of the linked list is: third
Internal implementation of the getLast() method
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
The linked list keeps track of the last node, and the getLast() method returns the value present at that last node.
The time complexity of the getLast() method
The time complexity of the getLast() method would be O(1) as we are fetching the value from the last node.
Now, what if we try to use the getLast() function too on a null LinkedList?
We will get the NoSuchElementException exception in this scenario too
public class Codekru {
public static void main(String[] args) {
LinkedList<Object> linkedList = new LinkedList<>();
System.out.println("Last element of the linked list is: " + linkedList.getLast());
}
}
Output –
Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.LinkedList.getLast(LinkedList.java:261)
Please visit this link to learn more about the linked list class and its methods.
We hope that you have liked this article. If you have any doubts or concerns, please feel free to write us in the comments or mail us at admin@codekru.com.