Tengo una lista que quiero recorrer, a veces de principio a fin, a veces de principio a fin. Esta lista nunca se modifica y la recorreré varias veces. Me gustaría evitar la operación de invertir la lista en O (n) cuando quiero iterar de un extremo a otro.

¿Existe alguna estructura de datos que lo permita?

Estaba pensando que sería simple para la implementación (doble) LinkedList en C # permitir este comportamiento (manteniendo una referencia interna de lo que es el comienzo de la lista), pero no creo que esté implementado de esa manera. ¿Puede proporcionar un enlace si me equivoco?

2
Gradient 25 oct. 2019 a las 03:44

1 respuesta

La mejor respuesta

Cualquier estructura de datos con acceso directo indexado y longitud (matrices, listas, cadenas, flujos de archivos) permite la representación de completar "reverso" en el tiempo O (1) (tenga en cuenta que es inverso, obviamente, la iteración de todos los elementos seguirá siendo O (n) .

Hay varios ejemplos en ¿Es posible iterar hacia atrás a través de un foreach? con "yield return" sugerido por Jon Skeet es la forma más flexible (probablemente un poco menos de rendimiento que solo hacia atrás {{X0} }):

public static IEnumerable<T> FastReverse<T>(this IList<T> items)
{
    for (int i = items.Count-1; i >= 0; i--)
    {
        yield return items[i];
    }
}

Como Patrick Roberts comentó, puede También use otra estructura de datos que se parezca a una matriz, es decir, un diccionario con claves int secuenciales y límites conocidos altos / bajos funcionaría (que es aproximadamente como funcionan las matrices de JavaScript).

De hecho, la lista de doble enlace (LinkedList en C #) es la estructura de datos de elección cuando solo se necesitan iteraciones hacia adelante y hacia atrás ... pero convirtiendo matriz / lista (que ya le da O (1) forma de representar el reverso iteración) no vale la pena. Dependiendo de otros requisitos, cambiar completamente a la lista vinculada puede ser una opción.

Tenga en cuenta que, desde el punto de vista teórico, si necesita iterar a través de todos los elementos de todos modos, gastar O (n) en reversa no cambia la complejidad general.

6
Alexei Levenkov 25 oct. 2019 a las 01:09