Listas enlazadas

¿Qué atributo pueden tener las clases Nodo / ListaEnlazada?

Mínimamente para construir una lista enlazada, se necesita:

• ListaEnlazada con atributo indicando al primer nodo.
• Nodo con un atributo que almacena el dato, y otro con una referencia al siguiente nodo.

Con esto podemos modelar una lista con cualquier cantidad de elementos (vacía, un elemento, N elementos) y de cualquier tipo de dato.

La implementación también podría incluir otros atributos, como por ejemplo:

• ListaEnlazada con un atributo indicando la cantidad de elementos que tiene.
• Nodo con una referencia al anterior elemento para que pueda iterarse en ambos sentidos (y armar una lista doblemente enlazada).
• ListaEnlazada con referencia al último elemento. Común en listas enlazadas doblemente enlazadas y en listas con métodos para insertar o borrar el último elemento.

Por supuesto todos los atributos con sus invariantes deben mantener su consistencia en cada uno de los métodos que modifiquen la lista enlazada.

¿Cuáles son los casos bordes típicos a considerar?

Va a depender del método que se busque implementar. Pensemos por ejemplo en el pop(i=None) que elimina el i-ésimo elemento de la lista, o el último en el caso i == None. ¿Qué casos deberíamos considerar? Nuestro método debería funcionar o al menos tomar una acción particular en todos los casos que se nos ocurran:

• Eliminar un elemento en el medio de la lista.
• Eliminar el primer elemento, y comprobar que se actualice correctamente la referencia al primer elemento de la lista.
• Eliminar el último elemento, y comprobar que el método no tire error en el caso de apuntar una referencia a None.
• ¿Qué pasa si el índice i no está en rango? Podemos lanzar una excepción (ValueError) con un mensaje particular, documentando en el método sobre el caso particular.
• ¿Qué pasa si la lista está vacía? Esto es posible encararlo con las mismas condiciones que el caso "i fuera de rango"!

Recomendamos fuertemente leer la unidad 15 del apunte, que incluye implementaciones del pop, remove e insert, los cuales consideran todos los casos bordes.

¿Por qué muchos ejercicios no permiten el uso de append(), estructuras auxiliares, o recorrer la lista más de N veces?

Una llamada a append() itera la lista en su totalidad, y un método que realiza múltiples llamadas a append() resultaría en una solución de complejidad temporal cuadrática que no escala bien a listas de muchos elementos.

Sucede algo similar con el uso de estructuras auxiliares. Un método que utiliza estructuras auxiliares estaría copiando los elementos en la nueva estructura, siendo poco óptimo en memoria.

Con un uso apto de variables y referencias a nodos, el método podría tener soluciones que recorran la lista una única vez (o al menos una cantidad fija de veces) y que utilicen poca memoria.

Por supuesto va a depender del método a implementar, pero si el enunciado contiene estas restricciones se espera una solución que las cumpla.