Lista dinâmica duplamente encadeada – C#

Autor: Emerson Shigueo Sugimoto 08/03/2014

Criei este projeto para resolver um problema que envolvia LinquedList (C#), que por definição é uma lista duplamente ligada. O objetivo do projeto é o desenvolvimento de uma biblioteca de objetos genéricos armazenados em uma lista duplamente ligada com inserção ordenada.

Exemplo de Entrada:

LinkedList lqDt = new LinkedList();
UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now));
UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now.AddDays(-1)));
UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now.AddDays(-4)));
UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now.AddDays(10)));

txt1.Text = UtilLinquedList.Print(lqDt) + Environment.NewLine + Environment.NewLine;

LinkedList lqInt = new LinkedList();
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(3));
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(20));
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(14));
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(-7));
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(1));
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(3));

txt1.Text += UtilLinquedList.Print(lqInt) + Environment.NewLine + Environment.NewLine;

LinkedList lqPessoa = new LinkedList();
UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Emerson", Idade = 10 }));
UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Maria", Idade = 7 }));
UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Alana", Idade = 20 }));
UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Denise", Idade = 20 }));
UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Kurtis", Idade = 15 }));
UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Paula", Idade = 9 }));
UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Gogh", Idade = 7 }));
UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Four", Idade = 4 }));

txt1.Text += UtilLinquedList.Print(lqPessoa) + Environment.NewLine + Environment.NewLine;

Exemplo de saída do sistema:

Estrutura do projeto:

Classe AbstLinquedList

A classe AbstLinquedList representa um item da lista duplamente encadeada. Os métodos necessários a ordenação dos itens na lista duplamente encadeada são:

• CompareTo
• AbsDiff
• int operator -

using System;

namespace DoubleLinquedList.code.linqued {

    /// <summary>
    /// Classe abstrata - representa um item da linquedlist
    /// 
    /// Desenvolvido por:
    /// Emerson Shigueo Sugimoto 08/03/2014
    /// </summary>
    public abstract class AbstLinquedList : IComparable {
        public abstract int CompareTo(object obj);

        public abstract int AbsDiff(AbstLinquedList obj);
        public static int operator -(AbstLinquedList x, AbstLinquedList y) {
            return x.AbsDiff(y);
        }

        public abstract override string ToString();
    }

}

O método CompareTo é responsável por comparar dois objetos AbstLinquedList (estude a interface IComparable – http://msdn.microsoft.com/pt-br/library/system.icomparable(v=vs.110).aspx). Sendo que se a função retornar 0, os objetos são “iguais”, se retornar -1, o obj é “menor” do que o objeto da classe AbstLinquedList e se retorna 1, é “maior”. Parece ser confuso para quem está aprendendo, mais é um conceito extremamente simples e amplamente utilizado.

Uso os termos comparativos entre aspas: “maior”, “menor” e “iguais” de forma genérica, pois para dois números, objetos do tipo DateTime, etc., é compreensível dizer que um número é maior, menor ou igual a outro, porém para objetos mais complexos, como um struct ou classe que representa uma entidade, é estranho pensar que uma classe é “maior”, “menor” ou “igual” (não pense no termo Equals, mais em igualdade númerica) que outra. Na verdade o “maior”, “menor” ou “igual” se aplica a função de comparação que você vai usar. Como exemplo este artigo define a classe Pessoa, com propriedades Nome (string) e Idade (int), para comparar dois objetos Pessoa eu uso o atributo Idade.

O método AbsDiff é responsável por realizar a diferença absoluta (Math.Abs) entre dois objetos do tipo AbstLinquedList. O número absoluto de uma diferença numérica pode ser traduzido pela função ternária:

int a = 3;
int b = 7;
return a > b ? a - b : b - a;

A sobrecarga do operador ‘-’ é feita pela função:

        public static int operator -(AbstLinquedList x, AbstLinquedList y) {
            return x.AbsDiff(y);
        }

O método ToString() é usado para imprimir o objeto AbstLinquedList através do método Print(LinkedList lq) da classe UtilLinquedList.

Classe UtilLinquedList

É nesta classe que a inserção de forma ordenada é feita.

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

namespace DoubleLinquedList.code.linqued {

    /// <summary>
    /// Funções úteis a linked list
    /// 
    /// Desenvolvido por:
    /// Emerson Shigueo Sugimoto 08/03/2014
    /// </summary>
    public static class UtilLinquedList {

        /// <summary>
        /// Adiciona os itens na Linqued List de forma ordenada
        /// </summary>
        /// <param name="lq">LinkedList</param>
        /// <param name="valor">AbstLinquedList</param>
        public static void AddLinkedList(ref LinkedList<AbstLinquedList> lq, AbstLinquedList valor) {
            if (lq == null) { lq = new LinkedList<AbstLinquedList>(); }
            if (lq.Count <= 0) { lq.AddFirst(valor); return; }

            LinkedListNode<AbstLinquedList> first = lq.First;
            LinkedListNode<AbstLinquedList> last = lq.Last;

            if (first.Value.CompareTo(valor) == 1) {
                lq.AddFirst(valor);
                return;
            }
            if (last.Value.CompareTo(valor) == -1) {
                lq.AddLast(valor);
                return;
            }

            //esta mais próximo do inicio ou do fim ?
            int diffInicio = first.Value - valor;
            int diffFim = last.Value - valor;

            if (diffInicio <= diffFim) { //mais próximo do início
                while (first.Next.Value.CompareTo(valor) == -1) {
                    first = lq.Find(first.Value).Next;
                }
                lq.AddBefore(first.Next, valor);
            } else { //mais próximo do fim
                while (last.Previous.Value.CompareTo(valor) == 1) {
                    last = lq.Find(last.Value).Previous;
                }
                lq.AddAfter(last.Previous, valor);
            }
        }

        /// <summary>
        /// Imprime objetos AbstLinquedList, observe a sobrecarga ToString()
        /// </summary>
        /// <param name="lq">LinkedList</param>
        /// <returns></returns>
        public static string Print(LinkedList<AbstLinquedList> lq) {
            StringBuilder rt = new StringBuilder();
            foreach (AbstLinquedList nd in lq) {
                if (rt.Length > 0) { rt.Append(", "); }
                rt.Append(nd.ToString());
            }
            return rt.ToString();
        }

    }
}
/*
-----------------------
    Exemplo de uso:
-----------------------

    LinkedList<AbstLinquedList> lqDt = new LinkedList<AbstLinquedList>();
    UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now));
    UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now.AddDays(-1)));
    UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now.AddDays(-4)));
    UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now.AddDays(10)));

    txt1.Text = UtilLinquedList.Print(lqDt) + Environment.NewLine + Environment.NewLine;

    LinkedList<AbstLinquedList> lqInt = new LinkedList<AbstLinquedList>();
    UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(3));
    UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(20));
    UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(14));
    UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(-7));
    UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(1));
    UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(3));

    txt1.Text += UtilLinquedList.Print(lqInt) + Environment.NewLine + Environment.NewLine;

    LinkedList<AbstLinquedList> lqPessoa = new LinkedList<AbstLinquedList>();
    UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Emerson", Idade = 10 }));
    UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Maria", Idade = 7 }));
    UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Alana", Idade = 20 }));
    UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Denise", Idade = 20 }));
    UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Kurtis", Idade = 15 }));
    UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Paula", Idade = 9 }));
    UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Gogh", Idade = 7 }));
    UtilLinquedList.AddLinkedList(ref lqPessoa, new LQPessoa(new Pessoa() { Nome = "Four", Idade = 4 }));

    txt1.Text += UtilLinquedList.Print(lqPessoa) + Environment.NewLine + Environment.NewLine; 
*/

O método Print retorna a sobrecarga ToString() dos objetos AbstLinquedList.

O método AddLinkedList(ref LinkedList lq, AbstLinquedList valor) adiciona de forma ordenada os objetos AbstLinquedList na lista LinkedList lq. A palavra chave ref indica que a lista será passada por referência, pode-se ler, de forma simplista, que um ponteiro para a variável será passado. Descrição do método:

Caso a lista seja nula, crie:

if (lq == null) { lq = new LinkedList(); }

Se está vazia, adicione o objeto:

if (lq.Count <= 0) { lq.AddFirst(valor); return; }

Primeiro e último itens da lista:

LinkedListNode first = lq.First;
LinkedListNode last = lq.Last;

Se o primeiro item da lista é “maior” do que o item a ser adicionado, significa que o item a ser adicionado será o primeiro item.

            if (first.Value.CompareTo(valor) == 1) {
                lq.AddFirst(valor);
                return;
            }

Se o último item da lista é “menor” do que o item a ser adicionado, significa que o item a ser adicionado será o último item.

            if (last.Value.CompareTo(valor) == -1) {
                lq.AddLast(valor);
                return;
            }

Neste ponto do código, eu preciso “varrer” a lista encadeada até encontrar o ponto de inserção. Sabendo que eu tenho o primeiro item e o último item da lista, eu preciso saber a distância do item em relação ao primeiro item e em relação ao último item, se ele estiver mais próximo do início, eu “varro” a lista de frente para trás, se ele estiver mais próximo do fim da lista, eu “varro” a lista de trás para frente.
Uso o termo chulo “varrer” para explicar de forma direta a intenção de percorrer os itens da lista.

//esta mais próximo do inicio ou do fim ?
int diffInicio = first.Value - valor;
int diffFim = last.Value - valor;

Se o item está mais próximo do início ou equidistante (diffInicio <= diffFim):

if (diffInicio <= diffFim) { //mais próximo do início

Enquanto os itens da lista forem “menores” do que o item a ser adicionado, vá para o próximo.

                while (first.Next.Value.CompareTo(valor) == -1) {
                    first = lq.Find(first.Value).Next;
                }

Adiciona o item na sequência da lista encadedada:

                lq.AddBefore(first.Next, valor);
            }

Se o ponto está mais próximo do final:

else { //mais próximo do fim

Enquanto os itens da lista forem “maiores” do que o item a ser adicionado, vá para o anterior.

                while (last.Previous.Value.CompareTo(valor) == 1) {
                    last = lq.Find(last.Value).Previous;
                }

Adiciona o item na sequência da lista encadedada:

                lq.AddAfter(last.Previous, valor);
            }

Classe LQInt

Exemplo de implementação da classe AbstLinquedList.

using System;

namespace DoubleLinquedList.code.linqued.implement {

    /// <summary>
    /// Exemplo de implementação de AbstLinquedList para objetos do tipo int
    /// 
    /// Desenvolvido por:
    /// Emerson Shigueo Sugimoto 08/03/2014
    /// </summary>
    public class LQInt : AbstLinquedList {

        public int Valor { get; set; }

        public LQInt(int valor) {
            Valor = valor;
        }

        public override int CompareTo(object obj) {
            if (obj == null) { return 1; }
            return ((LQInt)obj).Valor > Valor ? -1 : 1;
        }

        public override string ToString() {
            return Valor.ToString();
        }

        public override int AbsDiff(AbstLinquedList obj) {
            return Math.Abs(Valor - ((LQInt)obj).Valor);
        }
    }

}

A implementação é feita para objetos do tipo int.
A propriedade Valor:

public int Valor { get; set; }

É a base dos métodos da classe. CompareTo é dado por:

return ((LQInt)obj).Valor > Valor ? -1 : 1;

E AbsDiff:

return Math.Abs(Valor - ((LQInt)obj).Valor);

Exemplo de uso:

LinkedList lqInt = new LinkedList();
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(3));
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(20));
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(14));
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(-7));
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(1));
UtilLinquedList.AddLinkedList(ref lqInt, new LQInt(3));

txt1.Text += UtilLinquedList.Print(lqInt) + Environment.NewLine + Environment.NewLine;

Classe LQData

using System;

namespace DoubleLinquedList.code.linqued.implement {

    /// <summary>
    /// Exemplo de implementação de AbstLinquedList para objetos do tipo DateTime
    /// 
    /// Desenvolvido por:
    /// Emerson Shigueo Sugimoto 08/03/2014
    /// </summary>
    public class LQData : AbstLinquedList {

        public DateTime Valor { get; set; }

        public LQData(DateTime valor) {
            Valor = valor;
        }

        public override int CompareTo(object obj) {
            if (obj == null) { return 1; }
            return Valor.CompareTo(((LQData)obj).Valor);
        }

        public override string ToString() {
            return Valor.ToString("dd/MM/yyyy dd:mm:ss.fff");
        }

        public override int AbsDiff(AbstLinquedList obj) {
            return Math.Abs((Valor - ((LQData)obj).Valor).Milliseconds);
        }
    }

}

Exemplo de uso:

LinkedList lqDt = new LinkedList();
UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now));
UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now.AddDays(-1)));
UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now.AddDays(-4)));
UtilLinquedList.AddLinkedList(ref lqDt, new LQData(DateTime.Now.AddDays(10)));

txt1.Text = UtilLinquedList.Print(lqDt) + Environment.NewLine + Environment.NewLine;

Classe Pessoa

Criado para representar a ordenação de entidades.

namespace DoubleLinquedList.code.entidades {

    /// <summary>
    /// Classe Pessoa
    /// 
    /// Desenvolvido por:
    /// Emerson Shigueo Sugimoto 08/03/2014
    /// </summary>
    public class Pessoa {

        public string Nome { get; set; }
        public int Idade { get; set; }

        //.. etc

        public override string ToString() {
            return Nome + " " + Idade;
        }

    }

}

Classe LQPessoa

Ordena objetos do tipo Pessoa.

using DoubleLinquedList.code.entidades;
using System;

namespace DoubleLinquedList.code.linqued.implement {

    /// <summary>
    /// Exemplo de implementação de AbstLinquedList para objetos do tipo Pessoa
    /// 
    /// Desenvolvido por:
    /// Emerson Shigueo Sugimoto 08/03/2014
    /// </summary>
    public class LQPessoa : AbstLinquedList {
        public Pessoa Valor { get; set; }

        public LQPessoa(Pessoa valor) {
            Valor = valor;
        }

        /// <summary>
        /// Observe a sobrecarga, aqui compara-se a idade.
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public override int CompareTo(object obj) {
            if (obj == null) { return 1; }
            return ((LQPessoa)obj).Valor.Idade > Valor.Idade ? -1 : 1;
        }

        /// <summary>
        /// Sobrecarga usada no método UtilLinquedList.Print
        /// </summary>
        /// <returns></returns>
        public override string ToString() {
            return Valor.ToString();
        }

        public override int AbsDiff(AbstLinquedList obj) {
            return Math.Abs(Valor.Idade - ((LQPessoa)obj).Valor.Idade);
        }

    }

}

Esta foi a solução genérica que encontrei para ordenar objetos em uma estrutura de linkedlist. Possui sugestões ou melhorias? favor comentar no artigo.

O download do código fonte pode ser feito em:

https://mega.co.nz/#!EVIR1AKA!iUZcrrqrb4TKX9gmOFZsUGdol__ZfmyBtMoUSTULILQ

Nome(obrigatório)

E-mail(obrigatório)

Site

Comentário(obrigatório)

Enviar

Δ