3.3 LISTAS LINEALES SIMPLEMENTE ENLAZADAS

Una lista enlazada es una lista que se construye empleando apuntadores. Además no tiene un tamaño fijo, si no que puede crecer o decrecer durante la ejecución del programa.

Siguiente nulo

Para construir una lista lineal, primero tendremos que definir el tipo de los elementos que van a formar parte de la misma. Por ejemplo, cada elemento de la lista puede definirse como una estructura de datos con dos o más miembros: un puntero al elemento siguiente y una variable que defina el área de datos. El área de datos puede ser de un tipo predefinido o de un tipo definido por el usuario. El tipo de cada elemento de una lista puede venir definido de la forma siguiente:

class Nodo

{

// Atributos

// Defina aquí los datos o un puntero a los datos

Nodo *siguiente; // puntero al siguiente elemento

// Métodos

//…

};

Se observa que la clase Nodo definirá una serie de atributos correspondientes a los datos que deseemos manipular, además de un atributo especial, denominado siguiente, para así permitir que cada elemento pueda hacer referencia a su sucesor formando así una lista enlazada.

Una vez creada la clase de objetos Nodo la asignación de memoria para un elemento se haría de la siguiente manera:

int main ( )

{

Nodo *p=0; //puntero a un elemento

// Asignar memoria para un elemento

p=new Nodo;

// Este elemento no tiene un sucesor

p->siguiente=0;

// Operaciones cualesquiera

// Liberar la memoria ocupada por el elemento p

delete p;

}

El código Nodo *p define un puntero p a un objeto de la clase Nodo. La sentencia p=new Nodo crea (asigna memoria para) un objeto de tipo nodo, genera un puntero (direccion de memoria) que direcciona este nuevo objeto y asigna este puntero a la variable p. La sentencia p->siguiente=0 asigna al miembro siguiente del objeto apuntado por p el valor cero (puntero nulo), indicando así que después de este elemento no hay otro; esto es que este elemento es él ultimo de la lista.

NULL es un valor de apuntador constante especial que sirve para dar un valor a una variable de apuntador que de otro modo no tendría valor. Podemos asignar NULL a una variable de apuntador de cualquier tipo. Permite crear estructuras de datos finitas. Así mismo suponiendo que p apunta al principio de la lista, diremos que dicha lista esta vacia si p vale cero. Ejemplo, después de ejecutar las sentencias:

p=0 // Lista vacía

p=new nodo; // elemento p

p->siguiente=0; // no hay siguiente elemento

Tenemos una lista de un elemento:

nulo

Para añadir un nuevo elemento a la lista:

q=new Nodo; // Crear un nuevo elemento

q->siguiente=p; // almacenar la direccion del elemento siguiente

p=q; // p apunta al principio de la lista

Donde q es un puntero a un objeto de tipo Nodo. Ahora se tiene una lista de dos elementos. Los elementos nuevos se añaden al principio de la lista. Analicemos las tres sentencias anteriores. Partimos de que tenemos una lista referenciada por p con un solo elemento. La sentencia q=new Nodo crea un nuevo elemento:

q p

nulo

La sentencia q->siguiente=p hace que el sucesor del elemento creado sea el anteriormente creado. Se observa que ahora q->siguiente y p tiene el mismo valor; esto es, la misma dirección, por lo tanto, apuntan al mismo elemento:

nulo

Finalmente la sentencia p=q hace que la lista quede de nuevo apuntada por p; es decir, para nosotros p es siempre el primer elemento de la lista.

nulo

Ahora p y q apuntan al mismo elemento, al primero. Si ahora se ejecutara una sentencia q=q->siguiente;¿Quién es q->siguiente? Es el atributo siguiente del objeto apuntado por q que contiene la dirección de memoria donde se localiza el siguiente elemento al apuntado por p. Si este valor se lo asignamos a q, entonces q apuntara al mismo elemento que apuntaba q->siguiente. El resultado es que q apunta ahora al siguiente elemento como se puede ver en la figura.

nulo

Esto es una idea de cómo avanzar elemento a elemento sobre una lista. Si ejecutamos de nuevo la misma sentencia q=q->siguiente;

¿Qué sucede? Sucede que como q->siguiente vale cero, a q se le ha asignado el valor cero. Cuando en una lista utilizamos un puntero para ir de un elemento al siguiente, en el ejemplo anterior q, diremos que hemos llegado al final de la lista cuando q tome el valor cero.