从列表中移除第一个元素

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.

Persistence

REST