C# BasicLinkedList: Listas enlazadas

Vamos a seguir desarrollando el post anterior (“C# Clases autorreferenciadas“) para generar una lista enlazada, una lista enlazada es una colección lineal o una secuencia de nodos representados con clases autorreferenciadas. El acceso a la lista se realiza desde el primero nodo (raíz o head) y se recorre accediendo al miembro que apunta al siguiente nodo y así hasta el final (el miembro del último nodo que apunta al siguiente se define como null para evitar errores). Normalmente las listas tienen las operaciones comunes para trabajar con sus nodos, vamos a definir métodos para:

  • Construir una lista vacía y darle un nombre.
  • Insertar un nodo en la cabecera.
  • Insertar un nodo al final.
  • Eliminar el primer nodo de la lista.
  • Eliminar un nodo del final de la lista.
  • Comprobar si una lista está vacía.
  • Imprimir por pantalla el contenido.
  • Obtener el número de elementos o nodos de la lista.

Clase para definir un nodo

Similar al ejemplo anterior definimos una clase que represente un nodo. Definimos dos constructores, el segundo permite crear un nodo y definir el nodo al que apunta como siguiente elemento en la lista.

Lo más remarcable de la clase es la referencia object. Nos permite almacenar tipos de datos simples como si fueran objetos. El tipo object es un alias para Object en .NET. Todos los tipos de variables son herencia directa de este tipo. Podemos asignar valores de cualquier tipo a variables de tipo object. Cuando una variable se convierte a un tipo object a esta operación se le llama boxing o boxed. Cuando se realiza la operación inversa se denomina unboxing.

Clase lista

La clase lista tiene contiene como miembros head y tail. Son respectivamente referencias al primer y último nodo de la lista, también definimos una variable string para asignar un nombre a la lista.

 

Definimos un método que nos resultará de utilidad más adelante, el método IsListEmpty retorna true si la cabeza de lista apunta a null.

Ahora definimos un método para operar sobre la lista insertando un nuevo nodo al inicio de la misma.  Si la lista esta recién creada o vacía la cabeza y la cola apunta al nuevo y único la misma. En caso contrario la cabeza apunta al nuevo nodo y le pasamos el nodo de cabeza actual como miembro para que quede en segundo lugar.

Para añadir un nodo al final definimos el siguiente método:

Antes de continuar con un método para borrar un elemento del inicio de la lista vamos a definir una clase EmptyListException para lanzar una excepción cuando se producen operaciones ilegales sobra la lista, por ejemplo si la lista está vacía. Usamos System.ApplicationException para excepciones generadas por nuestra programa.

Ahora ya podemos crear un método para borrar un elemento de la cabecera de la lista. Si la lista está vacía lanza una excepción que podemos capturar y tratar desde el programa principal. Después obtenemos el miembro del nodo de cabecera y restablece las referencias del primer y último nodo (si solo hay un nodo en la lista head y last quedaran a null, si hay más de un elemento avanzamos al siguiente nodo la cabecera).

Visto el anterior ejemplo borrar el último nodo es similar. Pero en este caso el método que debemos seguir  nodo no es muy eficiente (esto se solucionaría con una lista doblemente enlazada). Recorremos desde el primero nodo uno de detrás de otro hasta que el nodo siguiente no sea el último, de esta manera hacemos que apunte a null quedando fuera el último nodo.

Ahora solo nos queda un método para imprimir los nodos de la lista.

Ahora veamos como se puede utilizar:

Referencias externas

 

Anuncios

C# Clases autorreferenciadas

Una clase autorreferenciada es muy común para almacenar datos de forma dinámica y consumirlos a medida que los necesitamos en otro proceso, una clase autorreferenciada contiene un miembro de la clase que hace referencia a un objeto del mismo tipo. La unión de las clases referenciadas crea una lista de nodos que podemos recorrer accediendo de forma sucesiva desde el nodo raíz  al miembro del nodo que apunta al siguiente y así sucesivamente.

El ejemplo de abajo es como se organiza un array bidimensional en memoria, realmente se reservan zonas de memoria contiguas como en un array de una dimensión.

Frente a un array estático (los elementos se organizan en memoria de forma contigua y su tamaño se reserva en la declaración de la variable)  con un número de elementos determinados tiene una importante ventaja, una lista basada en nodos autoenlazados puede modificar su tamaño de forma dinámica en tiempo de ejecución (aunque también tiene un coste computacional que puede afectar al rendimiento de nuestro programa el manejo de grandes estructuras de memoria que reservan y liberan memoria según su necesidad).

El ejemplo de arriba es un ejemplo muy básico de un clase autorreferenciada, por supuesto los nodos pueden contener todos los datos que necesitemos de cualquier tipo.

Para ir añadiendo nuevos nodos durante la ejecución de nuestro programa haremos uso de la reserva de memoria dinámica con el operador new, este operador recibe como operando el tipo de objeto que se asignará de forma dinámica y devuelve una referencia a un objeto de este tipo.

Basándonos en esta arquitectura podemos crear listas enlazadas, colas o arboles. Cada tipo de estructura tiene propósitos diferentes y puede ser aplicado según el problema que debamos resolver.

 

 

C# SerialConsoleApp2: Gestión básica de la línea serie

A partir del ejercicio C# SerialConsoleApp1: Gestión básica de la línea serie vamos a seguir refinando nuestra clase básica para comunicaciones RS232.

Constructor

Hemos sobrecargado el método OpenCOMPort para simplificarlo, el nuevo método sólo recibe el parámetro con la cadena que define el puerto que queremos abrir, en la mayoría de los casos el resto de parámetros se mantienen y suelen ser los mismos.

Definimos una serie de constantes como atributos de la clase con los valores por defecto.

Destructor de la clase

También comprobamos en el destructor de la clase si el puerto aún sigue abierto y si es así lo cerramos.

GetPortList: Nuevo método

Definimos un nuevo método para obtener la lista de puertos y así poder hacer lo que queramos (no solo mostrarlos por consola), por ejemplo alimentar un selector desplegable con esta información en una aplicación de ventanas.

El nuevo método retorna una lista de cadenas. Una clase List<T> representa una colección de objetos del mismo tipo indexados en una lista por posición. Al igual que cualquier clase tiene un constructor, propiedades y métodos (Add, BinarySearch, …)

Su uso es igualmente sencillo:

Leer de la línea serie byte a byte

Vamos a mejorar ligeramente el método de lectura para leer el buffer serie un valor cada vez, esto nos permite mayor control de la información leída realizando un tratamiento de cada byte a medida que llega.

Resultado

Volvemos a conectar el Arduino del primer ejercicio para poder leer la cadena que envía.