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).

Lista::Nodo::Nodo(float d, Nodo * a, Nodo * s) : dato{d}, anterior{a}, siguiente{s} {
}

Lista::Lista() : primero{nullptr}, ultimo{nullptr}, talla{0} {
}

void Lista::insertar(float dato, int posicion) { // Suponiendo 0 <= posicion <= talla
   if (primero == nullptr)
      primero = ultimo = new Nodo(dato, nullptr, nullptr);
   else if (posicion == 0) {
      primero = new Nodo(dato, nullptr, primero);
      primero->siguiente->anterior = primero;
   } else if (posicion == talla) {
      ultimo = new Nodo(dato, ultimo, nullptr);
      ultimo->anterior->siguiente = ultimo;
   } else {
      Nodo * actual = primero;
      for (int i = 0; i < posicion; i++)
	 actual = actual->siguiente;
      actual->anterior = new Nodo(dato, actual->anterior, actual);
      actual->anterior->anterior->siguiente = actual->anterior;
   }
   talla++;
}