Este documento describe las operaciones de listas doblemente enlazadas. Explica que un inspector de tren está buscando un pasajero en un vagón, lo que requiere recorrer la lista representando los asientos del vagón en ambas direcciones. También incluye ejemplos de cómo insertar un nodo en una lista doblemente enlazada y una tabla comparando listas simplemente enlazadas y doblemente enlazadas.
100%(3)100% encontró este documento útil (3 votos)
499 vistas10 páginas
Este documento describe las operaciones de listas doblemente enlazadas. Explica que un inspector de tren está buscando un pasajero en un vagón, lo que requiere recorrer la lista representando los asientos del vagón en ambas direcciones. También incluye ejemplos de cómo insertar un nodo en una lista doblemente enlazada y una tabla comparando listas simplemente enlazadas y doblemente enlazadas.
Este documento describe las operaciones de listas doblemente enlazadas. Explica que un inspector de tren está buscando un pasajero en un vagón, lo que requiere recorrer la lista representando los asientos del vagón en ambas direcciones. También incluye ejemplos de cómo insertar un nodo en una lista doblemente enlazada y una tabla comparando listas simplemente enlazadas y doblemente enlazadas.
Este documento describe las operaciones de listas doblemente enlazadas. Explica que un inspector de tren está buscando un pasajero en un vagón, lo que requiere recorrer la lista representando los asientos del vagón en ambas direcciones. También incluye ejemplos de cómo insertar un nodo en una lista doblemente enlazada y una tabla comparando listas simplemente enlazadas y doblemente enlazadas.
Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
Descargar como docx, pdf o txt
Está en la página 1/ 10
“Listas doblemente enlazadas”
Rodrigo Andrés Guzmán Farías
Estructura de datos
Instituto IACC
16/12/2019 Desarrollo
1. Un inspector de un tren está indagando si el pasajero del asiento 23a está en el vagón de la imagen, para validar el proceso el inspector deberá consultar el ticket del pasajero. Indique qué operación de listas doblemente enlazadas está realizando el inspector. Explique con sus palabras y aplicando los conceptos tratados en los contenidos, la forma en la cual se desarrolla esta operación.
R: De acuerdo al material proporcionado por IACC y la indagación que he realizado respecto al
contenido de esta semana puedo argumentar lo siguiente:
En este caso planteado la operación de listas doblemente enlazadas que se está realizando, corresponde a “búsqueda”. Para explicar mejor esta pregunta, debemos entender que el vagón de la imagen corresponde a la estructura de datos del tipo “lista doblemente enlazada” (el cual pertenece también, a una estructura mayor que es el tren), debido a esto es posible realizar el recorrido del inspector en ambos sentidos a través de este vagón.
La operación de búsqueda, es aquella que consiste en realizar el recorrido a través de toda la
estructura (vagón) con el fin de localizar un nodo (elemento) especifico dentro de la lista doblemente enlazada y hacer la consulta respecto a su información. El recorrido a través del vagón será posible realizarlo en ambas direcciones y debido al orden lógico de los nodos (elementos, en este caso los asientos de este vagón) no siempre será necesario realizar el recorrido completo de la estructura para poder ubicar el nodo requerido.
Para realizar esta operación lo haremos de un modo similar al utilizado en las listas simples, solo que esta vez no necesitaremos de un puntero auxiliar, eso sí, debemos tener en cuenta que la lista no tendrá por que estar en uno de los extremos. Para que el inspector pueda realizar la “búsqueda o recorrido” en la lista denomina vagón y así poder encontrar el nodo correspondiente al pasajero del asiento 23ª, el proceso sería el siguiente:
- Retroceder hasta el comienzo de la lista, y asignar a la lista el valor de lista ->anterior
mientras lista->anterior no sea NULL. - Debemos abrir un bucle que al menos tenga una condición, que el índice no corresponda a NULL. - En el interior del bucle asignaremos a lista el valor del nodo siguiente al actual.
Se entiende entonces que dentro de la lista “vagón A” existe cierta cantidad de nodos, los cuales serían los asientos de este carro. Pondremos como ejemplo que la capacidad de asientos será de 30 pasajeros (índice de 0 a 29 en la lista) el inspector con el fin de constatar si el pasajero del asiento 23A se encuentra a bordo, iniciará el recorrido (bucle) el cual puede ser de “inicio a fin” o de “fin a inicio”, pasando de un nodo al siguiente o anterior nodo (según sea la dirección) hasta encontrar el deseado.
* Si deseamos visualizar todos los valores de los nodos de la lista, podemos usar este bucle en C. 2. Realice una tabla comparativa entre listas enlazadas y listas doblemente enlazadas, considerando 2 diferencias y/o similitudes en cada caso. R: Lista enlazada simple Lista doblemente enlazada -Es una lista enlazada de tipo básico, la cual -Corresponde a una estructura de datos, la posee un solo enlace por nodo. cual consiste en un conjunto de nodos enlazados secuencialmente. -El enlace apunta al nodo siguiente dentro de -Cada uno de los nodos posee dos campos la lista, o al valor NULL o a la lista vacía si es denominados enlaces, los cuales son el último nodo. referencias al nodo siguiente y al anterior en la secuencia de nodos. -Los nodos de este tipo de listas no utilizan -Requieren más espacio debido a sus demasiado espacio debido a su estructura operaciones. simple. -El recorrido de la lista simple será iniciado -Esta lista puede ser recorrida en cualquier desde el primer nodo. dirección debido al doble enlace de los nodos. -Necesita la dirección del nodo anterior para -Permite insertar o borrar un nodo en un realizar acciones como insertar o suprimir. número de operaciones fijo, otorgando solamente la dirección de dicho nodo. -Son menos costosas, aunque presentan un -Son más costosas, por lo que dan una mayor mayor grado de dificultad porque no permiten facilidad en la manipulación, permiten el el acceso en ambas direcciones. acceso secuencial en ambas direcciones a la lista.
-Lista enlazada simple: corresponde a una estructura de tipo lineal donde los elementos tienen una relación de 1 a 1. Una lista con nodo de cabecera es aquella en la que el primer nodo de la lista contendrá en su campo algún valor que lo diferencie de los demás nodos: *,-,+, etc.
-Lista doblemente enlazada: Una lista doble o doblemente enlazada es una colección de nodos en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su antecesor y otro a su sucesor. Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero. - Similitudes:
1- Ambas son estructuras de dinámicas de tipo lineal y la asignación de memoria se realizará al
momento de su ejecución.
2.- Las operaciones que se pueden efectuar sobre ambas estructuras, básicamente son las mismas (insertar, borrar, recorrer, buscar).
- Diferencias:
1- A diferencia de las listas simples, la doblemente enlazada no necesita un nodo de carácter
especial para acceder a ella, es posible su recorrido en ambos sentidos desde cualquier nodo.
2.- El desplazamiento a través de este tipo de listas resulta más sencillo en la ejecución de las distintas operaciones, ya que esta permite el recorrido de la estructura desde “inicio a fin” y de “fin a inicio”.
3. Usando la siguiente imagen ejemplifique cómo se realiza operación de inserción de un
nodo 20 entre el nodo 12 y el nodo 57. Explique paso a paso cómo se realiza el proceso. En esta imagen es posible identificar una lista doblemente enlazada que contiene 3 nodos (12, 57 y 95), se requiere insertar el nodo 20 y se nos pide hacerlo entre el nodo 12 y el 57. Por lo tanto, después de haber creado el nodo 20 procederemos a insertarlo en la estructura mayor, ya que debemos verificar que la lista donde haremos esta operación no se encuentre vacía, insertamos entonces el nodo 20 a continuación del nodo 12 y antes del nodo 57, el proceso sería el siguiente: 1- Hacer que nodo->siguiente apunte a lista-> siguiente. 2- Hacer que Lista->siguiente apunte a nodo. 3- Hacer que nodo->anterior apunte a lista. 4- Hacer que nodo->siguiente->anterior apunte a nodo.
Para explicar esta operación, podríamos decir que hemos trabajado sobre dos listas enlazadas, donde los dos primeros pasos realizados equivalen a lo que realizábamos para insertar elementos en una lista simple. Los siguientes pasos realizaran lo mismo con la lista que enlaza los nodos en sentido opuesto. El cuarto paso es le más complejo de entender y se podría explicar de la siguiente forma: Podemos suponer que disponemos de un puntero auxiliar, “p” y antes de insertar el nodo, tendremos que hacer que apunte al nodo que quedará a continuación después de insertado el nodo, esto quiere decir que p= Lista->siguiente. En resumen, en el proceso de inserción serán ejecutados los pasos 1,2 y 3. El 4to solo corresponderá hacer que p->anterior apunte a nodo. Pero nodo->siguiente ya apunta a p, así que en realidad no necesitamos el puntero auxiliar, bastará con hacer que nodo->siguiente->anterior apunte a nodo. Bibliografía
