UNIDAD III: LISTAS ENLAZADAS

3.1 LISTAS ENLAZADAS SIMPLES

Definicion:

Recorrido simplemente despliega los datos almacenados en el arreglo Info, con ayuda de un segundo arreglo llamado Indice el cual guarda el orden en el que encuentran enlazados cada uno de los datos.

Explicacion:

Apuntador toma el valor de Inicio, despu¨¦s ve si la condici¨®n cumple para efectuar un Ciclo mientras Apuntador sea diferente de 0, si cumple lo que hace es que despliega la Info[Apuntador], despu¨¦s Apuntador toma el valor de Indice[Apuntador] (El cual nos indica el siguiente nodo que sigue en la lista) y hace esto hasta que Apuntador sea igual a 0 (Cuando llega a este punto a llegado al fin de la Lista Enlazada).

3.1.2 LISTAS ENLAZADAS DOBLES

Una lista doble , ó doblemente ligada es una colección de nodos en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (li) y otro a su sucesor(ld). 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.

La estructura de un nodo en una lista doble es la siguiente:

Existen dos tipos de listas doblemente ligadas:

• Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo del primer nodo como el derecho del último nodo apuntan a NIL.
• Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al último nodo de la lista, y el puntero derecho del último nodo apunta al primer nodo de la lista.

Debido a que las listas dobles circulares son más eficientes, los algoritmos que en esta sección se traten serán sobre listas dobles circulares.

En la figura siguiente se muestra un ejemplo de una lista doblemente ligada lineal que almacena números:

En la figura siguiente se muestra un ejemplo de una lista doblemente ligada circular que almacena números:

A continuación mostraremos algunos algoritmos sobre listas enlazadas. Como ya se mencionó, llamaremos li al puntero izquierdo y ld al puntero derecho, también usaremos el apuntador top para hacer referencia al primer nodo en la lista, y p para referenciar al nodo presente.

3.1.3 LISTAS ENLAZADAS CIRCULARES

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer un lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Una lista enlazada circular que contiene tres valores enteros

3.1.4 LISTAS ENLAZADAS MULTILISTAS

• Conjunto de nodos en que algunos tienen más de un puntero y pueden estar en más de una lista simultáneamente.
• Para cada tipo de nodo es importante distinguir los distintos campos puntero para realizar los recorridos adecuados y evitar confusiones.
• Estructura básica para Sistemas de Bases de Datos en Red.
• Dados dos tipos de entidades, TipoA y TipoB , se necesitan:

Dos nuevos tipos correspondientes a los nodos para cada clase de entidad, que junto con la información propia de la entidad incluye los punteros necesarios para mantener la estructura.

• typedef struct NodoTipoA {

• TipoA Info;

• NodoRelacion *PrimerB;

• } NodoTipoA;

•

• typedef struct NodoTipoB{

• TipoB Info;

• NodoRelacion *PrimerA;

• } NodoTipoB;

Una estructura para agrupar los objetos de cada tipo de entidad (Array, Lista,Árbol, Tabla Hash, ...).

Un TDA Nodo Relacion que incluye un puntero por cada lista así como información propia de la relación.

• typedef struct NodoRelacion {

• NodoTipoA *SiguienteA;

• NodoTipoB *SiguienteB;

• campo1;

• ........

• campo_n;

• } NodoRelacion;

Un nodo Multilista que engloba los distintos tipos de nodos (entidad A, entidad B y relación). El tipo de dato para construir esto es el registro variante:

typedef enum {NODO_A, NODO_B, NODO_ML} TipoNodo;

• typedef struct NodoMultilista {

• TipoNodo tipo;

• union {

• NodoTipoA a;

• NodoTipoB b;

• NodoRelacion nr;

• } cont;

• } NodoMultilista;

3.1.5 CLASES PARA IMPLEMENTACION DE LISTAS

• Para comenzar partiremos con una implementacion basica de una lista, la cual

  ocuparemos para realizar los ejercicios en la clase practica. Como reforzamiento

  a lo que se vio en la ayudantia, los metodos basicos que deben de tener estas

  implementaciones son:

  • Insert ( x, p ), insert el elemento x en la posicion p

  • end (), va a la posicion final de datos.(No necesariamenta la del arreglo).

  1

  • Locate ( x ), retorna la posicion del elemento x.

  • Retrieve ( p ), retorna el elemento en la posicion p.

  • Delete ( p ) ,Delete ( x ),Borra la posicion p. Borra el o los elementos x.

  • Next () ,Next ( p ), Posicion siguiente o posicion siguiente a p. La posicion

  siguiente esta dada por el valor de la posicion actual .

  • MakeNull () , Hace la lista nula, necesario para comenzar nuevamente.

  • PrintList (), Muestra los valores de la lista.

  Adicionalmente pueden agregar los metodos que uds encuentren necesarios por

  ejemplo.

  Para el manejo del arreglo:

  • Mover ( p ), dejara vacia la posicion p para poder insertar un dato.

  • Redimencionar ( x ),Agrega una cantidad de datos x al arreglo.

  • Borrar ( p ),borra el dato en p y dezplaza todos los valores una posicion.

  Recuerden que basicamente estamos trabajando con 3 variables:

  • El arreglo.

  • Variable de posicion Actual.

  • Variable de posicion Final.

  Recuerden que estas variables como su nombre lo dice, con la ejecucion del

  Codigo iran cambiando. Las 2 ultimas noson necesarias, pero pueden hacer el

  funcionamiento de la Lista mucho mas rapido, y servira para futuras implementacion

  que usaremos.