从列表中删除对象 [英] Remove a object from List

问题描述

如果我需要从List中删除一个对象，则希望删除哪一个，假设字符串"abc"
linkedList还是ArrayList? (我认为两者都相同)
如果我使用Linkedlist和arraylist，那么时间和空间的复杂性是什么?
(我相信两者的时间复杂度都为O(n)

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)

推荐答案

两者都具有相同的时间复杂度-O(n)，但是恕我直言，LinkedList版本会更快，尤其是在大型列表中，因为删除时数组(ArrayList)中的一个元素，右侧的所有元素都必须向左移动-以便填充空的数组元素，而LinkedList只需重新布线4个引用

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)

这篇关于从列表中删除对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！