Lista Enlazada 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:

 

 

 

 

 

 

Listas enlazadas Simples

 

 Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace. 

Una variable de referencia contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con el nodo siguiente, y el enlace del último nodo contiene null para indicar el final de la lista. Aunque normalmente a la variable de referencia se la suele llamar top, usted puede elegir el nombre que quiera. 

 

La siguiente figura presenta una lista de enlace simple de tres nodos, donde top referencia al nodo A, A conecta con B y B conecta con C y C es el nodo final:

 

Un algoritmo común de las listas de enlace simple es la inserción de nodos. 

Este algoritmo está implicado de alguna forma porque tiene mucho que ver con cuatro casos:

• Cuando el nodo se debe insertar antes del primer nodo.
• Cuando el nodo se debe insertar después del último nodo.
• Cuando el nodo se debe insertar entre dos nodos.
• Cuando la lista de enlace simple no existe.

Listas Enlazadas

La lista enlazada que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener.

En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.
Las operaciones que podemos realizar sobre una lista enlazada son las siguientes:

Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista. Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.

Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. 

 

 

Para esta operación se pueden considerar tres casos:

• Insertar un nodo al inicio.
• Insertar un nodo antes o después de cierto nodo.
• Insertar un nodo al final.

Borrado: La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:

• Eliminar el primer nodo.
• Eliminar el último nodo.
• Eliminar un nodo con cierta información.
• Eliminar el nodo anterior o posterior al nodo cierta con información.

Búsqueda: Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar

Colas

Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir.


El ejemplo cotidiano es una cola para comprar, por ejemplo, las entradas del cine. Los nuevos compradores sólo pueden colocarse al final de la cola, y sólo el primero de la cola puede comprar la entrada

ALGORITMO PARA INSERTAR

                         Si A=máximo 

                         entonces mensaje (overflow) 

                         en caso contrario 

                         cola[A]<-- va 

                         A<-- A+1 

                         lor

ALGORITMO PARA EXTRAER

                          Si A&ltF 

                          entonces mensaje (underflow) 

                          en caso contrario 

                          x <-- cola[ 

                          F <-- F+1 

                          F] 

Aplicaciones de las colas

Las operaciones principales en una cola son la de insercion y extraccion de datos, llamadas encolar (enqueue) y desencolar (dequeue).

• Las colas se utilizan en muchos algoritmos y en situaciones en las que el rendimiento de dos sistemas que se cruzan datos entre sí es más eficiente cuando no se intercambian indicativos y señales de control (handshaking) en cada transferencia.

• También almacenan temporalmente la transferencia de información, lo que permite procesarla en origen y en destino a tasas independientes.

• La cola de eventos en Java es un buen ejemplo.

• Tipos derivados: colas de prioridad y flujos de datos

Pilas

Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista. 

Estas operaciones se conocen como "push" y "pop", respectivamente "empujar" y "tirar". Además, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Estas características implican un comportamiento de lista LIFO (Last In First Out), el último en entrar es el primero en salir.

El ejemplo del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo pueden tomarse del mismo extremo.
El nodo típico para construir pilas es:

struct nodo {
int dato;
struct nodo *siguiente;
};

Los tipos que definiremos normalmente para manejar pilas serán casi los mismos que para manejar listas, tan sólo cambiaremos algunos nombres: 

                         

typedef struct _nodo {
int dato;
struct _nodo *siguiente;}
tipoNodo; typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;

tipoNodo es el tipo para declarar nodos, evidentemente.
· pNodo es el tipo para declarar punteros a un nodo.
· Pila es el tipo para declarar pilas.

Tipos abstractos de datos (II)

 Por ejemplo, se puede definir el tipo de datos Cuadradoy las operaciones Área(c)y Perímetro(c)que devolverían el valor del área y del perímetro del cuadrado c.

El cuadrado se puede implementar de distintas formas: 

●   Con la posición de los cuatro vértices en las coordenadas de un plano.

                    registro=punto

                 real: x,y 

             fin_registro 

             registro=cuadrado 

                  punto: infIzq, infDer, supIzq, supDer 

             fin_registro

●   Con la posición de un punto y el tamaño del lado. 

             registro=cuadrado 

                 punto:origen 

                 real: lado 

             fin_registro

Estructuras lineales de datos: listas, pilas, colas

Tipos abstractos de datos

 

Procedimientos y funciones generalizan el concepto de operador. 

 ●   El programador puede definir sus propios operadores y aplicarlos sobre operandosde tipos no definidos en el lenguaje.
En un algoritmo en lugar de utilizar sólo los operadores que utiliza el lenguaje, mediante procedimientos y funciones se pueden aplicar sus propios operandos a tipos de datos no definidos por el lenguaje. 

        o    Por ejemplo, se puede ampliar el operador de multiplicación para multiplicar matrices.

 Tipo Abstracto de Datos (TAD)

●   Amplía el concepto de procedimiento a la definición de datos. 

●   Modelo matemático del dato junto con las operaciones que se pueden definir sobre él. 

●   Utilizan también generalización y encapsulamiento.
      o    Son generalizaciones de los tipos de datos primitivos.      
      o    Facilitan la localización de la definición del tipo y de las operaciones para su manejo.