Удалить объект из списка

Question

, который вы отправляете для удаления, если мне нужно удалить объект из списка, предположим, что строка «abc»
linkedList или ArrayList? (Я думаю, оба же)
и что время и пространство сложности, если я иду с LinkedList и ArrayList
(я считаю, что оба будут иметь одинаковую временную сложность O (п)

Answer 1

Оба будут иметь одинаковая сложность - O (n), но IMHO, версия LinkedList будет быстрее, особенно в больших списках, потому что когда вы удаляете элемент из массива (ArrayList), все элементы справа должны сдвинуться влево - чтобы заполнить в элементе опустошенного массива, в то время как LinkedList нужно будет только переписать 4 ссылки

Ниже приведены временные сложности метода других списков:

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)