¿Son necesarias las listas enlazadas en Python?

[Koan]

Me surgen algunas dudas con esta estructura de datos. Con el fin de poder comprender los árboles binarios, me salte las listas enlazadas. Osea, que no creo pueda entender el concepto de árbol de decisión y binario, si antes no comprendo la lista enlazada.

Por lo que he leído, veo que en otros lenguajes son muy importantes. Ya que los vectores, a no ser de dimensionado dinámico, las listas enlazadas son una solución.

Pero sabemos en Python, que el objeto lista, no hace falta dimensionar. Ya que se pueden insertar, borrar y eliminar datos de forma dinámica. O por decirlo de otra manera, de forma muy fácil.

Tomando un primer contacto con listas enlazadas en Python, la utilidad que suelen atribuirles, se puede conseguir con el manejo del objeto list.

Pero por otro lado, no sé si con el objeto list (sin usar listas enlazadas) se podría crear un árbol de decisión o binario. Aunque para árboles, creo, deberían ser listas doblemente enlazadas.

¿Cuando es útil usar listas enlazadas y porque?

[AlvaroG]

En general, toda vez que un lenguaje te ofrece un tipo de objeto "array" que puede dimensionarse de forma automática, y contener datos de diferentes tipos, no se trata de un array (vector) verdadero sino de un tipo de lista.
Los arrays de Javascript, las listas de Python, o los ArrayList de Java son en realidad listas enlazadas. Con lo cual, en estos lenguajes no tiene sentido implementar una lista enlazada, porque ya están incluidas en el lenguaje.

Si es nada más por seguir un ejercicio, la implementación de una clase Lista en python que simule una lista enlazada no es difícil, pero solamente será válido como ejercicio, no en el "mundo real".

Recuerda que lo único que necesitas para implementar una lista es una estructura como esta:

Código Python:

class Nodo:
    contenido = [valor]
    siguiente = [objeto de tipo Nodo]
 
class Lista:
    primer_elemento = [objeto de tipo Nodo]
 
    # funciones de lista
    # ....
 

Que es perfectamente posible y válida en Python, aunque innecesaria. De la misma manera podrías implementar un árbol de cualquier tipo.


Saludos.

[Koan]

Muchas gracias por la respuesta, AlvaroG. Precisamente ahí radicaba la duda que tenía. Los que estudiamos de forma autodidacta, nos hacemos nuestro propio plan de estudios. Y claro, a veces, de forma erronea saltamos de un tema/concepto a otro.

Yo precisamente quería estudiar el tema de los árboles binarios y decisión. Y en los libros o manuales que tengo, antes de los árboles, explican las listas enlazadas. Pero claro, yo me estaba dando cuenta que era un simple objeto list que ya lleva incluido Python.

La verdad, creo que lo hacen expresamente (con estos ejercicios) para entrenar de alguna forma a pensar algoritmicamente.

En todo caso ¿Los árboles ya no se pueden hacer con listas, no?

[AlvaroG]

Pues se pueden hacer de la misma manera. Por ejemplo, para un árbol binario simplemente cambias tu clase Nodo a algo como

Código Python:

class Nodo:
    contenido = [objeto]
    izquierda = [objeto de tipo Nodo]
    derecha = [objeto de tipo Nodo]
 

[Koan]

Esta bien saberlo. Pues no sé por que esta estructura nunca se explica así. Al menos, se actualizaría un poco el tema de los árboles.

[AlvaroG]

Pues no conozco otra manera de crear un árbol binario (aunque no es el único tipo de árbol que existe)

[razpeitia]

Iniciado por AlvaroG

Pues no conozco otra manera de crear un árbol binario (aunque no es el único tipo de árbol que existe)

Yo si conozco otra manera y son con puros arreglos. De hecho hay una librería en python que te hace este tipo de árbol binario. https://docs.python.org/2/library/heapq.html

[AlvaroG]

Es que lo que quería decir no era "no conozco otra manera de crear un árbol binario en python" sino que la definición básica de un árbol binario es un nodo con dos punteros a sus nodos hijos. :)

[razpeitia]

Iniciado por AlvaroG

Es que lo que quería decir no era "no conozco otra manera de crear un árbol binario en python" sino que la definición básica de un árbol binario es un nodo con dos punteros a sus nodos hijos. :)

Si haces un heap con un array, realmente no apuntas directamente a los hijos si no que hay formulas que te definen como si te encuentras en cierto indice del arreglo obtener el padre o los hijos.

http://en.wikipedia.org/wiki/Binary_...implementation

[AlvaroG]

En el mensaje anterior no entendí lo que habías querido decir, lo entiendo ahora.
Tampoco conocía esta implementación de un heap, ciertamente mi formación en lo que respecta a estructuras de datos se reduce a dos semestres en la universidad, jeje.

Igual sigo insistiendo en la palabra básica de lo que escribí antes