EdD - Clase List (compleja pero con mucho comportamiento)

El diagrama de clases en este caso muestra una lista con acceso al principo y final de la misma y en la que cada nodo puede acceder al elemento anterior y siguiente.


En este caso la clase List<T> implementa (se comprometa a codificar) la especificación de la interface IEnumerable; esta interface es la que permite utilizar la sentencia foreach( ... ) y nos permitirá acceder a los elementos de lista sin saber su conformación interna.
También se observa la implementación del mecanismo de acceso mediante subíndices a los elementos que se almacenan en la lista, este código es un ejemplo siempre se debe evaluar la performance de utilizar o no este mecanismo de acceso.

El código de la clase Node<T> es el siguiente:

Código:


namespace E07
{
  /// <summary>
  /// Clase para representar un nodo de listas doblemente enlazadas
  /// </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;
    /// <summary>
    /// Mantiene el elace al nodo anterior
    /// </summary>
    private Node<ELEMENT> prev;
    #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;
      this.Prev = 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 elemento del nodo
    /// y el valor de ambos enlaces siguiente nodo
    /// </summary>
    /// <param name="item">Elemento en el nodo</param>
    /// <param name="next">Enlace al siguiente nodo</param>
    /// <param name="prev">Enlace al nodo anterior</param>
    public Node(ELEMENT item, Node<ELEMENT> next, Node<ELEMENT> prev)
      : this()
    {
      this.Item = item;
      this.Next = next;
      this.Prev = prev;
    }
    /// <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;
    }
    /// <summary>
    /// Constructor especializado, permite fijar el enlace al
    /// siguiente nodo y al nodo anterior
    /// </summary>
    /// <param name="next">Enlace al siguiente nodo</param>
    /// <param name="prev">Enlace al nodo anterior</param>
    public Node(Node<ELEMENT> next, Node<ELEMENT> prev)
      : this()
    {
      this.Next = next;
      this.Prev = prev;
    }
    #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;
      }
    }
    /// <summary>
    /// Facilita el acceso al enlace al nodo anterior
    /// </summary>
    public Node<ELEMENT> Prev
    {
      get
      {
        return this.prev;
      }
      set
      {
        this.prev = value;
      }

    #endregion

    }
  }
}


El código que implementa la estructura de datos de List<T> es el siguiente:

Código:


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

namespace E07
{
  /// <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> : IEnumerable where ELEMENT : IComparable
  {
    #region Estructura interna
    /// <summary>
    /// Mantiene la cantidad de elementos dentro de la lista
    /// </summary>
    private int count;

    /// <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.count = 0;
      this.head = null;
      this.tail = null;
    }

    #endregion

    #region Propiedades
    /// <summary>
    /// Devuelve la cantidad de elementos dentro de la lista
    /// </summary>
    public int Count
    {
      get
      {
        return this.count;
      }
      protected set
      {
        this.count = value;
      }
    }
    /// <summary>
    /// Devuelve verdadero cuando la lista está vacía
    /// </summary>
    public bool IsEmpty
    {
      get
      {
        return this.head == null;
      }
    }
    /// <summary>
    /// Implementa el acceso a los elementos de la lista mediante
    /// un índice como si fuese un arreglo
    /// </summary>
    /// <param name="pos">Posición (base cero) dentro de la lista que se desea acceder</param>
    /// <returns>Objeto del tipo ELEMENT en la posición pos</returns>
    public ELEMENT this[int pos]
    {
      get
      {
        if (pos < 0)
        {
          throw new ArgumentException("Argumento inválido pos = " + pos.ToString());
        }
        Node<ELEMENT> skip = head;
        for (int i = 0; (skip != null) && (i < pos); ++i)
        {
          skip = skip.Next;
        }
        if (skip == null)
        {
          throw new ArgumentException("Argumento inválido pos = {0} mayor que la cantidad de elementos", pos.ToString());
        }
        return skip.Item;
      }
    }

    #endregion

    #region Comportamiento de la lista enlazada

    /// <summary>
    /// Agrega un elemento después de la posición indicada
    /// </summary>
    /// <param name="item">Elemento a agregar</param>
    /// <param name="pos">Posición a partir de la que se debe agregar</param>
    public void AddAfter(ELEMENT item, int pos)
    {
      if (IsEmpty || (pos < 0)) // esta vacía o la posición es negativa
      {
        AddToHead(item);
      }
      else
      {
        Node<ELEMENT> skip = head;
        for (int i = 0; (skip != null) && (i < pos); ++i)
        {
          skip = skip.Next;
        }
        if (skip == null) // llego al final
        {
          AddToTail(item);  // TODO: Confirmar con el cliente
        }
        else
        {
          Node<ELEMENT> temp = new Node<ELEMENT>(item);
          if (skip.Next != null)  // hay algo despues
          {
            temp.Next = skip.Next;
            skip.Next.Prev = temp;
          }
          skip.Next = temp;
          temp.Prev = skip;
          ++Count;
        }
      }
    }
    /// <summary>
    /// Agrega un elemento después de la posición indicada
    /// </summary>
    /// <param name="item">Elemento a agregar</param>
    /// <param name="pos">Posición a partir de la que se debe agregar</param>
    public void AddBefore(ELEMENT item, int pos)
    {
      if (IsEmpty || (pos < 1))
      {
        AddToHead(item);
      }
      else
      {
        Node<ELEMENT> skip = head;
        for (int i = 0; (skip != null) && (i < pos); ++i)
        {
          skip = skip.Next;
        }
        if (skip == null) // llego al final
        {
          AddToTail(item);
        }
        else
        {
          Node<ELEMENT> temp = new Node<ELEMENT>(item);
          if (skip.Prev != null)  // hay algo adelante
          {
            temp.Prev = skip.Prev;
            skip.Prev.Next = temp;
          }
          skip.Prev = temp;
          temp.Next = skip;
          ++Count;
        }
      }
    }
    /// <summary>
    /// Agrega un elemento en la lista ordenada
    /// </summary>
    /// <param name="item">Elemento a agregar</param>
    public void AddInOrder(ELEMENT item)
    {
      if (IsEmpty || (item.CompareTo(head.Item) < 0))
      {
        // item es menor que el primer elemento de la lista
        AddToHead(item);
      }
      else
      {
        Node<ELEMENT> skip = head;
        while ((skip != null) && (item.CompareTo(skip.Item) >= 0))
        {
          skip = skip.Next;
        }
        if (skip == null)
        {
          // item es mayor que todos los elementos de la lista
          AddToTail(item);
        }
        else
        {
          // item es menor que el elemento que esta en el nodo skip
          // se debe agregar el nuevo nodo antes
          Node<ELEMENT> temp = new Node<ELEMENT>(item);
          temp.Prev = skip.Prev;
          skip.Prev.Next = temp;
          temp.Next = skip;
          skip.Prev = temp;
          ++Count;
        }
      }
    }

    /// <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, null);
        tail = head;
      }
      else
      {
        Node<ELEMENT> temp = new Node<ELEMENT>(item, head, null);
        head.Prev = temp; // Ajusta el enlace hacia atras
        head = temp;
      }
      ++Count;
    }
    /// <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, null);
        tail = head;
      }
      else
      {
        tail.Next = new Node<ELEMENT>(item, null, tail);
        tail = tail.Next;
      }
      ++Count;
    }
    /// <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>
    /// Busca un elemento determinado en la lista, y devuelve la posición
    /// (base cero) en que se encuentra.
    /// </summary>
    /// <param name="item">Elemento a buscar</param>
    /// <returns>Posición (base cero) donde el elemento se encuentra en la lista</returns>
    public int Find(ELEMENT item)
    {
      int i = 0;
      for (Node<ELEMENT> temp = head; temp != null; temp = temp.Next, ++i)
      {
        if (temp.Item.Equals(item))
        {
          return i;
        }
      }
      return -1;

    }
    /// <summary>
    /// Extrae el elemento que se encuentra en la posición indicada
    /// </summary>
    /// <param name="pos">Posición donde se desea extraer el elemento</param>
    /// <returns>Objeto del tipo ELEMENT que se extrae</returns>
    public ELEMENT RemoveAt(int pos)
    {
      if (IsEmpty || (pos < 0) || (pos > Count))
      {
        throw new ArgumentException("Argumento fuera de los límites de la lista pos = " + pos.ToString());
      }
      Node<ELEMENT> skip = head;
      for (int i = 0; (skip != null) && (i < pos); ++i)
      {
        skip = skip.Next;
      }
      if (skip == null)
      {
        throw new Exception("Error inesperado en la posición pos = " + pos.ToString());
      }
      if (skip.Prev == null)  // es el primero
      {
        if (skip.Next == null)  // es el primero y último
        {
          head = tail = null;  // vaciar la lista
        }
        else
        {
          head = head.Next; // ajustar la cabeza
          head.Prev = null;
          skip.Next = null; // cancelar la referencia
        }
      }
      else
      {
        if (skip.Next == null)  // es el último
        {
          tail = tail.Prev; // ajustar la cola
          tail.Next = null;
          skip.Prev = null; // cancelar la referencia
        }
        else
        {
          // estamos en el medio de la lista
          skip.Prev.Next = skip.Next; // ajustar los enlaces
          skip.Next.Prev = skip.Prev;
          skip.Next = skip.Prev = null; // cancelar las referencias
        }
      }
      --Count;
      return skip.Item;
    }
    /// <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;
      }
      else
      {
        head.Prev = null; // Ya no hay nodo anterior
      }
      temp.Next = null; // Asegurarse de anular la referencia
      --Count;
      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 = tail;
      if (temp.Prev == null)  // Es el único
      {
        head = null;
        tail = null;
      }
      else
      {
        tail = tail.Prev; // Retroceder la cola de la lista
        tail.Next = null; // Ajusta el enlace al último nodo
        temp.Prev = null; // Cancelar el enlace al anterior (por las dudas)
      }
      --Count;
      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

    #region IEnumerable Members

    /// <summary>
    /// Implementa el contrato indicado en IEnumerable
    /// </summary>
    /// <returns>Un objeto IEnumerator que permite recorrer la lista</returns>
    IEnumerator IEnumerable.GetEnumerator()
    {
      return MyEnumerator();
    }
    /// <summary>
    /// Implementa un IEnumerator específico para recorrer la lista.
    /// </summary>
    /// <returns>Objeto del tipo IEnumerator que recorre la lista</returns>
    private IEnumerator MyEnumerator()
    {
      for (Node<ELEMENT> skip = head; skip != null; skip = skip.Next)
      {
        yield return skip.Item;
      }
    }
    #endregion

  }
}


Como se puede ver, en la declaración de la clase se exige que los objetos del tipo ELEMENT implementen la interface IComparable; esto es necesario para poder implementar el mecanismo de agregar en orden, los objetos deben saber compararse unos con otros y eso esta estandarizado en el método CompareTo(...)
Utilizar esta implementación de lista con objetos comunes como char, int, double, string no presenta ningún inconveniente dado que todos estos objetos implementan la interface IComparable; pero al tratar de crear lista de objetos complejos como ser un Libro, Persona, Avion es necesario que dichas clases implementen el método CompareTo(...) o sea esos objetos deben saber compararse.

En la implementación del GetEnumerator() se utiliza un método interno, esto muestra la posibilidad de contar con varias formas de recorrer o enumerar los elementos de la lista, pudiendo en consecuencia determinar mediante una propiedad cuál de esos métodos es el que se utilizará.