1ra parte:-
Estaba leyendo en el libro "Estructura de datos y algoritmos simplificados en Java" que la complejidad del tiempo para eliminar el último elemento de Linkedlist y Arraylist es O (n). Pero Linkedlist implementa internamente DoublyLinkedlist, por lo que la complejidad del tiempo debe ser O (1) y, de manera similar, para Arraylist, ya que implementa internamente Array, debe ser O (1).
2da parte:-
También dice que la inserción de un elemento al final de una lista enlazada tiene una complejidad de tiempo de O(n) pero la lista enlazada mantiene punteros tanto al final como al principio. Entonces, ¿es correcta esta afirmación? Además, dice que la complejidad del tiempo para insertar un elemento en una lista de arreglos al final es O (1) si el arreglo no está lleno y O (n) si el arreglo está lleno. ¿Por qué O (n) si la matriz está llena?
Gracias por contestar la 1ra parte. ¿Alguien puede explicar también la segunda parte? Gracias :)
Depende de los métodos que estés llamando.
Un vistazo a la implementación muestra que si está llamando a LinkedList.removeLast() , eso es O(1). LinkedList mantiene punteros tanto al primer como al último nodo de la lista. Por lo tanto, no tiene que atravesar la lista para llegar al último nodo.
Llamar a LinkedList.remove(index) con el índice del último elemento también es O(1), porque atraviesa la lista desde el extremo más cercano. [Notado por el usuario @andreas en el comentario a continuación.]
Pero si está llamando a LinkedList.remove(Object) , entonces hay una búsqueda O(n) para el primer nodo coincidente.
De manera similar, para ArrayList, si está llamando a ArrayList.remove(index) con el índice del último elemento, entonces eso es O(1). Para todos los demás índices, hay una llamada System.arrayCopy() que puede ser O(n), pero se omite por completo para el último elemento.
Pero si llama a ArrayList.remove(Object) , nuevamente hay una búsqueda O(n) para el primer nodo coincidente.