As many other algorithms in Linked List – remove element from given position runs in linear time. Here we are going to implement it to better understand how it works.
In previous posts we’ve implemented add, count, print contents, and insert methods for a Linked List. Now we will implement removal of element from selected position.
Linked List – remove element at position
As previously, we base our Linked List implementation on Node class, we’ve defined in the first post.
public void remove(int position) {
Node<T> prev = null, node = head;
// Find node to remove:
while (position > 0 && node != null) {
--position;
prev = node;
node = node.next;
}
// If exists, unpin it from the list:
if (node != null) {
if (prev == null) {
// Removed 1st, so change the head:
head = node.next;
} else {
// Just connect prev with next:
prev.next = node.next;
}
}
}
How it works
The algorithm consists of two parts. First, we have to find the node we want to remove and remember its predecessor, so that we could connect it to the next node.
In the second part, if the node was found, we have to handle two cases. If we remove a node from the first position, it means we are removing the head, therefore we have to promote the next node to be the new head. In every other case we just need to connect previous node with the node after the removed one.
Performance
It’s pretty clear that in the worst case – removal of element from the last position – we have to iterate through whole Linked List. Thus the algorithm runs in linear time – O(n).
Unit Tests
Let’s write a simple unit tests to see how the algorithm works:
package com.farenda.tutorials.algorithms.lists;
import org.junit.Test;
import static org.junit.Assert.*;
public class LinkedListTest {
private LinkedList<Integer> list = new LinkedList<>();
@Test
public void shouldRemoveElements() {
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.printContent();
list.remove(3);
assertEquals(3, list.size());
list.printContent();
list.remove(0);
assertEquals(2, list.size());
list.printContent();
list.remove(0);
assertEquals(1, list.size());
list.printContent();
list.remove(0);
assertEquals(0, list.size());
list.printContent();
}
}
The above code produces the following output:
[1,2,3,4] [1,2,3] [2,3] [3] []
