Estruturas de Dados em C#: Part 1 :: Lista Simplesmente Encadeada

Publicado: 03/11/2004 em IntoSpaces
Olá Pessoal!
Pretendo iniciar uma série de Posts mostrando como pode ser feita a implementação de estruturas de dados avançadas.

Para quem aprende estruturas de dados em uma liguagem estruturada, a tradução da estrutura para o Mundo OO pode ser traumática, porém quero mostrar aqui para vocês que a forma de se raciocinar em OO é bem mais interessante e o trabalho é facilitado.

A primeira estrutura que estarei mostrando é a estrutura de uma Lista Simplesmente Encadeada.
Ela consiste em em uma "alocação sequêncial de memória", em liguangens não OO utilizaríamos ponteiros para fazer essa alocação dinânica, porém em nosso cenário isso não é necessário já que existe uma flexibilidade muito grande entre os tipos.

Mostrarei a estrutura e os algoritmos aqui, sem comentários no código, para quem desejar baixar os códigos comentados e a solução inteira para o Visual Studio, incluindo uma aplicação Console para testar a estrutura http://www.shindesign.net/thespoke/pt-br/03-11-2004/ListaSimplesmenteEncadeada.zip

Vamos ao código.

Primeiro Criamos uma Classe Node, ela será o nosso trunfo do alocamento dinâmico. Contem 2 campos fundamentais, Info para receber um objeto e Next para refernciar o próximo objeto da nossa lista.

public class Node
{
   public Node(object info, Node next)
   {
      this.Info = info;
      Next = next;
   }

   public Node(object info)
   {
        Info = info;
        Next = null;
   }

   public
object Info = null;
  
public Node Next = null;
}

Utilizei 2 contrutores diferentes, eles nos ajudarão na codificação mais adiante.
A próxima classe a ser criada é a classe Nodes, que é uma coleção de objetos Node, ela é muito útil para percorrer a lista toda. Esse tipo de Classe está presente nas coleções que conhecemos nativamente no .NET Framework, como por exemplo os "Items" de um ComboBox. Ela funciona como um indexador. Foi implementada, mas não utlizaremos todos os seus recursos.

public
class Nodes : CollectionBase
{
   public Node this[int item]
   {get{return this.GetNode(item);}}

   public void Add(Node node)
   {
         List.Add(node);
   }

   public bool Remove(int index)
   {
        if (index > Count – 1 || index < 0)
           return false;
        else
      
{
          List.RemoveAt(index);
          return true;
        }
    }

   private Node GetNode(int Index)
   {
      return (Node) List[Index];
   }

}

Essa é uma implementação padrão de uma coleção, sem muitos comentários pois não é o nosso foco hoje.
Agora vamos à classe que fará todo o trabalho pra gente, nela temos diversos métodos para resolver o nosso problema de alocação dinâmica baseada em Lista Encadeada.
Com ela executamos os procedimentos básicos para manipulação dos dados:

Insere no início da lista;
Insere no final da lista;
Remove do início da lista;
Remove do final da lista;
Percorre e lista todos os objetos da lista;
Busca um objeto na lista;
Limpa a lista;

De forma simples trabalhando as Classes Node e Nodes conseguimos armazenar n objetos em forma de uma lista sequêncial sem um limite.
Com esse algoritmo otimizado podemos simplificar o trabalho e diminuir overloads em nossas aplicações para realizar determinadas tarefas.

public
class ListaSimples
{
   private Node Node;
   
   public void InsereInicio(object info)
   {
         if(Node == null)
            Node = new Node(info);
         else
            Node = new Node(info,Node);
   }

   public Node RemoveInicio()
   {
         Node no = null;
         if(Node != null)
         {
             no = Node;
             Node = Node.Next;
         }
         return no;
   }

   public void InsereFinal(object info)
   {
        
if(Node == null)
            Node = new Node(info);
         else
         {
             Node nodeAux = Node;
             while(nodeAux.Next != null)
             {
                nodeAux = nodeAux.Next;
             }
             nodeAux.Next = new Node(info);
          }
   }

   public Node RemoveFinal()
   {
         Node no = null;
         Node nodeAux;
         Node nodeAux2 = new Node(null);
         if(Node != null)
         {
             nodeAux = Node;
             while(nodeAux.Next != null)
             {
                 nodeAux2 = nodeAux;
                 nodeAux = nodeAux.Next;
              }
            
              no = nodeAux;
              
nodeAux = null;
              nodeAux2.Next = null;
           }
           return no;
   }

   public Nodes Percorre()
   {
          Node nodeAux = Node;
          Nodes nodes = new Nodes();
          while(nodeAux != null)
          {
              nodes.Add(nodeAux);
              nodeAux = nodeAux.Next;
          }
          return nodes;
   }

   public bool Busca(object info)
   {
         bool exists = false;
         if(Node != null)
         {
             Node nodeAux = Node;
             while(nodeAux != null)
             {
                 if(nodeAux.Info == info)
                 {
                     exists = true;
                     break;
                  }
                  nodeAux = nodeAux.Next;
               }
          }
          return exists;
   }

   public void Clear()
   {
        Node = null;
   }

}

Essa implementação para C# é muito limpa, se comparada a uma linguagem estruturada. Com ela o trabalho fica muito mais intuitivo e é uma alternativa para resolvermos problemas críticos.
Espero que ajude vocês, novamente quem quiser os arquivos da solução completa, inclusive com uma Aplicação Console para testar a estrutura http://www.shindesign.net/thespoke/pt-br/03-11-2004/ListaSimplesmenteEncadeada.zip

Breve continuarei a série com outras estruturas de dados mais avançadas.
[]’s
Shinji

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s