The remove methods of the Linked List class are used to remove an element from the linked list. This post will discuss the remove methods in the Linked List class of java.
We have three overloaded remove method implementations in the Linked List class –
Let’s discuss each of the functions in detail
public E remove()
remove() method was introduced in Java 5.
- What does it do? It removes the head node from the linked list, and after removing it, the size of the linked list is reduced by 1.
- What does it return? It returns the value present at the head of the linked list, or we can say that it returns the first element of the linked list.
Code Example
import java.util.LinkedList;
public class Codekru {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<String>();
// adding elements to the list
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
System.out.println("Linked list before using remove method: " + linkedList);
String headOfLinkedList = linkedList.remove(); // removing the first element
System.out.println("Head of the linked list was: " + headOfLinkedList);
System.out.println("Linked list after using remove method: " + linkedList);
}
}
Output –
Linked list before using remove method: [first, second, third]
Head of the linked list was: first
Linked list after using remove method: [second, third]
Internal implementation of the remove() method
remove() method internally uses the removeFirst() function, shown in the implementation below.
public E remove() {
return removeFirst();
}
Time complexity of the remove() method
The time complexity of the remove() method is O(1) as it uses the removeFirst() method internally, which further has a time complexity of O(1).
public E remove(int index)
- What does it do? It will remove the element present at the index passed in the argument.
- Remember, the indexing here is 0-index, which means if you want to delete the 3rd element of the linked list, then you have to pass index as 2 in the argument.
- After removing the element from the list, the subsequent elements will be shifted to the left.
- What does it return? It will return the removed element of the linked list, and if the index >= size of the linked list, it will give the IndexOutOfBoundsException exception.
import java.util.LinkedList;
public class Codekru {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<String>();
// adding elements to the list
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
System.out.println("Linked list before using remove method: " + linkedList);
String removedElement = linkedList.remove(1); // removing the second element by passing index as 1
System.out.println("Removed element was: " + removedElement);
System.out.println("Linked list after using remove method: " + linkedList);
}
}
Output –
Linked list before using remove method: [first, second, third]
Removed element was: second
Linked list after using remove method: [first, third]
Internal implementation of the remove(int index) method
remove(int index) internally uses two methods – node() and unlink().
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
Time complexity of the remove(int index) method
As remove(int index) method internally uses the unlink() and node() method. So, its time complexity would also depend on these methods.
node() method has an average time complexity of O(n) with the best-case complexity of O(1) and worst-case complexity of O(1). At the same time, the unlink() method has the complexity of O(1).
- Best case time complexity – The best-case scenario would be when we have to remove the head node from the linked list, and its time complexity would be O(1)
- Worst-case time complexity – The worst-case scenario is when we have to remove the last node from the list, and its time complexity would be O(n)
So, the average time complexity of remove(int index) is O(n).
public boolean remove(Object o)
- What does it do? It will remove the first occurrence of the object passed in the arguments.
- What does it return? It will return true if the specified object is removed from the list. Otherwise, it will return false if the object is not found.
import java.util.LinkedList;
public class Codekru {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<String>();
// adding elements to the list
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
System.out.println("Linked list before using remove method: " + linkedList);
String string = "third";
System.out.println("is \"third\" present in the linked list: " + linkedList.remove(string)); // removing the "third" string
String string2 = "codekru";
System.out.println("is \"last\" present in the linked list: " + linkedList.remove(string2)); // As "codekru" string
// is not present in
// the linked list, so,
// it will return false
System.out.println("Linked list after using remove method: " + linkedList);
}
}
Output –
Linked list before using remove method: [first, second, third]
is "third" present in the linked list: true
is "last" present in the linked list: false
Linked list after using remove method: [first, second]
Internal implementation of the remove(Object o) method
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
Time complexity of the remove(Object o) method
The remove(Object o) time complexity is O(n) as it runs a loop over the linked list elements.
The What If scenarios
Q – What if we use the remove() method on an empty Linked List?
We will get a NoSuchElementException exception.
import java.util.LinkedList;
public class Codekru {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<String>();
String headOfLinkedList = linkedList.remove(); // removing the first element
}
}
Output –
Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.LinkedList.removeFirst(LinkedList.java:274)
at java.base/java.util.LinkedList.remove(LinkedList.java:689)Q – What if we use index >= size in remove(int index) method?
Here, we will get an IndexOutOfBoundsException as the index value can only be between 0 and size-1.
import java.util.LinkedList;
public class Codekru {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<String>();
// adding elements to the list
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");
String removedElement = linkedList.remove(3);
}
}
Output –
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3, Size: 3
at java.base/java.util.LinkedList.checkElementIndex(LinkedList.java:559)
at java.base/java.util.LinkedList.remove(LinkedList.java:529)We recommend reading this article to learn more about the linked list and its methods.
We hope that you have liked the article. If you have any doubts or concerns, please feel free to write us in the comments or mail us at admin@codekru.com.