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

Ir abajo

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

Mensaje  Admin el Jue Oct 13, 2011 12:21 pm

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.
avatar
Admin
Admin

Cantidad de envíos : 94
Fecha de inscripción : 28/08/2009

http://www.jtentor.com.ar

Volver arriba Ir abajo

Volver arriba

- Temas similares

 
Permisos de este foro:
No puedes responder a temas en este foro.