No se trata solo de listas vinculadas, se trata específicamente de listas individualmente vinculadas. A diferencia de las matrices, tienen una definición inductiva simple y agradable:
Una lista es:
- La lista vacía
- O bien, una celda que contiene dos referencias: un elemento y otra lista.
Esto hace que trabajar con ellos de manera simbólica y de alto nivel sea muy fácil, ya que se asignan muy bien a todo tipo de definiciones recursivas; por ejemplo, una función que busca algún elemento es simplemente:
- ¿Cuáles son los beneficios de usar la recursividad de la cola? ¿Es siempre posible?
- ¿Los algoritmos de aprendizaje automático han salido del laboratorio y han pasado a entornos clínicos que involucran pacientes?
- Cómo comenzar con algoritmos en CS
- ¿Quién sabe qué hay detrás de la API de Google Nearby Search? ¿Qué algoritmo usan? ¿Cómo encuentra Google una estación de servicio cercana?
- ¿Por qué Java utiliza diferentes algoritmos de clasificación para diferentes tipos de datos?
- Si la lista que tenemos es la lista vacía, entonces es falsa.
- De lo contrario, es verdadero si el “espacio de valor” de la celda es el valor que estamos buscando, o el valor de self aplicado a la cola de la lista (el “espacio de descanso” de la celda, que es una lista completa) por sí mismo).
Puede pensar: “claro, puedo hacer esto casi tan fácilmente con una matriz y un bucle for “, pero la cuestión es que las escalas anteriores. Este fue solo un ejemplo muy simple; las ventajas se hacen cada vez más grandes cuando las definiciones se vuelven más complejas, con múltiples casos posibles y coincidencia de patrones y retroceso y no determinismo y demás.
Otro problema es que las matrices son mutables; por ejemplo, si mi programa Prolog estaba atravesando una matriz y sacando valores en cada paso de la recursión, y de repente ve que esta ruta no lleva a ninguna parte y decide retroceder, la matriz ha sido destruida. no puede simplemente “rebobinar el tiempo” a una llamada anterior (donde con las listas, siempre y cuando recuerde la referencia que se usó, puede usarlo nuevamente; no se ha cambiado nada al recorrer la lista). Para lograr un efecto similar con las matrices, necesitaría transportar parámetros de índice adicionales. Por lo tanto, no son solo una de las estructuras de datos más simples, sino que también son una de las estructuras de datos persistentes más simples.
Además, a pesar de ser tan simples (¿o quizás por eso?), Son muy versátiles: también se pueden usar para modelar árboles y gráficos, no solo listas planas.
