How remove(Object obj) method in List in java is implemented?

Question

Can someone give the implementation of remove(Object obj) method is List in java?

How and where is this overloaded method defined and what is the implementation in ArrayList?

The second part of the question is between an ArrayList and LinkedList the remove(int index) method will work faster in ArrayList because of the underlying implementation(one is array and other linkedlist). But what about remove(object obj) method? Which one will be faster? Because according to my understanding both will take same time. In ArrayList the iteration will be on contiguous memory locations whereas for LinkedList it won't be. But we have to basically iterate over each element and check using equals which object needs to be fetched.

EDIT:

I just thought I will give some background why I am asking this question. Often we are asked for frequent insertion and deletion which List is best to use. And I am very much confused regarding this. If we use the remove(int index) method ArrayList can jump to the location(move the underlying pointer and delete the object) and then shift the elements whereas for LinkedList it needs to traverse from the headNode to the index and change the nextNode to point to the later value. Which will be faster and why? What happens when we start using the remove(Object o) method?Some information: When to use LinkedList over ArrayList?

Answer 1

You may thing that remove(int index) on an ArrayList is faster than remove(int index) on a LinkedList, but that's not the case.

Why? You're ignoring one of the largest costs to an ArrayList: how much it actually costs to resize the array after an element is removed.

The actual implementation for the ArrayList is provided here:

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;
}

Now, that System.arraycopy call is actually doing the work of copying your existing array halves into new memory, lining them up contiguously, and then cleaning up after itself. Effectively, every element is shifted to the left by 1 after this entire operation.

Regardless as to where this operation was performed (front of list, middle of list, end of list), you're copying n-1 elements into contiguous memory. That's an O(n) operation.

Now, compare/contrast with LinkedList's implementation (checkElementIndex is omitted as it is intuitive):

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

The implementation will either search from the rear or from the front, depending on which is closer (hence the bitwise division by two, or size >> 1). There is work involved in actually finding the location, but once it is found, a very specific and non-size-dependent set of steps is done to ensure that the integrity of the list is preserved.

So, regardless of where I remove this one element (front, middle, end), I'm doing about the same unit of work to both delete the node and adjust my list. Hence, the runtime operation could be considered about constant time.

Addendum:

To further your reading, the addition of an element in an ArrayList would behave in a similar manner as to when you're removing an element - you have to take into account that your underlying array may need to be resized before you can enter, and if you enter 10,000 elements and undergo 1,000 resizes, you're inserting data on the order of O(n).

Contrast inserting in a LinkedList, which only inserts at either the front or the end; both of which are directly accessible, do not involve anything with the original array whatsoever, and can be done in constant time.