Implementación de una Cola mediante Listas Enlazadas.

Antes de Leer este Post

Aún y cuando este escrito menciona algunas de las características de las Colas(Queues) y Lista Enlazadas(Linked Lists) con el propósito de situar al lector en el contexto de la problemática a resolver, este post  no tiene la intención de ahondar en dichas estructuras Esto en vista de que existen infinidad de recursos en internet que pueden proporcionar al lector un profundo entendimiento acerca de estos tópicos.

Introducción a la Problemática

Las operaciones  encolar y desencolar que pueden ser efectuadas en una cola siempre poseen una complejidad constante de O(1), mientras que  la complejidad computacional de agregar  y remover nodos en una lista enlazada puede ir de O(1) a O(n), en virtud de la posición del nodo.

1_2

Ingreso de Elementos en Lista Vacía

De esta forma, insertar o purgar un nodo al principio de una lista enlazada tiene una complejidad de O(1) debido que no se debe recorrer la estructura con  el fin de llevar a cabo semejantes acciones. No obstante, el realizar un acción sobre una posición n( donde n es diferente de cero ) en una lista enlizada, conlleva el recorrer n posiciones en la  lista antes de poder desempeñar tal acción. Así, se concluye que el ejecutar una tarea sobre una lista enlazada, puede arrastrar una complejidad O(n).

2

Ingreso de Nodos en Lista con Elementos

2Entonces,  si las operaciones que pueden ser realizadas tanto en una cola como en una lista enlazadas poseen complejidades computacionales diferentes ¿Cómo es posible implementar una cola mediante una lista enlazada? La respuesta a es  absurdamente sencilla. Mediante una lista enlazada capaz de:

  • Agregar nuevos nodos al final de la lista en tiempo constanteEsto es posible mediante un nodo auxiliar capaz de guardar una referencia al último nodo de la lista( en caso de que exista ).
  • Remover el primer elemento de la lista en un tiempo  O(1).

Código

Es bien sabido que las listas enlazadas se erigen a partir de un conjunto de nodos que antes de ser conectados, primero deben ser concebidos. Así, la clase Nodo tiene como objetivo el crear los eslabones  que darán pie a la cola que se intenta poner en funcionamiento. Más aún, semejante clase asigna las propiedades de nodo siguiente y dato a cada objeto Nodo. Cabe destacar que Nodo no cuenta con el módulo asignarDato en virtud de que los datos hospedados en la cola no deben sufrir alteraciones.

Por su parte, la clase ListaEnlazada es responsable de llamar a la clase Nodo y especificarle los datos que deben estar contenidos en los elementos de la cola y la manera en que dichos elementos deben estar enlazados. Cabe destacar que aún y cuando esta clase se compone de múltiples métodos, este post tan sólo detalla los modulos más relevantes.

El método especial init  inicializa las variables de instancia de la clase:
  • cabeza: Referencia al elemento que encabeza la cola. Es decir, el nodo próximo a salir de la estructura.
  • cola: Referencia al último nodo agregado a la cola. Esta referencia es vital ya que permite agregar un nodo a la estructura en tiempo O(1).
  • tamanio: Tamaño de la cola.

El modulo encolar realiza una llamada a la clase Nodo para crear la variable nuevoNodo y posteriormente realiza las siguientes acciones:

  • Identifica si un objeto listaEnlazada se encuentra vacío o no. De encontrarse el objeto falto de contenido( es decir, si la cabeza de lista apunta a None ), el método asigna la referencia de nuevoNodo a None y apunta la cabeza de la lista a nuevoNodo. De lo contrario, de no estar la lista vacía, este modulo simplemente asigna la referencia de la colanuevoNodo.
  • Utiliza el nodo auxiliar cola para guardar la referencia al último nodo agregado a la lista. Dicho de otra forma, la variable cola siempre preserva a la variable nuevoNodo.
  • Aumenta el valor de la variable tamanio en 1.

Por último, el código perteneciente al método desencolar únicamente se encarga de revisar, por medio de la cabeza del objeto lista  si existen elementos en la cola. De existir, nodos en la estructura( es decir, de apuntar la cabeza a algo diferente de None), el nodo próximo a la cabeza, será asignado a la propia cabeza.

3

Eliminación del Primer Elemento de la Cola.

El código completo puede ser descargado desde aquí.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s