Remove the First Element from a List

1. Overview

In this super-quick tutorial, we’ll show how to remove the first element from a List.

We’ll perform this operation for two common implementations of the List interface – ArrayList and LinkedList.

2. Creating a List

Firstly, let’s populate our Lists:

@Before
public void init() {
    list.add("cat");
    list.add("dog");
    list.add("pig");
    list.add("cow");
    list.add("goat");

    linkedList.add("cat");
    linkedList.add("dog");
    linkedList.add("pig");
    linkedList.add("cow");
    linkedList.add("goat");
}

3. ArrayList

Secondly, let’s remove the first element from the ArrayList, and make sure that our list doesn’t contain it any longer:

@Test
public void givenList_whenRemoveFirst_thenRemoved() {
    list.remove(0);

    assertThat(list, hasSize(4));
    assertThat(list, not(contains("cat")));
}

As shown above, we’re using remove(index) method to remove the first element – this will also work for any implementation of the List interface.

4. LinkedList

LinkedList also implements remove(index) method (in its own way) but it has also the removeFirst() method.

Let’s make sure that it works as expected:

@Test
public void givenLinkedList_whenRemoveFirst_thenRemoved() {
    linkedList.removeFirst();

    assertThat(linkedList, hasSize(4));
    assertThat(linkedList, not(contains("cat")));
}

5. Time Complexity

Although the methods look similar, their efficiency differs. ArrayList‘s remove() method requires O(n) time, whereas LinkedList‘s removeFirst() method requires O(1) time.

This is because ArrayList uses an array under the hood, and the remove() operation requires copying the rest of the array to the beginning. The larger the array is, the more elements need to be shifted.

Unlike that, LinkedList uses pointers meaning that each element points to the next and the previous one.

Hence, removing the first element means just changing the pointer to the first element. This operation always requires the same time not depending on the size of a list.

6. Conclusion

In this article, we’ve covered how to remove the first element from a List, and have compared the efficiency of this operation for ArrayList and LinkedList implementations.

As usual, the complete source code is available over on GitHub.

Related posts:

Java Program to Implement Hash Tables Chaining with List Heads
Spring Cloud – Bootstrapping
Difference Between Wait and Sleep in Java
The Basics of Java Security
HttpClient 4 Cookbook
Java Program to Implement Euclid GCD Algorithm
Java Program to Perform Preorder Non-Recursive Traversal of a Given Binary Tree
Giới thiệu Java Service Provider Interface (SPI) – Tạo các ứng dụng Java dễ mở rộng
Jackson vs Gson
Giới thiệu Design Patterns
Phân biệt JVM, JRE, JDK
Spring Data Java 8 Support
4 tính chất của lập trình hướng đối tượng trong Java
Hướng dẫn sử dụng Java Reflection
A Guide to Java 9 Modularity
Intro to Inversion of Control and Dependency Injection with Spring
Introduction to Spring Cloud OpenFeign
Java Program to Perform Searching Using Self-Organizing Lists
Java Program to Implement Range Tree
Java Program to Implement Sorted Doubly Linked List
Java Program to Construct an Expression Tree for an Infix Expression
Guide to DelayQueue
Java Program to Generate All Possible Subsets with Exactly k Elements in Each Subset
OAuth2 for a Spring REST API – Handle the Refresh Token in AngularJS
Java Program to Implement String Matching Using Vectors
Java Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers
Java Program to Find All Pairs Shortest Path
Java Program to Construct an Expression Tree for an Postfix Expression
Hướng dẫn Java Design Pattern – Transfer Object
ArrayList trong java
Từ khóa static và final trong java
The Spring @Controller and @RestController Annotations