Listas Estáticas, Ponteiros, Pilhas e Listas Encadeadas em C#

Lista Estática

Uma lista estática sequencial é uma coleção ordenada de componentes do mesmo tipo. O sucessor de um elemento ocupa posição física subsequente.

Vantagens

• Acesso direto indexado a qualquer elemento da lista
• Tempo constante para acessar o elemento i, dependendo somente do índice.

Desvantagens

• Movimentação quando um elemento é eliminado ou inserido
• Tamanho máximo pré-estimado

Quando usar

• Listas pequenas
• Inserção/remoção no fim da lista
• Tamanho máximo bem definido

Ponteiro

Um apontador ou ponteiro é um tipo de variável especial, cujo objetivo é armazenar um endereço da memória.

• &x retorna o endereço da variável x
• *p é o conteúdo do endereço p (Ex.: int * p;)

Pilhas Dinâmicas

As pilhas criadas utilizando-se apontadores são mais eficientes, pois não precisamos definir um limite. Cada elemento da pilha aponta para o anterior, utilizando para isso apontadores.

Cada elemento da pilha possui:

• Valor que deve ser empilhado.
• Apontador para o elemento anterior na pilha.

A base da pilha tem como elemento anterior o valor NULL.

Lista Simplesmente Encadeada

Em uma lista simplesmente encadeada, cada elemento contém um apontador que aponta para o elemento seguinte.

Importante: a ordem dos endereços não importa. O que importa é a ordem em que eles estão encadeados!

Lista Duplamente Encadeada

Diferença entre simples e dupla: na duplamente encadeada, cada elemento contém um segundo apontador que aponta para o elemento que o antecede.

Pilha Dinâmica com Objetos Encadeados

Classe Nodo

class Nodo
{
    private string valor;
    private Nodo anterior;

    // Valor que será armazenado
    public string Valor
    {
        get { return valor; }
        set { valor = value; }
    }

    // Endereço do nodo anterior na pilha
    public Nodo Anterior
    {
        get { return anterior; }
        set { anterior = value; }
    }
}

Classe Pilha

class Pilha
{
    // Representa o topo da pilha
    private Nodo topo = null;

    // Quantidade de elementos na pilha
    int quantidade = 0;

    public int Quantidade
    {
        get { return quantidade; }
    }

    // Método para empilhar strings
    public void Empilhar(string valor)
    {
        Nodo novoNodo = new Nodo();
        novoNodo.Valor = valor;
        novoNodo.Anterior = topo;
        topo = novoNodo;
        quantidade++;
    }

    // Desempilhar elementos da pilha
    public string Desempilhar()
    {
        if (quantidade == 0)
            throw new Exception("A pilha está vazia!");
        else
        {
            string retorno = topo.Valor;
            topo = topo.Anterior;
            quantidade--;
            return retorno;
        }
    }

    // Método para retornar o topo da pilha
    public string RetornaTopo()
    {
        if (quantidade == 0)
            throw new Exception("A pilha está vazia!");
        else
            return topo.Valor;
    }
}

Form1 (Pilha)

public partial class Form1 : Form
{
    Pilha pilha = new Pilha();

    public Form1()
    {
        InitializeComponent();
    }

    private void btnEmpilhar_Click(object sender, EventArgs e)
    {
        pilha.Empilhar(txtValor.Text);
        txtValor.Clear();
    }

    private void btnDesempilhar_Click(object sender, EventArgs e)
    {
        try
        {
            txtValor.Text = pilha.Desempilhar();
        }
        catch (Exception erro)
        {
            MessageBox.Show(erro.Message);
        }
    }

    private void btnTamanho_Click(object sender, EventArgs e)
    {
        MessageBox.Show(pilha.Quantidade.ToString());
    }

    private void btnRetornaTopo_Click(object sender, EventArgs e)
    {
        try
        {
            txtValor.Text = pilha.RetornaTopo();
        }
        catch (Exception erro)
        {
            MessageBox.Show(erro.Message);
        }
    }
}

Lista Duplamente Encadeada em C#

Classe ListaDup

public class ListaDup
{
    private Nodo primeiro;
    private Nodo ultimo;
    int quantidade = 0;

    public Nodo Localizar(string valor)
    {
        Nodo aux = primeiro;
        while (aux != null)
        {
            if (aux.Valor == valor)
                return aux;
            aux = aux.Proximo;
        }
        return null;
    }

    public void InsereDepoisDe(string oque, string depoisDeQue)
    {
        Nodo nodo = Localizar(depoisDeQue);

        if (nodo == null)
            throw new Exception("O valor [ " + depoisDeQue + " ] não existe na lista!");

        Nodo novo = new Nodo();
        novo.Valor = oque;
        novo.Anterior = nodo;
        novo.Proximo = nodo.Proximo;

        if (nodo.Proximo != null)
            nodo.Proximo.Anterior = novo;

        nodo.Proximo = novo;
    }

    public void InsereNoInicio(string valor)
    {
        Nodo novo = new Nodo();
        novo.Valor = valor;
        novo.Proximo = primeiro;

        if (primeiro != null)
            primeiro.Anterior = novo;

        if (ultimo == null)
            ultimo = novo;

        primeiro = novo;
        quantidade++;
    }

    public void InsereNoFim(string valor)
    {
        Nodo novo = new Nodo();
        novo.Valor = valor;

        if (ultimo != null)
            ultimo.Proximo = novo;

        if (primeiro == null)
            primeiro = novo;

        novo.Anterior = ultimo;
        ultimo = novo;
        quantidade++;
    }

    public List Listar()
    {
        List lista = new List();
        Nodo aux = primeiro;
        while (aux != null)
        {
            lista.Add(aux.Valor);
            aux = aux.Proximo;
        }
        return lista;
    }
}

Classe Nodo (Lista Duplamente Encadeada)

public class Nodo
{
    private string valor = string.Empty;

    /// Guarda o valor de um item da lista
    public string Valor
    {
        get { return valor; }
        set { valor = value; }
    }

    private Nodo anterior = null;

    /// Guarda o endereço do nó anterior
    internal Nodo Anterior
    {
        get { return anterior; }
        set { anterior = value; }
    }

    private Nodo proximo = null;

    /// Guarda o valor do próximo nodo
    internal Nodo Proximo
    {
        get { return proximo; }
        set { proximo = value; }
    }
}

Form1 (Lista Duplamente Encadeada)

namespace Lista_Duplamente_Encadeada
{
    public partial class Form1 : Form
    {
        ListaDup minhalista = new ListaDup();

        public Form1()
        {
            InitializeComponent();
        }

        private void button3_Click(object sender, EventArgs e)
        {
            listBox1.Items.Clear();
            List lista = minhalista.Listar();
            foreach (string item in lista)
            {
                listBox1.Items.Add(item);
            }
        }

        private void button1_Click(object sender, EventArgs e)
        {
            minhalista.InsereNoInicio(textBox1.Text);
        }

        private void button2_Click(object sender, EventArgs e)
        {
            minhalista.InsereNoFim(textBox1.Text);
        }

        private void button4_Click(object sender, EventArgs e)
        {
            try
            {
                minhalista.InsereDepoisDe(textBox1.Text, textboxValorPosicao.Text);
            }
            catch (Exception erro)
            {
                MessageBox.Show(erro.Message);
            }
        }
    }
}