3.22. El tipo abstracto de datos Lista Ordenada

Ahora consideraremos un tipo de lista conocida como lista ordenada. Por ejemplo, si la lista de enteros mostrada arriba era una lista ordenada (orden ascendente), entonces podría escribirse como 17, 26, 31, 54, 77 y 93. Dado que 17 es el ítem más pequeño, ocupa la primera posición en la lista. Asimismo, puesto que 93 es el más grande, ocupa la última posición.

La estructura de una lista ordenada es una colección de ítems en los que cada uno contiene una posición relativa que se basa en alguna característica subyacente del ítem. El orden es típicamente ascendente o descendente y asumimos que los ítems de la lista tienen una operación de comparación significativa que ya está definida. Muchas de las operaciones de lista ordenada son las mismas que las de la lista no ordenada.

Next Section - 3.23. Implementación de una lista ordenada