Aplicaciones De Las Listas Y Ejemplos

uè es una lista?Una lista enlazada es un conjunto de elementos

llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo,donde el orden de los mismos seestablece mediante punteros.

La idea básica es que cada componente de la listaincluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista. El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista.

El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.

Listas Enlazadas frente a Arrays

Las listas enlazadas tienen las siguiente ventajas sobre los arrays:

• No requieren memoria extra para soportar la expansión. Por el contrario, los arrays requieren memoria extra si se necesita expandirlo (una vez que todos los elementos tienen datos no se pueden añadir datos nuevos a un array).

• Ofrecen una inserción/borrado de elementos más rápida que sus operaciones equivalentes en los arrays. Sólo se tienen que actualizar los enlaces después de identificar la posición de inserción/borrado. Desde la perspectiva de los arrays, la inserción de datos requiere el movimiento de todos los otros datos del array para crear un elemento vacío. De forma similar, el borrado de un dato existente requiere el movimiento de todos los otros datos para eliminar el elementovacío.

En contraste, los arrays ofrecen las siguiente ventajas sobre las listas enlazadas:

• Los elementos de los arrays ocupan menos memoria que los nodos porque no requieren campos de enlace.

• Los arrays ofrecen un aceso más rápido a los datos, medante índices basados en enteros.

Las listas enlazadas son más apropiadas cuando se trabaja con datos dinámicos. En otras palabras, inserciones y borrados con frecuencia. Por el contrario, los arrays son más apropiados cuando los datos son estáticos (las inserciones y borrados son raras). De todas formas, no olvide que si se queda sin espacio cuando añade ítems a un array, debe crear un array más grande, copiar los datos del array original el nuevo array mayor y elimiar el original. Esto cuesta tiempo, lo que afecta especialmente al rendimiento si se hace repetidamente.

Mezclando una lista de enlace simple con un array uni-dimensional para acceder a los nodos mediante los índices del array no se consigue nada. Gastará más memoria, porque necesitará los elementos del array más los nodos, y tiempo, porque necesitará mover los ítems del array siempre que inserte o borre un nodo. Sin embargo, si es posible integrar el array con una lista enlazada para crear una estructura de datos úti.

Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas y Listas Enlazadas Circulares.

Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C, C++ o Java disponen de referencias para crear listas enlazadas.

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:

o Insertar un nodo al inicio.

o Insertar un nodo antes o después de cierto nodo.

o 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:

o Eliminar el primer nodo.

o Eliminar el último nodo.

o Eliminar un nodo con cierta información.

o 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.

Figura 1. Esquema de un nodo y una lista enlazada.

LISTA ENLAZADA SIMPLE

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

He aquì tenemos un ejemplo de una lista enlazada simple

//DECLARACIÒN DE PROTOTIPOS

#include<alloc.h>

#include<stdlib.h>

#include<conio.h>

#include<iostream.h>

//Declaramosla estructura

typedef struct nodo

{

int dato;

struct nodo * siguiente;

}tipoNodo;

//reservamos el espacio de memoria

tipoNodo *nuevo_elemento();

//Operaciones que vamos a arealizar

void crear();

void insertar();

void insertar_inicio();

void insertar_ordenado();

void insertar_final();

void presentar();

void modificar();

void buscar();

void ordenar();

void ordenar_ascendente();

void ordenar_descendente();

void eliminar();

void eliminar_cabeza();

//FUNCION PARA EL CUADRO

void cuadro(int x1,int y1, int x2, int y2, char simb);

//NUESTRA CABEZA

tipoNodo *cab;

tipoNodo *nuevo_elemento()

{

tipoNodo *nodo1;

nodo1=(tipoNodo *)malloc(sizeof(tipoNodo ));

if(!nodo1)

cout<<”No se ha reservado memoria para el nuevo “;

return nodo1;

}

void main()

{

clrscr();

crear();

clrscr();

char opc=’ ‘;

do

{

clrscr();

cuadro(1,10,35,56,’²’);

gotoxy(13,3);cout<<”->[ LISTAS ENLAZADAS ]<-\n”;

gotoxy(12,6);cout<<” MENU PRINCIPAL\n”;

gotoxy(12,9); cout<<” [1]: INSERTAR\n”;

gotoxy(12,12);cout<<” [2]: MODIFICAR\n”;

gotoxy(12,15);cout<<” [3]: BUSCAR\n”;

gotoxy(12,17);cout<<” [4]: ORDENAR\n”;

gotoxy(12,19);cout<<” [5]: ELIMINAR\n”;

gotoxy(12,21);cout<<” [6]: PRESENTAR\n”;

gotoxy(12,24);cout<<”

...