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

En este caso vemos como el diagrama de clases muestra la existencia de dos puntos de acceso (referencias) en la estructura interna de la lista, una al principio de la lista y otra al final de la misma:


El código de la clase Node<T> es el mismo, de manera que solo se debe modificar la implemetación de List<T>:

Código:


using System;

namespace E04
{
  /// <summary>
  /// Implementación de lista enlazada con dos puntos de acceso
  /// </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 cabeza de lista
    /// </summary>
    private Node<ELEMENT> head;

    /// <summary>
    /// Mantiene un punto de entrada al último nodo de la lista
    /// </summary>
    private Node<ELEMENT> tail;

    #endregion

    #region Constructores
    /// <summary>
    /// Constructor por defecto
    /// </summary>
    public List()
    {
      this.head = null;
      this.tail = 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);
        tail = head;
      }
      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);
        tail = head;
      }
      else
      {
        tail.Next = new Node<ELEMENT>(item, null);
        tail = tail.Next;
      }
    }
    /// <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
      if (head == null) // Es el único elemento en la lista?
      {
        tail = null;
      }
      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;
        tail = null;
      }
      else
      {
        Node<ELEMENT> skip = head;
        while (skip.Next.Next != null)
        {
          skip = skip.Next;
        }
        tail = skip;  // Ajusta el enlace al último nodo
        temp = skip.Next;
        tail.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

  }
}


Cómo se dijo en teoría, esta implementación soluciona la mayoría de los problemas de performance de la lista enlazada. El único problema que persiste es remover el último, hace falta recorrer toda la lista para hacerlo, lo que presenta un tiempo de ejecución que tiene relación directa con la cantidad de elementos en la lista; lo que no es aceptable cuando hay muchos elementos.
Otro comportamiento, puede implementarse sobre esta versión codificando los métodos que hagan faltan.