Remove a object from List

Question

which one you perfer to remove if i need to remove a object from List , suppose String "abc"
linkedList or ArrayList ? ( I think, both are same)
and what is the time and space complexity if i go with Linkedlist and arraylist
(I believe that both will have same time complexity of O(n)

Answer 1

Both will have the same time complexity - O(n), but IMHO, the LinkedList version will be faster especially in large lists, because when you remove an element from array (ArrayList), all elements on the right will have to shift left - in order to fill in the emptied array element, while the LinkedList will only have to rewire 4 references

Here are the time complexities of the other list methods:

For LinkedList<E>

    get(int index) - O(n)
    add(E element) - O(1)
    add(int index, E element) - O(n)
    remove(int index) - O(n)
    Iterator.remove() is O(1) 
    ListIterator.add(E element) - O(1) 

For ArrayList<E>

    get(int index) is O(1) 
    add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
    add(int index, E element) is O(n - index) amortized,  O(n) worst-case 
    remove(int index) - O(n - index) (removing last is O(1))
    Iterator.remove() - O(n - index)
    ListIterator.add(E element) - O(n - index)