Listas doblemente enlazadas en C++
Una
lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos
enlaces, uno al nodo siguiente, y otro al anterior.
Las
listas doblemente enlazadas no necesitan un nodo especial para acceder a ellas,
pueden recorrerse en ambos sentidos a partir de cualquier nodo, esto es porque
a partir de cualquier nodo, siempre es posible alcanzar cualquier nodo de la
lista, hasta que se llega a uno de los extremos.
El
nodo típico es el mismo que para construir las listas que hemos visto, salvo
que tienen otro puntero al nodo anterior:
struct nodo {
int dato;
struct nodo *siguiente;
struct nodo *anterior;
};
El puntero anterior del
primer elemento debe apuntar hacia NULL (el
inicio de la lista).
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos: comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento; comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.
Resumiendo, el desplazamiento se hace en ambas direcciones, del primer al último elemento y/o del último al primer elemento.
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos: comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento; comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.
Resumiendo, el desplazamiento se hace en ambas direcciones, del primer al último elemento y/o del último al primer elemento.
Declaraciones de tipos para manejar listas doblemente enlazadas en C
Para definir un elemento de la lista será utilizado
el tipo struct.
El elemento de la lista contendrá un campo dato, un puntero anterior y un puntero siguiente.
Los punteros anterior y siguiente deben ser del mismo tipo que el elemento, de lo contrario no va a poder apuntar hacia un elemento de la lista.
El puntero anterior permitirá el acceso hacia el elemento anterior mientras que el puntero siguiente permitirá el acceso hacia el próximo elemento.
El elemento de la lista contendrá un campo dato, un puntero anterior y un puntero siguiente.
Los punteros anterior y siguiente deben ser del mismo tipo que el elemento, de lo contrario no va a poder apuntar hacia un elemento de la lista.
El puntero anterior permitirá el acceso hacia el elemento anterior mientras que el puntero siguiente permitirá el acceso hacia el próximo elemento.
typedef struct dl_ElementoLista {
char *dato;
struct dl_ElementoLista *anterior;
struct dl_ElementoLista *siguiente;
}dl_Elemento;
char *dato;
struct dl_ElementoLista *anterior;
struct dl_ElementoLista *siguiente;
}dl_Elemento;
Para tener el control de la lista es preferible conservar algunos elementos: el primer elemento, el último elemento y el número de elementos.
Para esto, será utilizada otra estructura (no es obligatorio, pueden ser utilizadas variables).
typedef struct dl_ListaIdentificacion {
dl_Elemento *inicio;
dl_Elemento *fin;
int tamaño;
}dl_Lista;
dl_Elemento *inicio;
dl_Elemento *fin;
int tamaño;
}dl_Lista;
El puntero inicio contendrá la dirección del primer elemento de la lista.
El puntero fin va a contener la dirección del último elemento de la lista.
La variable tamaño contendrá el número de elementos.
En cualquier posición de la lista, los punteros inicio y fin apuntan siempre al primer y último elemento.
El campo tamaño va a contener el número de elementos de la lista cualquiera que sea la operación efectuada sobre la lista.
Un procedimiento para borrar un elemento en la posición p en una lista
doblemente enlazada es:
void borrar (posicion p)
{
if (p->anterior != NULL)
p->anterior->siguiente
= p->siguiente;
if (p->siguiente != NULL)
p->siguiente->anterior
= p->anterior;
free(p);
}
El procedimiento anterior se
expresa de forma gráfica en como muestra la figura:
Dentro del tipo
abstracto de listas doblemente
enlazadas podemos proponer las siguientes primitivas:
- tLista crear ()
- void destruir (tLista l)
- tPosicion primero (tLista l)
- tPosicion fin (tLista l)
- void insertar (tElemento x, tPosicion p, tLista l)
- void borrar (tPosicion *p, tLista l)
- tElemento elemento(tPosicion p, tLista l)
- tPosicion siguiente (tPosicion p, tLista l)
- tPosicion anterior (tPosicion p, tLista l)
- tPosicion posicion (tElemento x, tLista l)
ESPECIFICACIÓN SEMANTICA Y SINTACTICA.
- tLista crear ()
Argumentos: Ninguno.
Efecto: (Constructor primitivo). Crea un objeto del tipo tLista. - void destruir
(tLista l)
Argumentos: Una lista.
Efecto: Destruye el objeto l liberando los recursos que empleaba. Para volver a usarlo habrá que crearlo de nuevo. - tPosicion
primero (tLista l)
Argumentos: Una lista.
Efecto: Devuelve la posición del primer elemento de la lista. - tPosicion fin
(tLista l)
Argumentos: Una lista.
Efecto: Devuelve la posición posterior al último elemento de la lista. - void insertar
(tElemento x, tPosicion p, tLista l)
Argumentos:
l: Es modificada.
p: Es una posición válida para la lista l.
x: Dirección válida de un elemento del tipo T con que se instancia la lista, distinta de NULL.
p: Es una posición válida para la lista l.
x: Dirección válida de un elemento del tipo T con que se instancia la lista, distinta de NULL.
Efecto: Inserta
elemento x en la posición p de la lista l desplazando todos los demás elementos
en una posición.
- void borrar
(tPosicion *p, tLista l)
Argumentos:
l: Es modificada.
p: Es una posición válida para la lista l.
p: Es una posición válida para la lista l.
Efecto: Elimina el
elemento de la posición p de la lista l desplazando todos los demás elementos
un una posición.
- tElemento
elemento(tPosicion p, tLista l)
Argumentos:
l: Una lista.
p: Es una posción válida de la lista l.
p: Es una posción válida de la lista l.
Efecto: Devuelve el
elemento que se encuentra en la posición p de la lista l.
- tPosicion
siguiente (tPosicion p, tLista l)
Argumentos:
l: Una lista.
p: Es una posición válida para la lista l, distinta de fin(l).
p: Es una posición válida para la lista l, distinta de fin(l).
Efecto: Devuelve la
posición siguiente a p en l.
- tPosicion
anterior (tPosicion p, tLista l)
Argumentos:
l: Una lista.
p: Es una posición válida para la lista l, distinta de primero(l).
p: Es una posición válida para la lista l, distinta de primero(l).
Efecto: Devuelve la
posición que precede a p en l.
- tPosicion
posicion (tElemento x, tLista l)
Argumentos:
l: Una lista.
x: Dirección válida de un elemento del tipo T con que se instancia la lista, distinta de NULL.
x: Dirección válida de un elemento del tipo T con que se instancia la lista, distinta de NULL.
Efecto: Si x se
encuentra entre los elementos de la lista l, devuelve la posición de su primera
ocurrencia. En otro caso, devuelve la posición fin(l).
EJEMPLO
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct nodo elemento;
struct nodo{
int dato;
nodo*sig;
nodo*ant;
};
elemento *nuevonodo(){
return ((elemento*) malloc (sizeof(elemento)));
}
int main (){
elemento *p, *q, *i, *d;
char r,r2;
int c = 1;
do{
p = nuevonodo();
cout<<"POR FAVOR INGRESE EL DATO : ";
cin>>p->dato;
if (c==1){
p->sig = NULL;
p-> ant = NULL;
d = p; i = p;
}
else{
cout<<"quiere insertar a la izquierda o a la derecha? I = izquierda/ D = Derecha\n";
cin>>r2;
if (r2 == 'd'||r2 == 'D'){
p-> sig = NULL;
d-> sig = p;
p-> ant = d;
d = p;
}else{
p-> ant = NULL;
i-> ant = p;
p-> sig = i;
i = p;
}
}
c++;
cout<<"Desea ingresar un valor? S = si / N = no \n";
cin>>r;
}while(r == 's'||r == 'S');
// Recorrido
q=i;
cout<<"Recorrido de izquierda...\n";
do{
cout<<"\t"<<q->dato;
q = q-> sig;
}while (q != NULL);
q=d;
cout<<"\nRecorrido de derecha...\n";
do{
cout<<"\t"<<q->dato;
q = q -> ant;
}while (q != NULL);
return 0;
}
Elaborar un programa que me permita ingresar datos, luego presentar el recorrido de derecha y de izquierda. Y eliminar un nodo.