Duda sobre Listas simples.

[Swastik]

Buenas a todos, tengo una duda que pudiera parecer tonta, resulta estoy comenzando a estudiar los tipos de estructuras (pilas, colas, listas) y se me hace un poco engorroso por novato.

Me han mandado a investigar sobre Listas con centinelas ( o nodo ficticio) y no encuentro casi material, me han dejado esto que vendría siendo como seria el nodo centinela.

Código C:

typedef struct nodo
{
     char *dato;
     struct nodo *siguiente;
} NODO;
 
 
typedef struct centinela           // este seria el nodo centinela.
{
     int cant_nodos;
     int mayor;
     int menor;
     NODO *inicio;
}
 

Ahora bien, vengo trabajando con colas pilas y listas con dos estructuras (una para el nodo donde guardo los elementos y otra estructura con apuntadores para desplazarme)

por ejemplo una cola:

Código C:

/////// COLA //////
typedef struct nodo
{
  int    elem;
  struct nodo *sig;
  }NODO;
  
typedef struct cola
{
        NODO *frente;   //frente de la cola
        NODO *final;     //final de la cola
  }COLA;
 

la pregunta es, mi 2da estructura de la cola vendría siendo como un nodo centinela? por que la estructura es igual a la que puse anteriormente, no se si me explico.

[anrodse]

En tu cola lo que tienes es una lista de nodos enlazada, es decir tienes nodos que tienen un valor y un puntero al siguiente de la lista. Ademas, tienes otra estructura con un puntero al primero de la cola y otro para el ultimo. Para recorrer tu cola empiezas por el primero y continuas hasta llegar al ultimo.

El tu 'centinela' (nunca oi ese nombre) lo que tienes es una lista igual a la de la cola, y ademas otra estructura donde se guarda un puntero al primer elemento (necesario para empezar a recorrer la lista), el numero de elementos en la lista y dos valores mas (que no se que representan). Cada vez que insertes o elimines un elemento, deberas actualizar el valor de cant_nodos. Para recorrerla, empiezas por el inicio e iteras cant_nodos veces.

En resumen: son lo mismo, pero la forma de parar al recorrerlo es lo que cambia. Ademas, en la segunda puedes saber el tamaño de la lista sin recorrerla entera.