Continuando a série: ED’s, irei mostrar um algoritmo para criar uma Lista Encadeada, e em seguida, um exemplo de utilização.

Conforme a publicação sobre Pilha e Fila, farei a implementação em C#, caso queiram em alguma outra linguagem, é só entrar em contato.

Mas primeiro, é importante perceber alguns conceitos básicos sobre as Listas Encadeadas. Hoje, em C#, é possível criar Listas Genéricas tranqüilamente, basta inserir o seguinte código:

List< int > myList = new List< int >();

Isto torna possível a geração de uma lista fortemente tipada em C#, cujo elemento contido sempre será do tipo int.

Mas isto não vai ser aplicado em nosso caso, pois o foco está em como criar uma estrutura no mínimo parecida. É interessante entender-mos este funcionamento para ampliar nosso conhecimento sobre os objetos encapsulados em outro objeto (lista ou coleção) e o comportamento aplicado para simular uma lista/coleção de objetos. O comportamento é bastante semelhante ao desenho abaixo:

Bom, como dito acima, uma Lista Encadeada é formada por vários objetos encapsulados. Então, para dar início ao nosso raciocínio, vamos criar a Classe Nodo.

namespace ED
{
    public class Nodo
    {
        // A propriedade Objeto vai marcar o Objeto encapsulado neste Nodo
        public object Objeto { get; set; }
        // A propriedade ProximoNodo vai marcar o Nodo que sucede a posição deste Nodo
        public Nodo ProximoNodo { get; set; }
        // A propriedade Parent vai marcar o Nodo que antecede a posição deste Nodo
        public Nodo Parent { get; set; }
    }
}

Feito isto, agora vamos criar a Classe Lista para simular o comportamento desejado:

namespace ED
{
    public class Lista
    {
        private int _count = 0;

        public Nodo PrimeiroNodo { get; set; }
        public Nodo UltimoNodo { get; set; }

        public int Count
        {
            get { return this._count; }
        }

        public void Add(object obj)
        {
            Nodo nodo = new Nodo();
            nodo.Objeto = obj;

            if (PrimeiroNodo == null)
            {
                nodo.Parent = PrimeiroNodo;
                PrimeiroNodo = nodo;
            }
            else
            {
                nodo.Parent = UltimoNodo
                UltimoNodo.ProximoNodo = nodo;
            }

            UltimoNodo = nodo;
            this._count++;
        }

        public object Get(int indice)
        {
            Nodo nodo = PrimeiroNodo;
            bool encontrado = false;
            int i = 0;

            while (nodo != null)
            {
                if (i == indice)
                {
                    encontrado = true;
                    break;
                }

                nodo = nodo.ProximoNodo;
                i++;
            }

            return encontrado ? nodo.Objeto : null;
        }

        public void Set(int indice, object valor)
        {
            Nodo nodo = PrimeiroNodo;
            int i = 0;

            while (nodo != null)
            {
                if (i == indice)
                {
                    nodo.Objeto = valor;
                    break;
                }

                nodo = nodo.ProximoNodo;
                i++;
            }
        }

        public void Remove(int indice)
        {
            Nodo nodo = PrimeiroNodo;
            bool encontrado = false;
            int i = 0;

            while (nodo != null)
            {
                if (i == 0 && i == indice)
                {
                    nodo.Parente = PrimeiroNodo;
                    PrimeiroNodo = nodo.ProximoNodo;
                    this._count--;
                    break;
                }
                else if (i == indice)
                {
                    nodo.ProximoNodo.Parent = nodo.Parent;
                    nodo.Parent = nodo.ProximoNodo;
                    this._count--;
                    break;
                }

                nodo = nodo.ProximoNodo;
                i++;
            }
        }
    }
}

Exemplo

Para exemplo, vamos criar um sistema simples de inserir N dados randômicos e em seguida, fazer uma alteração, inclusão ou exclusão aleatórias:

using System;

namespace ED
{
    public class ExemploLista
    {
        public static void Main(string Args[])
        {
            Random r = new Random();
            Lista myList = new Lista();

            for (int i = 0; i != 100; i++)
                myList.Add(r.NextInt(50));

            for(int i = 0; i != myList.Count; i++)
            {
                int sort = r.NextInt(2);

                switch(sort)
                {
                    case 0: myList.Remove(i); break;
                    case 1: myList.Set(i, r.Random(50)); break;
                    case 2: Console.WriteLine(myList.Get(i)); break;
                }
            }
        }
    }
}

Então é isto. Nos próximos artigos da série ED’s, vou providenciar assuntos relacionados às metodologias de ordenação. Até lá!