Algoritmos y Estructuras de Datos (VJ1215)

La siguiente solución tiene los siguientes costes, siendo n la talla de la lista:

• Coste temporal en el peor caso: O(n).

• Coste temporal en el mejor caso: O(1).

void Lista::eliminar(int posicion) { // Suponiendo 0 <= posicion < talla
   if (talla == 1) {
      delete primero;
      primero = ultimo = nullptr;
   } else if (posicion == 0) {
      Nodo * basura = primero;
      primero = primero->siguiente;
      primero->anterior = nullptr;
      delete basura;
   } else if (posicion == talla - 1) {
      Nodo * basura = ultimo;
      ultimo = ultimo->anterior;
      ultimo->siguiente = nullptr;
      delete basura;
   } else {
      Nodo * basura = primero;
      for (int i = 0; i < posicion; i++)
	 basura = basura->siguiente;
      basura->anterior->siguiente = basura->siguiente;
      basura->siguiente->anterior = basura->anterior;
      delete basura;
   }
   talla--;
}