Una lista enlazada es una de las estructuras
de datos fundamentales, y puede ser usada para implementar otras estructuras de
datos. Consiste en una secuencia de nodos, en los que se guardan campos de
datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior
o posterior. El principal beneficio de las listas enlazadas respecto a los
vectores convencionales es que el orden de los elementos enlazados puede ser
diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el
orden de recorrido de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de dato
autoreferenciado porque contienen un puntero o enlace a otro dato del mismo
tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en
cualquier punto de la lista en tiempo constante (suponiendo que dicho punto
está previamente identificado o localizado), pero no permiten un acceso
aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas
Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas
Enlazadas Doblemente Circulares.
Tipos
de Listas Enlazadas
Listas enlazadas
lineales:
Listas simples
enlazadas
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.
Lista Doblemente
Enlazada
Un tipo de lista enlazada más sofisticado es
la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos
enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer
nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el
último nodo.
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 una lista
enlazada circular podemos empezar por cualquier nodo y seguir la lista en
cualquier dirección hasta que se regrese hasta el nodo original. 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 ingerirdatos, y para
visitar todos los nodos de una lista a partir de uno dado.
Listas enlazadas
circulares simples
Cada nodo tiene un enlace, similar al de las listas
enlazadas simples, excepto que el siguiente nodo del último apunta al primero.
Como en una lista enlazada simple, los nuevos nodos pueden ser solo
eficientemente insertados después de uno que ya tengamos referenciado. Esto nos
permite rápidas inserciones al principio, y también permite accesos al primer
nodo desde el puntero del último nodo.
Lista Enlazada
Doblemente Circular
En una lista enlazada doblemente circular,
cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada,
excepto que el enlace anterior del primer nodo apunta al último y el enlace
siguiente del último nodo, apunta al primero. Como en una lista doblemente
enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier
punto con acceso a algún nodo cercano. Aunque estructuralmente una lista
circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso
externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola,
y así mantener el orden tan bien como en una lista doblemente enlazada.
#include <iostream>
#include <stdlib.h>
using namespace
std;
struct nodo{
int nro; //los datos seran de tipo entero
struct nodo *sgte; //puntero
};
typedef struct
nodo;//definimos a nodo como un tipo de variable
nodo *fin;//puntero
que ira siempre al final de la lista
nodo *lista;//puntero
que para nosotros apuntara a la cabeza de nuestra lista
void menu1();
//declaramos las funciones a usar
void
insertarInicio();
void
insertarFinal();
void mostrar();
void buscarElemento();
void
eliminarElemento();
void
eliminarElementos();
/* Funcion Principal
---------------------------------------------------------------------*/
int main()
{
lista = NULL;
int op;
// opcion del menu
system("color
0b");
do
{
menu1();
cin>>op;
switch(op)
{
case 1:
insertarInicio();
break;
case 2:
insertarFinal();
break;
case 3:
cout<<"\n\n
Lista Circular \n\n";
mostrar();
break;
case 4:
buscarElemento();
break;
case 5:
eliminarElemento();
break;
case 6:
eliminarElementos();
break;
default:
cout<<"OPCION NO VALIDA...!!!";
break;
}
cout<<endl<<endl;
system("pause"); system("cls");
}while(op!=7);
return 0;
}
//////////////////////MOSTRAR
MENU///////////////////////////////
void menu1()
{
cout<<"\n\t\tLISTA ENLAZADA
CIRCULAR\n\n";
cout<<" 1. INSERTAR AL
INICIO "<<endl;
cout<<" 2. INSERTAR AL
FINAL "<<endl;
cout<<" 3. REPORTAR LISTA "<<endl;
cout<<" 4. BUSCAR ELEMENTO "<<endl;
cout<<" 5. ELIMINAR ELEMENTO
'V' "<<endl;
cout<<" 6. ELIMINAR ELEMENTOS
CON VALOR 'V' "<<endl;
cout<<" 7. SALIR "<<endl;
cout<<"\n INGRESE OPCION: ";
}
//////////////////////INSERTAR
AL INICIO//////////////////////////
void
insertarInicio()
{
nodo *nuevo;
nuevo=new struct nodo;
cout<<"\n***INSERTA AL
INICIO*****\n";
cout<<"\nINGRESE DATO:";
cin>>nuevo->nro;
nuevo->sgte=NULL;
if(lista==NULL)
{
cout<<"PRIMER ELEMENTO..!!!";
lista=nuevo;
lista->sgte=lista;
fin=nuevo;
}
else
{
nuevo->sgte = lista;
lista = nuevo;
fin->sgte = lista;
}
}
//////////////////INSERTAR
AL FINAL/////////////////////
void
insertarFinal()
{
nodo *nuevo;
nuevo=new struct nodo;
cout<<"\n***INSERTA AL
INICIO*****\n";
cout<<"\nINGRESE DATO:";
cin>>nuevo->nro;
nuevo->sgte=NULL;
if(lista==NULL)
{
cout<<"PRIMER
ELEMENTO..!!!";
lista=nuevo;
lista->sgte=lista;
fin=nuevo;
}
else
{
fin->sgte = nuevo;
nuevo->sgte = lista;
fin = nuevo;
}
}
//////////////////MOSTRAR
TODOS LOS DATOS////////////////////////
void mostrar()
{ nodo *aux;
aux=lista;
int i=1;
if(lista!=NULL)
{
do
{
cout<<" "<<aux->nro;
aux = aux->sgte;
i++;
}while(aux!=lista);
}
else
cout<<"\n\n\tLista
vacia...!"<<endl;
}
//////////////////BUSCAR
ELEMENTO///////////////////////
void
buscarElemento() //esta funcion muestra la posicion del primer dato coincidente
//encontrado en la lista
{
nodo *aux;
int i = 1, valor , flag = 0;
cout<<"\nINGRESE ELEMENTO A
BUSCAR:";
cin>>valor;
if(lista !=NULL)
{
aux = lista;
do
{
if(aux->nro == valor)
{
cout<<"\n\n
Encontrado en posicion "<< i <<endl;
flag=1;
}
else
{
aux = aux->sgte;
i++;
}
}while(aux!=lista);
if(flag==0) cout<<"\n\n\tNumero
no econtrado..!"<<endl;
}
else
cout<<"\n\n\tLista
vacia...!"<<endl;
}
////////////////ELIMINAR
ELEMENTO DETERMINADO//////////////////////
void
eliminarElemento()
{
nodo *aux, *r, *q;
int i = 1, flag = 0,valor;
cout<<"\n INGRESE ELEMENTO A
ELIMINAR:";
cin>>valor;
if(lista !=NULL)
{
aux = lista;
do
{
if(aux->nro == valor)
{
if(aux==lista)//si es que
el dato a eliminar es el primero
{ r=lista;
lista=lista->sgte;
aux=aux->sgte;
fin->sgte=lista;
r->sgte=NULL;
if(fin->sgte==NULL)
{
lista==NULL;
aux==NULL;
delete(r);
cout<<"\nELEMENTO
ELIMINADO...!!!\n";
return;
}
else
{
delete(r);
cout<<"\nELEMENTO
ELIMINADO...!!!\n";
return;
}
}
else
{
if(aux==fin)//si es que
el dato a eliminar es al que apunta a fin
{
r=aux;
aux=aux->sgte;
q->sgte=aux;
fin=q;
r->sgte=NULL;
delete(r);
cout<<"\nELEMENTO
ELIMINADO...!!!\n";
return;
}
else
{
r=aux;
aux=aux->sgte;
q->sgte=aux;
r->sgte=NULL;
delete(r);
cout<<"\nELEMENTO ELIMINADO...!!!\n";
return;
}
}
flag=1;
}
else
{ q=aux;
aux = aux->sgte;
i++;
}
}while(aux!=lista);
if(flag==0)
cout<<"\n\n\tNumero no
econtrado..!"<<endl;
}
else
cout<<"LISTA VACIA...!!!!";
}
//////////////////////ELIMINAR
REPETIDOS/////////////////////
void
eliminarElementos()
{
nodo *aux, *r, *q;
int
flag = 0,valor;
cout<<"\n DATO REPETIDO A
ELIMINAR:";
cin>>valor;
if(lista !=NULL)
{ aux=lista;
while(aux->nro==valor)//si los primeros
elementos son repetidos
if(aux==lista) //esta funcion borra a estos
{
r=lista;
aux=lista->sgte;
lista=lista->sgte;
fin->sgte=lista;
r->sgte=NULL;
if(fin->sgte==NULL)
{
lista==NULL;
aux==NULL;
delete(r);
flag=1;
}
else
{
delete(r);
flag=1;
}
}
do
{
if(aux->nro == valor)
{
while(aux==lista)
{
r=lista;
aux=lista->sgte;
lista=lista->sgte;
fin->sgte=lista;
r->sgte=NULL;
if(fin->sgte==NULL)
{
lista==NULL;
aux==NULL;
delete(r);
}
else
delete(r);
}
if(aux==fin)//para si el
elemento a borrar es apuntado por *fin
{
r=aux;
aux=aux->sgte;
q->sgte=aux;
fin=q;
r->sgte=NULL;
delete(r);
}
else
{
r=aux;
aux=aux->sgte;
q->sgte=aux;
r->sgte=NULL;
delete(r);
}
flag=1;
}
else
{ q=aux;
aux = aux->sgte;
}
}while(aux!=lista);
if(flag==0)
cout<<"\n\n\tNumero no
econtrado..!"<<endl;
}
else
cout<<"LISTA VACIA...!!!!";
}
Nodos Centinelas
A veces las listas enlazadas tienen un nodo
centinela; al principio o al final de la lista, el cual no es usado para
guardar datos. Su propósito es simplificar o agilizar algunas operaciones,
asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la
lista (incluso alguna que no contenga datos) siempre tenga un primer y último
nodo.
