Es fácil implementar la lista vinculada en C++ donde tiene punteros. Pero ¿cómo se implementan en otros idiomas (como java, python, etc.)? No quiero usar la clase incorporada (que son compatibles con JAVA) para la lista enlazada, pero lo que quiero es ¿cómo reemplazar los punteros para crear una lista enlazada?¿Cómo se implementan las listas de enlaces sin el uso de puntero?
Se implementan utilizando referencias que son esencialmente punteros (excluyendo la sintaxis) con los que no se puede hacer la aritmética del puntero (en algunos idiomas tampoco pueden ser nulos). En muchos idiomas, las referencias son la forma predeterminada de usar variables, a diferencia de C++, donde el valor predeterminado es por valor.
+1 Me encanta esa explicación para las referencias. Es tan rápido, fácil y preciso, además de ser obvio para los veteranos de C y dar a los demás una razón para aprender ese aspecto de la programación. – delnan
Con otros idiomas, se ocupan de las referencias que están estrechamente relacionadas con los punteros.
Cuando usted escribe su propia clase, por ejemplo class node, y que cada node presionado un campo al siguiente node, en realidad se mantiene una referencia al siguiente nodo (o nula si se trata de la última)
En lugar de punteros que apuntan a un bloque de memoria, se usan referencias, como se dijo anteriormente. Así que, como usted tendría en C++
Struct Node {
Node *last;
Node *next;
}
que se vería así:
Struct Node {
Node last;
Node next;
}
La última oración es desafortunada. Si lo tomamos como valor nominal, es decir, "' Node' es un tipo de valor ", implica que su segunda definición de' Node' no es válida porque está en tamaño infinito. Las referencias no son direcciones, de hecho, pero * son * indirectas. – delnan
Acabo de notar que su segundo ejemplo no es válido incluso ignorando la explicación ahora eliminada. (Si se supone que es C++). – delnan
Se suponía que era una visualización en pseudocódigo. The Struct acaba de salir de su pasado en C++ –
Una buena clase de estructuras de datos le mostrará que una lista enlazada se puede implementar en cualquier lenguaje utilizando matrices, tales como FORTRAN.
En lugar de utilizar punteros, utilizaría otros medios para localizar el siguiente enlace. Con las matrices, en lugar de un puntero usaría un índice para el próximo elemento.
Por lo tanto, podría implementar una lista vinculada en un archivo de acceso aleatorio utilizando la posición del archivo en lugar de los punteros.
No estoy seguro de si esto cuenta como lista vinculada. Definitivamente tiene características diferentes de la implementación basada en punteros, ya que es más limitada. Aparte de eso, esto no tiene nada que ver con el punto porque * puedes * construir listas enlazadas "regulares" (y todas las otras estructuras de datos que dependen indirectamente) con referencias. – delnan
Es una lista, y está vinculada. No utiliza punteros para vincular los nodos. Es una * implementación * diferente de una lista vinculada. Me enseñaron esto en mi clase de Data Structures en la Universidad. –
Puede encontrar una buena respuesta en este libro - http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 - Resumiré lo que recuerdo para usted.
Básicamente, tendrá dos matrices de igual tamaño (con suerte mayor que n donde n = número de elementos que desea almacenar). Los llamaremos Array A y Array B.
La matriz A [i] contiene el valor de los datos. La matriz B [i] tiene el 'siguiente' valor 'k' tal que A [i] -> siguiente = A [k].
Espero que esto ayude.
Ver mi comentario sobre la respuesta de Thomas Matthew. – delnan
Recuerde que el concepto de una lista vinculada es que puede obtener de un elemento a otro. Cómo lo haces puede ser muy diferente.
En C++, por ejemplo, usted mencionó que puede usar punteros. Lo que dijo de otra manera sería que usas la dirección de memoria de los objetos.
Pero eso es sólo una forma. Si se hizo referencia a todos sus objetos desde una matriz, entonces sería capaz de hacer referencia a un objeto por su índice en esa matriz. Por lo tanto, cada elemento de su lista vinculada tendrá un número entero que especifica el índice del objeto al que está conectado.
Para darle otro ejemplo. Si tuviera un diccionario donde asoció objetos con cadenas. Entonces podrías usar cadenas para hacer referencia entre sí.
El concepto central de las listas vinculadas no es punteros, sino que los elementos de la lista son responsables de realizar un seguimiento del elemento al que está conectado.
Lea esto y vea si satisface suficientemente su pregunta: http://stackoverflow.com/questions/7480783/pointers-in-java –
@asawyer No se pasa nada por referencia en Python y Java. Tampoco en muchos otros idiomas que usan referencias en el mismo sentido. – delnan
@asawyer: de acuerdo con delnan. Java es pasar por valor. Siempre. Ese valor puede ser una referencia, pero un valor es lo que se pasa. –