ListasSimplesEnlazadas

Listas Simples
La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodos se organizan
de modo que cada uno apunta al siguiente, y el último no apunta a nada, es decir, el puntero del
nodo siguiente vale NULL.
En las listas abiertas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es
un puntero a ese primer nodo y llamaremos a ese nodo lacabeza de la lista. Eso es porque mediante
ese único puntero podemos acceder a toda la lista.
Cuando el puntero que usamos para acceder a la lista vale NULL, diremos que la lista está vacía.
El nodo típico para construir listas tiene esta forma:
struct nodo {
int dato;
struct nodo *siguiente;
};
En el ejemplo, cada elemento de la lista sólo contiene un dato de tipo entero, pero en la práctica no
haylímite en cuanto a la complejidad de los datos a almacenar.
Declaraciones de tipos para manejar listas en C++
Normalmente se definen varios tipos que facilitan el manejo de las listas, en C/C++, la declaración
de tipos puede tener una forma parecida a esta:
struct Nodo {
int dato;
struct _nodo *siguiente;
};
Nodo *pNodo;
Nodo *Lista;
Nodo es el tipo para declarar nodos, evidentemente. Tambiénpuede definirse como una clase.
pNodo es el tipo para declarar punteros a un nodo.
Lista es el tipo para declarar listas, como puede verse, un puntero a un nodo y una lista son la misma
cosa. En realidad, cualquier puntero a un nodo es una lista, cuyo primer elemento es el nodo
apuntado.

Es muy importante que el programa nunca pierda el valor del puntero al primer elemento, ya que si
no existeninguna copia de ese valor, y se pierde, será imposible acceder al nodo y no se podrá
liberar el espacio de memoria que ocupa. También se puede utilizar un apuntador de referencia hacia
el final de la lista, con la fina de en algunos casos evitar recorridos innecesarios.

Operaciones básicas con listas
Con las listas se tiene un pequeño repertorio de operaciones básicas que se pueden realizar:



Añadir o insertar elementos.
Buscar o localizar elementos.
Borrar elementos.
Moverse a través de una lista, anterior, siguiente, primero.

Cada una de estas operaciones tendrá varios casos especiales, por ejemplo, no será lo mismo
insertar un nodo en una lista vacía, o al principio de una lista no vacía, o la final, o en una posición
intermedia.
Insertar un elemento en una lista vacía
Este es,evidentemente, el caso más sencillo. Se parte de que ya se tiene el nodo a insertar y, por
supuesto un puntero que apunte a él, además el puntero a la lista valdrá NULL:

Lista vacía
El proceso es muy simple, bastará con que:
1. nodo->siguiente apunte a NULL.
2. Lista apunte a nodo.
Insertar un elemento en la primera posición de una lista

Se puede considerar el caso anterior como un caso particularde éste, la única diferencia es que en
el caso anterior la lista es una lista vacía, pero siempre se puede, y debe considerar una lista vacía
como una lista.
De nuevo se parte de un nodo a insertar, con un puntero que apunte a él, y de una lista, en este caso
no vacía:
El proceso sigue siendo muy sencillo:
1. Hacer que nodo->siguiente apunte a Lista.
2. Hacer que Lista apunte a nodo.

Insertarun elemento en la última posición de una lista
Este es otro caso especial. Para este caso se parte de una lista no vacía:

El proceso en este caso tampoco es excesivamente complicado:
1. Se necesita un puntero que señale al último elemento de la lista. La manera de conseguirlo
es empezar por el primero y avanzar hasta que el nodo que tenga como siguiente el valor
NULL o manejar un nodo dereferencia hacia el ultimo nodo.
2. Hacer que nodo->siguiente sea NULL.
3. Hacer que ultimo->siguiente sea nodo.

Insertar un elemento a continuación de un nodo cualquiera de una lista
De nuevo se puede considerar el caso anterior, como un caso particular de este. Ahora el nodo
"anterior" será aquel a continuación del cual insertaremos el nuevo nodo:

Se supone que ya se dispone del nuevo nodo a...