Clases de complejidad para una lista [cerrado] - c ++, matrices, lista, vector, complejidad de tiempo

¿Por qué es que eliminar algo de una matriz o vector es complejo O (n) pero al eliminar algo de una lista es complejidad O (1)?

Respuestas

Cuando eliminas un elemento de un vector y esno en la última posición, debe mover todos los elementos posteriores una posición hacia la izquierda. Esto sucede porque un requisito para el vector es que todos sus elementos forman un bloque continuo de memoria y, por lo tanto, no puede tener "agujeros". Para la lista no hay ningún requisito para el orden en que los elementos se almacenan en la memoria y, por lo tanto, no es necesario moverlos después de eliminar un elemento.

Una lista almacena punteros al siguiente y al anteriorentradas. Entonces, si desea eliminar el elemento (donde ya tiene el iterador / puntero), simplemente se trata de actualizar 2 punteros y eliminar la memoria. Un vector almacena memoria de forma contigua, por lo que cuando elimina un elemento, tiene que mover todos los elementos después de él a una nueva ubicación de memoria (el mejor caso es eliminar el último elemento; no es necesario mover elementos; el peor de los casos es eliminar el primer elemento: todos los demás elementos deben moverse).

Operaciones de lista

x->prev->next = x->next;
x->next->prev = x->prev;
delete x;

Operaciones vectoriales

for x to size - 1
copy next memory block to previous

Cuando elimina un elemento de una matriz (matrices ylos vectores usan memoria contigua), el resto de la matriz necesita moverse. Eso es O (N). En las listas, cada elemento de la lista apunta al siguiente y al anterior, por lo que se desvincula un elemento en O (1), independientemente de la longitud de la lista.