• Author / Uploaded
• Jaime Radich Vasquez

• Categories
• Gestión de tecnologías de la información
• Gestión de datos
• Datos
• Programación de computadoras
• Datos informáticos

Citation preview

ESTRUCTURA DE DATOS LISTAS DOBLEMENTE ENLAZADAS JAIME RADICH VASQUÉZ IACC 13/05/2018

1) Suponga que Ud. es un programador y le han solicitado que organice una base de datos de los estudiantes de una red de colegios pertenecientes a una congregación, para que sea manejada por el área administrativa. De acuerdo a sus conocimientos informáticos, concluye que lo mejor es trabajar los datos con listas doblemente enlazadas. Argumente adecuadamente su decisión tomando en cuenta las ventajas de usar este sistema de estructura de datos. Las estructuras de datos son colecciones de datos organizados y entre los cuales se pueden realizar ciertas operaciones como:  Agregar un nuevo valor a la estructura.  Borrar un valor de la estructura.  Buscar un valor dentro de la estructura.  Ordenar los valores.

La razón principal para utilizar listas doblemente enlazadas es que: Mover grandes cantidades de datos consume mucho tiempo, como lo seria en una red de colegios, al promover de grado o curso a todos los estudiantes a final de año y ademas ingresar nuevos alumnos y eliminar de los registros a los que ya no seguirán en los colegios. Se establece entonces un orden lógico de los datos, que es independiente al orden físico en memoria de los datos. El orden lógico se crea a través de las listas doblemente enlazadas, donde cada nodo tiene un puntero hacia sus dos nodos vecinos. Los nuevos nodos se agregan entre dos nodos existentes, que actualizan su puntero haciendo referencia al nuevo nodo. La ubicación física de los nuevos nodos no importa, ya que la lista doblemente enlazada mantiene el orden lógico. Cada nodo, entonces hace referencia al anterior y al siguiente nodo, de este modo la base de datos podrá leer el indice hacia adelante o hacia atrás según sea necesario. También sera posible insertar o borrar un nodo sin mover grandes cantidades de datos, solo se actualizan los punteros.

2) La siguiente lista doblemente enlazada tiene cinco nodos:

[1][2][3][4][5]

a) Si tuviera que insertar dos nodos uno entre los nodos 1 y 2 y el otro entre los nodos 3 y 4 ¿cómo quedaría configurada la nueva lista doblemente enlazada?

Insertar un elemento a continuación de un nodo cualquiera de una lista: Genéricamente hablando (como se insertan 2 nodos nuevos el procedimiento se realiza dos veces) : 1. Nodo ^.siguiente apunte apunte 2. Lista ^.siguiente apunte a nodo. 3. Nodo ^.anterior apunte a lista. 4. Nodo ^.siguiente ^.anterior apunte a nodo. Como se muestra en la siguiente imagen:

La posición donde se guardan los nodos es de orden lógico no son espacios de memoria contiguas; [1][2][3][4][5][6][7]

b) Y de la lista doblemente enlazada recién re-configurada, que ahora cuenta con siete nodos, tuviera que borrar el nodo 2 ¿cómo quedaría configurada la nueva lista doblemente enlazada?

Eliminar un nodo intermedio genéricamente hablando: 1. Si nodo apunta a lista, se hará que lista apunte a lista ^.anterior (o lista ^.siguiente). 2. Nodo ^.anterior ^.siguiente apunte a nodo ^.siguiente. 3. Nodo ^.siguiente ^.anterior apunte a nodo ^.anterior. 4. Borrar el nodo apuntado por nodo

Como se muestra a continuación:

Borrado de nodo general

Nuevamente las posiciones son de orden lógico es decir no son posiciones contiguas en el disco. [1] [2][3][4][5][6]

BIBLIOGRAFIA IACC (2018) www.google.cl/search?q=imagenes file:///C:/Users/Jaime/Downloads/4%20Estructuras%20Enlazadas%20(9).pdf