Lista (estructura de datos)
De Wikipedia, la enciclopedia libre
La forma más simple de estructura dinámica es la lista abierta o lista ligada. 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 la cabeza de la lista. Eso es porque mediante ese único puntero podemos acceder a toda la lista.
Lista ligada con tres valores enteros
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 hay límite en cuanto a la complejidad de los datos a almacenar.
[editar] Declaraciones de tipos para manejar listas en C
Normalmente se definen varios tipos que facilitan el manejo de las listas, en C, la declaración de tipos puede tener una forma parecida a esta:
typedef struct _nodo {
int dato;
struct _nodo *siguiente;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;
tipoNodo es el tipo para declarar nodos, evidentemente.
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 nuestro programa nunca pierda el valor del puntero al primer elemento, ya que si no existe ninguna copia de ese valor, y se pierde, será imposible acceder al nodo y no podremos liberar el espacio de memoria que ocupa.
[editar] Tipos de listas
- Lista lineal: En la cual el último nodo apunta a NULL.
- Lista circular: El último nodo apunta al primero y que más.
- Lista doblemente enlazada: Los nodo aparte de tener un nodo siguiente, tiene un nodo llamado anterior el cual apunta al anterior nodo.
struct nodo
{
int dato;
nodo *sig;
}
class listaCircular{
nodo*inicio;
public:
listaCircular(){inicio=NULL}
nodo*buscar_pos(int elem);
~listaCircular();
};
