91 - Colección : LinkedList<T>


La clase LinkedList<T> nos facilita administrar una lista doblemente encadenada. A diferencia de la clase List<T> es más eficiente cuando tenemos que insertar y borrar elementos del medio de la colección.

Hay que tener en cuenta que con la clase List<T> si insertamos un elemento en la primer posición se deben desplazar todos los elementos una posición hacia adelante, en cambio con la clase LinkedList<T> solo se modifican punteros.

Como desventaja no podremos acceder a los elementos por medio de un subíndice como lo hacemos con la clase List<T> y deberemos recorrerla mediante una estructura repetitiva.

Problema 1:

Confeccionar un programa que cree un objeto de la clase LinkedList<T> y llamar a sus métodos y propiedades principales.

Programa:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProblemaLinkedList1
{
    class Program
    {
        private static void ImprimirLista(LinkedList<int> lista)
        {
            LinkedListNode<int> reco = lista.First;
            while (reco!=null)
            {
                Console.Write(reco.Value + "-");
                reco = reco.Next;
            }
            Console.WriteLine();
        }

        private static void ImprimirUltimoAlPrimero(LinkedList<int> lista)
        {
            LinkedListNode<int> reco = lista.Last;
            while (reco!=null)
            {
                Console.Write(reco.Value + "-");
                reco = reco.Previous;
            }
            Console.WriteLine();
        }

        static void Main(string[] args)
        {
            LinkedList<int> lista1 = new LinkedList<int>();
            lista1.AddFirst(30);
            lista1.AddFirst(20);
            lista1.AddFirst(10);
            lista1.AddFirst(5);
            lista1.AddLast(1);
            Console.WriteLine("Imprimimos la lista");
            ImprimirLista(lista1);
            Console.WriteLine("Cantidad de nodos de la lista:"+lista1.Count);
            Console.WriteLine("Imprimimos la lista del final al principio.");
            ImprimirUltimoAlPrimero(lista1);
            Console.ReadKey();
        }
    }
}

Creamos un objeto de la clase LinkedList<T> con elementos de tipo entero:

            LinkedList<int> lista1 = new LinkedList<int>();

Insertamos tres nodos al principio de la lista:

            lista1.AddFirst(30);
            lista1.AddFirst(20);
            lista1.AddFirst(10);

Ahora insertamos un nodo al final de la lista mediante el método AddLast:

            lista1.AddLast(1);

Para imprimir la lista la clase LinkedList<T> tiene una propiedad llamada First que almacena la referencia al primer nodo de la lista (los nodos son de la clase LinkedListNode<int>), para avanzar al siguiente nodo accedemos a la propiedad Next que guarda la referencia del siguiente nodo:

        private static void ImprimirLista(LinkedList<int> lista)
        {
            LinkedListNode<int> reco = lista.First;
            while (reco!=null)
            {
                Console.Write(reco.Value + "-");
                reco = reco.Next;
            }
            Console.WriteLine();
        }

Podemos saber la cantidad de nodos almacenados en la lista consultando a la propiedad Count:

            Console.WriteLine("Cantidad de nodos de la lista:"+lista1.Count);

Para imprimir la lista del final al principio solo debemos obtener la referencia del último nodo y retrocedemos al nodo anterior mediante la propiedad Previous:

        private static void ImprimirUltimoAlPrimero(LinkedList<int> lista)
        {
            LinkedListNode<int> reco = lista.Last;
            while (reco!=null)
            {
                Console.Write(reco.Value + "-");
                reco = reco.Previous;
            }
            Console.WriteLine();
        }

Problema 2:

Confeccionar el juego de la serpiente (snake) utilizando un objeto de la clase LinkedList<T> para representar cada trozo de la misma.

Programa:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace Vibora
{
    public partial class Form1 : Form
    {
        private enum TDireccion { izquierda, derecha, arriba, abajo };
        private TDireccion Direccion { get; set; } = TDireccion.derecha;
        private LinkedList<Punto> lista1 = new LinkedList<Punto>();
        private Punto Fruta { get; set; } = new Punto(10, 10);
        private int Pendientes { get; set; } = 0;

        public Form1()
        {
            InitializeComponent();
            lista1.AddFirst(new Punto(0, 0));
        }

        private void timer1_Tick(object sender, EventArgs e)
        {
            if (Direccion == TDireccion.derecha)
                lista1.AddFirst(new Punto(lista1.First.Value.X + 1, lista1.First.Value.Y));
            if (Direccion == TDireccion.izquierda)
                lista1.AddFirst(new Punto(lista1.First.Value.X - 1, lista1.First.Value.Y));
            if (Direccion == TDireccion.arriba)
                lista1.AddFirst(new Punto(lista1.First.Value.X, lista1.First.Value.Y - 1));
            if (Direccion == TDireccion.abajo)
                lista1.AddFirst(new Punto(lista1.First.Value.X, lista1.First.Value.Y + 1));
            SaleMapa();
            SePisa();
            TocaFruta();
            RemoverCola();
            Invalidate();
        }

        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            foreach (var ele in lista1)
                e.Graphics.FillRectangle(new SolidBrush(Color.Red), ele.X * 10, ele.Y * 10, 9, 9);
            e.Graphics.FillRectangle(new SolidBrush(Color.Green), Fruta.X * 10, Fruta.Y * 10, 9, 9);
        }

        private void Form1_KeyDown(object sender, KeyEventArgs e)
        {
            if (e.KeyCode == Keys.Right)
                Direccion = TDireccion.derecha;
            if (e.KeyCode == Keys.Left)
                Direccion = TDireccion.izquierda;
            if (e.KeyCode == Keys.Up)
                Direccion = TDireccion.arriba;
            if (e.KeyCode == Keys.Down)
                Direccion = TDireccion.abajo;
        }

        private void TocaFruta()
        {
            if (lista1.First.Value.X == Fruta.X && lista1.First.Value.Y == Fruta.Y)
            {
                Pendientes = 5;
                Fruta.X = new Random().Next(1, 40);
                Fruta.Y = new Random().Next(1, 40);
            }
        }

        private void RemoverCola()
        {
            if (Pendientes == 0)
                lista1.RemoveLast();
            else
                Pendientes--;
        }

        private void SaleMapa()
        {
            if (lista1.First.Value.X == -1 || lista1.First.Value.Y == -1 ||
                lista1.First.Value.X == 40 || lista1.First.Value.Y == 40)
            {
                timer1.Enabled = false;
                MessageBox.Show("Perdio");
            }
        }

        private void SePisa()
        {
            foreach(var ele in lista1)
            {
                if (lista1.First.Value!=ele)
                    if (ele.X==lista1.First.Value.X &&
                        ele.Y==lista1.First.Value.Y)
                    {
                        timer1.Enabled = false;
                        MessageBox.Show("Perdio");
                    }
            }
        }


    }

    public class Punto
    {
        public int X { get; set; }
        public int Y { get; set; }
        public Punto(int x, int y)
        {
            X = x;
            Y = y;
        }
    }

}

Cuando lo ejecutemos tendremos un resultado similar a esto:

LinkedList<T>

Este proyecto lo puede descargar en un zip desde este enlace :Vibora.zip

Analicemos un poco nuestro problema, primero debemos definir un Timer para que avance la serpiente varias veces por segundo:

Timer

Definimos que el Timer se dispare cada 100 milisegundos y lo activamos con el valor true en la propiedad Enabled.

Definimos un atributo de tipo LinkedList que almacenará cada trozo de la víbora. Cada trozo son de tipo Punto que almacena la coordenada X e Y del segmento:

        private LinkedList<Punto> lista1 = new LinkedList<Punto>();

Como podemos ver la clase Punto tiene dos propiedades:

    public class Punto
    {
        public int X { get; set; }
        public int Y { get; set; }
        public Punto(int x, int y)
        {
            X = x;
            Y = y;
        }
    }

Definimos una propiedad llamada Direccion de tipo TDireccion que almacena cual es la dirección actual de la víbora (por defecto indicamos que la dirección es la 'derecha'):

        private enum TDireccion { izquierda, derecha, arriba, abajo };
        private TDireccion Direccion { get; set; } = TDireccion.derecha;

Creamos el tipo de dato enum para que nuestro programa sea más legible cuando necesitemos saber la dirección actual de la víbora.

La propiedad fruta almacena la coordenada donde aparece la primera fruta que puede comer la víbora (la primera fruta aparece en la coordenada 10,10):

        private Punto Fruta { get; set; } = new Punto(10, 10);

Por último la propiedad Pendientes representa cuantos segmentos debemos agregarle a la víbora cuando coma una fruta:

        private int Pendientes { get; set; } = 0;

En el constructor agregamos el primer segmento a la víbora indicando que arranca en la coordenada 0,0:

        public Form1()
        {
            InitializeComponent();
            lista1.AddFirst(new Punto(0, 0));
        }

El método timer1_Tick se dispara cada 100 milisegundos y lo primero que hacemos es verificar cual es la dirección que tiene actualmente la víbora y según este valor añadimos un nodo al LinkedList al principio.
También tenemos que controlar si pierde llamando a los métodos: SaleMapa y SePisa. Verificamos si come la fruta llamando a TocaFruta. Removemos la cola de la víbora llamando RemoverCola y repintamos la pantalla llamando al método Invalidate:

        private void timer1_Tick(object sender, EventArgs e)
        {
            if (Direccion == TDireccion.derecha)
                lista1.AddFirst(new Punto(lista1.First.Value.X + 1, lista1.First.Value.Y));
            if (Direccion == TDireccion.izquierda)
                lista1.AddFirst(new Punto(lista1.First.Value.X - 1, lista1.First.Value.Y));
            if (Direccion == TDireccion.arriba)
                lista1.AddFirst(new Punto(lista1.First.Value.X, lista1.First.Value.Y - 1));
            if (Direccion == TDireccion.abajo)
                lista1.AddFirst(new Punto(lista1.First.Value.X, lista1.First.Value.Y + 1));
            SaleMapa();
            SePisa();
            TocaFruta();
            RemoverCola();
            Invalidate();
        }

El método Form1_KeyDown se dispara cuando el operador presiona alguna tecla del teclado y en la misma verificamos cual de las teclas de flechas presionó. Cambiamos el valor de la propiedad Direccion por el valor respectivo:

        private void Form1_KeyDown(object sender, KeyEventArgs e)
        {
            if (e.KeyCode == Keys.Right)
                Direccion = TDireccion.derecha;
            if (e.KeyCode == Keys.Left)
                Direccion = TDireccion.izquierda;
            if (e.KeyCode == Keys.Up)
                Direccion = TDireccion.arriba;
            if (e.KeyCode == Keys.Down)
                Direccion = TDireccion.abajo;
        }

El método Form1_Paint se ejecuta cuando aparece el Form en pantalla y cada vez que se llama al método Invalidate. Aquí dibujamos todos los segmentos de la víbora y también dibujamos la fruta:

        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            foreach (var ele in lista1)
                e.Graphics.FillRectangle(new SolidBrush(Color.Red), ele.X * 10, ele.Y * 10, 9, 9);
            e.Graphics.FillRectangle(new SolidBrush(Color.Green), Fruta.X * 10, Fruta.Y * 10, 9, 9);
        }

En el método TocaFruta verificamos si la cabeza de la víbora (que está representada por el primer nodo del LinkedList) coincide con las coordenadas de la fruta, en el caso de coincidir iniciamos la propiedad Pendientes con el valor 5 (indica que se agregaran 5 segmentos a la víbora) y generamos otra coordenada aleatoria para la fruta:

        private void TocaFruta()
        {
            if (lista1.First.Value.X == Fruta.X && lista1.First.Value.Y == Fruta.Y)
            {
                Pendientes = 5;
                Fruta.X = new Random().Next(1, 40);
                Fruta.Y = new Random().Next(1, 40);
            }
        }

Cada vez que se dispara el Timer agregamos un nodo a la lista al principio y borramos el último, con esto logramos que se desplace la víbora. Si la propiedad Pendientes es cero se borra el nodo en caso que la propiedad sea distinta a cero dejamos el nodo del final con lo que logramos que la víbora crezca en un segmento (cada vez que come una fruta crece 5 segmentos):

        private void RemoverCola()
        {
            if (Pendientes == 0)
                lista1.RemoveLast();
            else
                Pendientes--;
        }

El método SaleMapa se ejecuta cada vez que se dispara el Timer y controlamos si la cabeza de la víbora sale del área (el área permitida son las coordenadas en X de 0 a 39 y en Y de 0 a 39):

        private void SaleMapa()
        {
            if (lista1.First.Value.X == -1 || lista1.First.Value.Y == -1 ||
                lista1.First.Value.X == 40 || lista1.First.Value.Y == 40)
            {
                timer1.Enabled = false;
                MessageBox.Show("Perdio");
            }
        }

Por último para controlar si la víbora se pisa a si misma verificamos si la cabeza de la víbora coincide con la coordenada de otro segmento:

        private void SePisa()
        {
            foreach(var ele in lista1)
            {
                if (lista1.First.Value!=ele)
                    if (ele.X==lista1.First.Value.X &&
                        ele.Y==lista1.First.Value.Y)
                    {
                        timer1.Enabled = false;
                        MessageBox.Show("Perdio");
                    }
            }
        }

Retornar