← Volver a los ejercicios

construir: Nil, :: y las tres operaciones básicas

Toda lista se arma con dos piezas: Nil, que es la lista vacía, y ::, que pone un elemento al frente de una lista que ya existe. Las cuatro primeras líneas construyen List(1, 2, 3), y el orden en que lo hacen no es el de la lista: el 3 entra cuando todavía no hay nada detrás de él y el 1 entra de último. Las cinco últimas descomponen la lista de frutas con head, tail e isEmpty. Avance paso por paso y mire los dos valores que cambian: la lista que queda y el elemento que la operación toma.

1. Las dos piezas y los tres selectores

paso 0 de 0
nodos en la cadena: 0
■ nodo que :: acaba de agregar ■ nodo que head devuelve ■ líneas de los selectores

El dibujo es la lista del chip lista: una cadena de nodos donde cada uno guarda su elemento y apunta al siguiente, y el último apunta a Nil. Los rótulos head y tail.head marcan los dos primeros nodos. El contador de la derecha de cada línea dice cuántas veces se evaluó.

2. Lo que se lleva de aquí

:: no modifica la lista que recibe: crea un nodo nuevo cuyo puntero apunta a la lista anterior. Por eso paso2 sigue valiendo List(3) después de que paso3 y paso4 se construyan, y por eso la construcción avanza de derecha a izquierda. El 3 necesita que Nil exista antes; el 1 necesita que exista List(2, 3). Esa dependencia es la misma que hace que :: se asocie a la derecha: 1 :: 2 :: 3 :: Nil se lee como 1 :: (2 :: (3 :: Nil)).

head y tail son las dos mitades de un nodo: el primero devuelve el elemento que el nodo guarda, el segundo devuelve a dónde apunta. Ninguno recorre la cadena, así que cuestan lo mismo con tres elementos que con tres mil. Encadenarlos sí recorre: frutas.tail.head son dos operaciones, y el contador de esa línea llega a × 2.

head y tail sobre la lista vacía lanzan una excepción, porque no hay nodo del que sacar nada: NoSuchElementException y UnsupportedOperationException. De ahí que isEmpty se consulte antes de bajar por la cadena, o que el descenso se escriba con match, que distingue las dos formas de la lista sin preguntar.