Foros del Web » Programando para Internet » Python »

¿Son necesarias las listas enlazadas en Python?

Estas en el tema de ¿Son necesarias las listas enlazadas en Python? en el foro de Python en Foros del Web. 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 ...
  #1 (permalink)  
Antiguo 24/01/2015, 07:32
 
Fecha de Ingreso: diciembre-2009
Ubicación: Spain
Mensajes: 180
Antigüedad: 14 años, 3 meses
Puntos: 9
¿Son necesarias las listas enlazadas en Python?

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?
  #2 (permalink)  
Antiguo 26/01/2015, 09:48
AlvaroG
Invitado
 
Mensajes: n/a
Puntos:
Respuesta: ¿Son necesarias las listas enlazadas en Python?

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:
Ver original
  1. class Nodo:
  2.     contenido = [valor]
  3.     siguiente = [objeto de tipo Nodo]
  4.  
  5. class Lista:
  6.     primer_elemento = [objeto de tipo Nodo]
  7.  
  8.     # funciones de lista
  9.     # ....

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


Saludos.
  #3 (permalink)  
Antiguo 26/01/2015, 12:41
 
Fecha de Ingreso: diciembre-2009
Ubicación: Spain
Mensajes: 180
Antigüedad: 14 años, 3 meses
Puntos: 9
Respuesta: ¿Son necesarias las listas enlazadas en Python?

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?
  #4 (permalink)  
Antiguo 27/01/2015, 06:23
AlvaroG
Invitado
 
Mensajes: n/a
Puntos:
Respuesta: ¿Son necesarias las listas enlazadas en Python?

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:
Ver original
  1. class Nodo:
  2.     contenido = [objeto]
  3.     izquierda = [objeto de tipo Nodo]
  4.     derecha = [objeto de tipo Nodo]
  #5 (permalink)  
Antiguo 27/01/2015, 13:33
 
Fecha de Ingreso: diciembre-2009
Ubicación: Spain
Mensajes: 180
Antigüedad: 14 años, 3 meses
Puntos: 9
Respuesta: ¿Son necesarias las listas enlazadas en Python?

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.
  #6 (permalink)  
Antiguo 28/01/2015, 06:58
AlvaroG
Invitado
 
Mensajes: n/a
Puntos:
Respuesta: ¿Son necesarias las listas enlazadas en Python?

Pues no conozco otra manera de crear un árbol binario (aunque no es el único tipo de árbol que existe)
  #7 (permalink)  
Antiguo 28/01/2015, 08:52
Avatar de razpeitia
Moderador
 
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 19 años
Puntos: 1360
Respuesta: ¿Son necesarias las listas enlazadas en Python?

Cita:
Iniciado por AlvaroG Ver Mensaje
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
  #8 (permalink)  
Antiguo 29/01/2015, 06:51
AlvaroG
Invitado
 
Mensajes: n/a
Puntos:
Respuesta: ¿Son necesarias las listas enlazadas en Python?

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. :)
  #9 (permalink)  
Antiguo 29/01/2015, 08:31
Avatar de razpeitia
Moderador
 
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 19 años
Puntos: 1360
Respuesta: ¿Son necesarias las listas enlazadas en Python?

Cita:
Iniciado por AlvaroG Ver Mensaje
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
  #10 (permalink)  
Antiguo 29/01/2015, 09:02
AlvaroG
Invitado
 
Mensajes: n/a
Puntos:
Respuesta: ¿Son necesarias las listas enlazadas en Python?

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

Etiquetas: enlazadas, gui, listas
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 19:18.