Efficient way to get/remove first element from the list?

Question

I want to take out and remove first element from the List. I can see, I have two options:

First Approach:

LinkedList<String> servers = new LinkedList<String>();
....
String firstServerName = servers.removeFirst();

Second Approach

ArrayList<String> servers = new ArrayList<String>();
....
String firstServerName = servers.remove(0);

I have lot of elements in my list.

• Is there any preference which one we should use?
• And what is the difference between the above two? Are they technically same thing in terms of performance? What is the complexity involve here if we have lot of elements?

What is the most efficient way to do this.

Answer 1

List.subList​(int fromIndex, int toIndex)

Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.

Good to use for ArrayList where removing the first element has complexity O(n).

final String firstServerName = servers.get(0);
servers = servers.subList(1, servers.size());

Answer 2

In practical terms, LinkedList#removeFirst is more efficient since it's operating over a doubly-linked list and the removal of first element basically consist in only unlinking it from the head of the list and update the next element to be the first one:

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

ArrayList#remove is operating over an internal array which requires shiftting all subsequents elements one position to the left by copying over the subarray:

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

On the other hand, LinkedList#get operation requires traversing half of the entire list for retrieving an element at a specified index - in worst case scenario. ArrayList#get would directly access the element at the specified index since it's operating over an array.

My rule of thumbs for efficiency here would be:

• Use LinkedList if you do a lot of add/remove in comparison with retrieval operations (e.g.: get);
• Use ArrayList if you do a lot of retrieval operations in comparison with add/remove.