Lista Enlazada
Es una colección de elementos dispuestos uno detrás del otro, en la que cada elemento se conecta al siguiente por un “Enlace” o “Puntero”.
Los nodos de las listas al igual que las colas y pilas, está compuesta por una parte de información (que pude ser datos enteros, flotantes, caracteres, estructuras..) y el puntero que mantiene el enlace entre un nodo y otro.
Existen varios tipos de Listas, pero para efectos de comprensión y sintetización, hablaremos de cuatro tipos esenciales de listas:
Tipos De Listas
- Lista simplemente enlazada: Cada nodo, contiene un único apuntador hacia el siguiente nodo, por lo cual hace de él una estructura muy eficiente, ya que el último de la lista apunta hacia null, por ello, es fácil hacer recorridos directos.
- Listas Doblemente enlazada: Esta lista se caracteriza por que sus nodos contienen dos punteros, uno hacia el nodo siguiente y otro hacia el nodo anterior.
- Listas Circulares: Este tipo de lista, es sólo una extensión de las lista simplemente enlazada, con la diferencia que el último elemento se enlaza al primer elemento de la lista, lo cual permite el recorrido en forma de anillo
- Lista Circular Doblemente enlazada: Quizá este tipo de lista, sea la más compleja, ya que es la combinación de la lista circular y las doblemente enlazadas, ya que es una lista doblemente enlazada donde el primer elemento se conecta con el último y viceversa.
El TAD (Tipo Abstracto de Datos) Lista
En una lista podemos almacenar datos del mismo tipo, con la característica que puede contener un número indeterminado de elementos y que, mantienen un orden explícito, porque cada elemento, se une a otro mediante un puntero, como ya se ha dicho anteriormente, los elementos constitutivos de las listas se denominan nodos.
Las listas son estructuras de datos dinámicos, por tanto, pueden cambiar de tamaño durante la ejecución del programa, aumentando o disminuyendo el número de nodos.
Un aspecto importante de las listas es que las inserciones, las podemos hacer por el frente, al final, en medio, después de..., etc, etc, etc; es decir que, no existen reglamentos que nos restringían añadir datos a una lista, en la posición que nosotros queramos.
De igual manera, para las eliminaciones de nodos, podemos hacerlo como nosotros lo queramos, si embargo, se acostumbra ingresando el campo de información o dato que se desea eliminar.
Operaciones con las listas
P: puntero a un nodo
L: puntero a la lista
àListaVacia(L): Iniciliza la lista L, como lista vacía
àempty(L): determina si la lista está vacía o no
àInsertar(L, x, p): Inserta al dato x, en un nuevo nodo de la lista L, después del nodo apuntado por p
àeliminar(L, x): elimina, de la lista L, el nodo que contiene a x
àNodo(p): Hace referencia la nodo que apunta p
àInfo(p): hace referencia al info del nodo
ànext(p): siguiente dirección si p no es NULL
àInfo(next(p)): info del nodo que sigue a nodo (p) en la lista
Se puede decir que, estas son las operaciones básicas para una lista; sin embargo, como ya se ha insistido, eso dependerá del programador y de la complejidad del problema que se está resolviendo, además del tipo de lista que se haya elegido.
Para ello, acontinuación hablaremos, por separado, de cada uno de los tipos de listas.
Listas Simplemente Enlazadas
Una estructura como ésta, requiere, que se tengan en cuenta, las operaciones básicas que, se realizarán:
Estructura del Nodo
Por ejemplo, la podemos definir así:
struct nodo{
int x;
struct nodo *sig;
};
typedef struct nodo *Lista; /* Sinónimo para el tipo de dato*/
Lista p; /* Aquí guardaremos la dirección del primer nodo */
p=getnodo();
Función getnodo()
Esta función, se utiliza para pedirle memoria a la computadora, lo cual puede realizarse en las misma función de insertar, pero para tener un mekor orden, es mejor hacerlo por aparte.
Por tanto, es evidente que, ésta función lo que devuelve es una dirección de memoria.
Lista getnodo()
{
Lista p;
p=(Lista)malloc(sizeof(struct nodo));
return p;
}
Operaciones con las listas
P: puntero a un nodo
L: puntero a la lista
àListaVacia(L): Iniciliza la lista L, como lista vacía
àempty(L): determina si la lista está vacía o no
àInsertar(L, x, p): Inserta al dato x, en un nuevo nodo de la lista L, después del nodo apuntado por p
àeliminar(L, x): elimina, de la lista L, el nodo que contiene a x
àNodo(p): Hace referencia la nodo que apunta p
àInfo(p): hace referencia al info del nodo
ànext(p): siguiente dirección si p no es NULL
àInfo(next(p)): info del nodo que sigue a nodo (p) en la lista
Se puede decir que, estas son las operaciones básicas para una lista; sin embargo, como ya se ha insistido, eso dependerá del programador y de la complejidad del problema que se está resolviendo, además del tipo de lista que se haya elegido.
Para ello, a continuación hablaremos, por separado, de cada uno de los tipos de listas.
Listas Simplemente Enlazadas
Una estructura como ésta, requiere, que se tengan en cuenta, las operaciones básicas que, se realizarán:
Estructura del Nodo
Por ejemplo, la podemos definir así:
struct nodo{
int x;
struct nodo *sig;
};
typedef struct nodo *Lista; /* Sinónimo para el tipo de dato*/
Lista p; /* Aquí guardaremos la dirección del primer nodo */
p=getnodo();
Función getnodo()
Esta función, se utiliza para pedirle memoria a la computadora, lo cual puede realizarse en las misma función de insertar, pero para tener un mekor orden, es mejor hacerlo por aparte.
Por tanto, es evidente que, ésta función lo que devuelve es una dirección de memoria.
Lista getnodo()
{
Lista p;
p=(Lista)malloc(sizeof(struct nodo));
return p;
}
Función Borrar después de...
Ésta función es muy similar a la función de eliminar de las pilas y colas, con la diferencia que debemos enlazar el nodo anterior con el siguiente nodo:
Algoritmo:
- Crear un nodo auxiliar apuntado por q.
- si p, apunta a nullo p->sig apunta a NULL, imprima mensaje de error
- sino; q, en suparte de siguiente, debe tener la dirección a la que apuntaba, p->sig.
- p->sig debe apuntar a q en su parte de siguiente.
- Liberar de memoria el nodo apuntado por q.
void delafter(Lista p, char *px)
{
Lista q;
If(p==NULL || p->sig==NULL)
Printf(“ERROR, lista vacía\a\n”);
Else
{
q->sig=p->sig;
p->sig=q->sig;
free(q);
}
}
Función de Lista Vacía
Int empty(Lista p)
{
int r;
if(p==NULL)
r=1;
else
r=0;
return r;
}
/* Para limpiar la lista*/
void limpiar (Lista L)
{
L=NULL;
}
Con ésta función, lo que hacemos es inicializar la lista a NULL, por lo que se pierden los elementos que habíamos guardado en los nodos. Pero Ojo, eso no significa que hayamos liberado memoria que ocuparon, los nodos, esa memoria será liberada, cuando se deje de ejecutar el programa, o si hubiésemos, utilizado la función free(), para cada nodo.
Función Buscar
Ésta función, nos devuelve, la dirección de memoria de un valor que deseamos buscar en la lista.
Lista buscar(Lista frente, char x)
{
/* frente: puntero que indica la cabeza de una lista.
X: carácter que deseamos buscar
*/
Lista dir;
For(dir=frente; dir!=NULL; dir=dir->sig)
If(x==dir->x)
Return dir;
Return NULL;
}
