EdD - Clase List (primer implementación, la más simple pero la menos eficiente)

El siguiente diagrama muestra la relación entre los objetos Node<T> y List<T> así como sus Propiedades y Métodos:


El código que necesitarán para los ejercicios es el siguiente:

Código:


namespace E01
{
  /// <summary>
  /// Clase para representar un nodo de listas enlazdas
  /// </summary>
  /// <typeparam name="ELEMENT">Tipo de dato del elemento</typeparam>
  internal class Node<ELEMENT>
  {

    #region Estructura Interna
    /// <summary>
    /// Mantiene el elemento en el nodo
    /// </summary>
    private ELEMENT item;
    /// <summary>
    /// Mantiene el enlace al siguiente nodo
    /// </summary>
    private Node<ELEMENT> next;
    #endregion

    #region Constructores
    /// <summary>
    /// Constructor por defecto, inicializa los campos de la estructura
    /// interna en valores por defecto
    /// </summary>
    public Node()
    {
      this.item = default(ELEMENT);
      this.next = null;
    }
    /// <summary>
    /// Constructor especializado, permite fijar el elemento del nodo
    /// </summary>
    /// <param name="item">Elemento en el nodo</param>
    public Node(ELEMENT item)
      : this()
    {
      this.item = item;
    }
    /// <summary>
    /// Constructor especializado, permite fijar el elemento del nodo
    /// y el valor del enlace al siguiente nodo
    /// </summary>
    /// <param name="item">Elemento en el nodo</param>
    /// <param name="next">Enlace al siguiente nodo</param>
    public Node(ELEMENT item, Node<ELEMENT> next)
      : this()
    {
      this.item = item;
      this.next = next;
    }
    /// <summary>
    /// Constructor especializado, permite fijar el enlace al
    /// siguiente nodo
    /// </summary>
    /// <param name="next">Enlace al siguiente nodo</param>
    public Node(Node<ELEMENT> next)
      : this()
    {
      this.next = next;
    }
    #endregion

    #region Propiedades Getters and Setters
    /// <summary>
    /// Facililta el acceso al elemento en el nodo
    /// </summary>
    public ELEMENT Item
    {
      get { return this.item; }
      set { this.item = value; }
    }

    /// <summary>
    /// Facilita el acceso al enlace al siguiente nodo
    /// </summary>
    public Node<ELEMENT> Next
    {
      get { return this.next; }
      set { this.next = value; }

    #endregion
    }
  }
}


Esta es la implementación de la List<T> en modo simple, un enlace por nodo y un único acceso al principio de la lista.

Código:


using System;

namespace E01
{
  /// <summary>
  /// Implementación básica de lista enlazada
  /// </summary>
  /// <typeparam name="ELEMENT">Tipo de dato de elementos que se introduce en la lista</typeparam>
  public class List<ELEMENT>
  {
    #region Estructura interna
    /// <summary>
    /// Mantiene un punto de entrada a la lista
    /// </summary>
    private Node<ELEMENT> head;

    #endregion

    #region Constructores
    /// <summary>
    /// Constructor por defecto
    /// </summary>
    public List()
    {
      this.head = null;
    }

    #endregion

    #region Propiedades
    /// <summary>
    /// Devuelve verdadero cuando la lista está vacía
    /// </summary>
    public bool IsEmpty
    {
      get { return this.head == null; }
    }
    #endregion

    #region Comportamiento de la lista enlazada

    /// <summary>
    /// Agrega un elemento al principio de la lista
    /// </summary>
    /// <param name="item">Elemento a agregar</param>
    public void AddToHead(ELEMENT item)
    {
      if (head == null)
      {
        head = new Node<ELEMENT>(item, null);
      }
      else
      {
        Node<ELEMENT> temp = new Node<ELEMENT>(item, head);
        head = temp;
      }
    }
    /// <summary>
    /// Agrega un elemento al final de la lista
    /// </summary>
    /// <param name="item">Elemento a agregar</param>
    public void AddToTail(ELEMENT item)
    {
      if (head == null)
      {
        head = new Node<ELEMENT>(item, null);
      }
      else
      {
        Node<ELEMENT> temp = head;
        while (temp.Next != null)
        {
          temp = temp.Next;
        }
        temp.Next = new Node<ELEMENT>(item, null);
      }
    }
    /// <summary>
    /// Determina si un elemento determinado se encuentra en la lista
    /// </summary>
    /// <param name="item">Elemento a buscar</param>
    /// <returns>Verdadero si el elemento se encuentra en la lista</returns>
    public bool Contains(ELEMENT item)
    {
      for (Node<ELEMENT> temp = head; temp != null; temp = temp.Next)
      {
        if (temp.Item.Equals(item))
        {
          return true;
        }
      }
      return false;
    }
    /// <summary>
    /// Retira el elemento del principio de la lista
    /// </summary>
    /// <returns>Elemento retirado</returns>
    public ELEMENT RemoveFromHead()
    {
      if (IsEmpty)
      {
        throw new Exception("Lista vacía");
      }
      Node<ELEMENT> temp = head;
      head = head.Next; // Avanza la posición de head
      temp.Next = null; // Asegurarse de anular la referencia
      return temp.Item; // Devolver el elemento no el nodo
    }

    /// <summary>
    /// Retira el elemento al final de la lista
    /// </summary>
    /// <returns>Elemento retirado</returns>
    public ELEMENT RemoveFromTail()
    {
      if (IsEmpty)
      {
        throw new Exception("Lista vacía");
      }
      Node<ELEMENT> temp = head;
      if (temp.Next == null)
      {
        head = null;
      }
      else
      {
        Node<ELEMENT> skip = head;
        while (skip.Next.Next != null)
        {
          skip = skip.Next;
        }
        temp = skip.Next;
        skip.Next = null; // Cancelar el enlace al último nodo
      }
      return temp.Item;
    }

    #endregion

    #region Métodos heredados de object
    /// <summary>
    /// Representación del contenido de la lista
    /// </summary>
    /// <returns>Cadena con el contenido de la lista</returns>
    public override string ToString()
    {
      string s = "";
      for (Node<ELEMENT> temp = head; temp != null; temp = temp.Next)
      {
        s += "  " + temp.Item.ToString() + "\n";
      }
      return s;
    }
    #endregion
  }
}


NOTA: cuando copien y peguen este codigo en sus proyectos deben cuidar que el namespace sea el mismo al del proyecto, caso contrario se intentará utilizar la clase que viene en el Framework.