2 – Listas encadeadas

Uma lista encadeada é uma estrutura de dados fundamental em programação que consiste em uma coleção de elementos chamados nós, onde cada nó contém dois componentes principais:

• Dados: O valor armazenado no nó.
• Ponteiro (ou referência): Um campo que aponta para o próximo nó da lista.

A lista encadeada possui algumas características:

1. É uma estrutura de dados usada para armazenar coleções de dados
2. Os dados são armazenados em nós.
3. Cada nó contém uma referência para o próximo nó em sequência. Estruturalmente uma lista encadeada é organizada em uma cadeia de nós, por isso o seu nome.
4. Existem 2 tipos de listas encadeadas:
   • Lista singularmente encadeada(singly linked list) :
     • aonde cada nó aponta para o próximo nó e o último nó contém nulo.
   • Lista duplamente encadeada(doubly linked list)
     • aonde cada nó possui 2 referências(links), uma para o nó anterior e uma para o próximo.
5. Listas encadeadas são utilizadas em outros tipos de estruturas de dados como pilhas e filas.

Exemplo de implementação simples, com a explicação nos comentários:

using System;

//Estrutura de dados utilizada para armazenar os valores da nossa lista
public class No
{
    public int Valor { get; set; }
    public No Anterior { get; set; } //Referência para o item anterior na lista
    public No Proximo { get; set; } //Referência para o próximo valor na lista

    public No(int valor)
    {
        Valor = valor;
        Anterior = null;
        Proximo = null;
    }
}

public class ListaDuplamenteEncadeada
{
    private No cabeca; //Primeiro elemento da lista encadeada, por isso o nome cabeça
    private No cauda; //Próximos nós da lista encadeada(importante aqui, não é o último e sim o próximo nó, dado a posição em que você se encontra na lista)

    public ListaDuplamenteEncadeada()
    {
        cabeca = null;
        cauda = null;
    }

    // Adiciona um novo nó ao final da lista
    public void AdicionarAoFinal(int valor)
    {
        No novoNo = new No(valor);
        if (cabeca == null)
        {
            cabeca = novoNo;
            cauda = novoNo;
        }
        else
        {
            cauda.Proximo = novoNo;
            novoNo.Anterior = cauda;
            cauda = novoNo;
        }
    }

    // Adiciona um novo nó ao início da lista
    public void AdicionarAoInicio(int valor)
    {
        No novoNo = new No(valor);
        if (cabeca == null)
        {
            cabeca = novoNo;
            cauda = novoNo;
        }
        else
        {
            novoNo.Proximo = cabeca;
            cabeca.Anterior = novoNo;
            cabeca = novoNo;
        }
    }

    // Remove o primeiro nó que contém o valor especificado
    public void Remover(int valor)
    {
        No atual = cabeca;
        while (atual != null)
        {
            if (atual.Valor == valor)
            {
                if (atual.Anterior != null)
                {
                    atual.Anterior.Proximo = atual.Proximo;
                }
                else
                {
                    cabeca = atual.Proximo;
                }

                if (atual.Proximo != null)
                {
                    atual.Proximo.Anterior = atual.Anterior;
                }
                else
                {
                    cauda = atual.Anterior;
                }
                return;
            }
            atual = atual.Proximo;
        }
    }

    // Exibe os elementos da lista do início ao fim
    public void ExibirDoInicioAoFim()
    {
        No atual = cabeca;
        while (atual != null)
        {
            Console.Write(atual.Valor + " ");
            atual = atual.Proximo;
        }
        Console.WriteLine();
    }

    // Exibe os elementos da lista do fim ao início
    public void ExibirDoFimAoInicio()
    {
        No atual = cauda;
        while (atual != null)
        {
            Console.Write(atual.Valor + " ");
            atual = atual.Anterior;
        }
        Console.WriteLine();
    }
}

class Program
{
    static void Main()
    {
        ListaDuplamenteEncadeada lista = new ListaDuplamenteEncadeada();
        lista.AdicionarAoFinal(10);
        lista.AdicionarAoFinal(20);
        lista.AdicionarAoInicio(5);
        lista.ExibirDoInicioAoFim(); // Saída: 5 10 20
        lista.ExibirDoFimAoInicio(); // Saída: 20 10 5

        lista.Remover(10);
        lista.ExibirDoInicioAoFim(); // Saída: 5 20
    }
}

[]’s
Otávio

---

Item Anterior:

1 – Arrays

Próximo Item: NULL