Listas Encadeadas Simples

Prévia do material em texto

Universidade Federal de Itajubá
BAC004 - Informática
Profa. Claudia Akemi Izeki
Prof. Walter Aoiama Nagai
Tópico Complementar: Lista Encadeada Simples
1. Listas Sequenciais e Dinâmicas
Uma lista linear agrupa informações referentes a um conjunto de elementos que, de alguma forma, 
se relacionam entre si. Uma lista linear é um conjunto de n >= 0 elementos ou nós: L[1], L[2], ..., L[n] tais 
que suas propriedades estruturais são:
● Se n é igual a 0, a lista está vazia;
● Se n > 0, L[1] é o primeiro elemento da lista;
● L[n] é o último elemento da lista;
● Para 1 < k <= n, o nó L[k] é precedido por L[k-1] e seguido pelo elemento L[k+1].
Em outras palavras, a característica fundamental de uma lista linear é o sentido de ordem 
unidimensional dos elementos que a compõem. Pode-se dizer com precisão onde o conjunto de elementos 
se inicia e onde termina, sem possibilidade de dúvida.
1.1. Listas Sequenciais
Os exemplos anteriores de programas utilizam a representação por alocação sequencial. A 
representação por alocação sequencial explora a característica de sequencialidade de memória do 
computador, de tal forma que os nós de uma lista sejam armazenados em endereços contíguos, ou 
igualmente distanciados um do outro. Neste caso, a relação de ordem entre os nós da lista é representada 
pelo fato de que se o endereço do nó x é conhecido, então o endereço do nó x+1pode ser determinado.   
Esse tipo de representação facilita a compreensão, mas era obrigatório estipular antecipadamente a 
quantidade de elementos do vetor; verificar se ocorreria overflow ou underflow; se poderia inserir 
elementos no meio do vetor; etc.
1.2. Listas Dinâmicas
Uma outra representação de listas lineares é a representação por encadeamento de nós. Ao invés 
de manter os elementos agrupados numa área contínua, ou seja, ocupando posições consecutivas na 
memória; na alocação encadeada os elementos ocupam quaisquer células, não necessariamente 
consecutivas e, para manter a relação de ordem linear, juntamente com cada nó é armazenado o endereço 
do próximo nó da lista.
Desta forma, na alocação encadeada, os elementos estão armazenados em blocos de memória 
denominados nós, sendo que cada nó é composto por pelo menos dois campos: um para armazenar dados 
e outro para armazenar endereço.
Dois tipos de nós especiais devem ser destacados:
1
● o nó que aponta para o primeiro elemento da lista, denominado comumente como inicio;
● o nó NULO ou NULL que aponta para o endereço que deve terminar uma lista.
A alocação encadeada apresenta como maior vantagem a facilidade de inserir ou remover 
elementos do meio da lista. Como os elementos não precisam estar armazenados em posições consecutivas 
de memória, nenhum dado precisa ser movimentado, bastando atualizar o campo de ligação do elemento 
que precede aquele inserido ou removido. Na Figura 1 pode ser observado um exemplo de lista encadeada 
de nós que tem seu início indicado pelo nó início e seu término pelo nó nulo.
Quando os nós de uma lista encadeada possuem informação do próximo nó da lista, esta é chamada 
lista simplesmente encadeada. Já quando os nós possuem ponteiros para o próximo nó e para o seu 
anterior, a lista é chamada de duplamente encadeada. Neste roteiro, o foco são as listas simplesmente 
encadeadas.
Figura 1. Lista dinâmica encadeada de nós, também chamada de lista simplesmente encadeada.
A implementação de uma lista encadeada caracteriza-se na forma de declarar o nó e a lista.
struct No
{
int info;
struct No *proximo;
};
struct Lista
{
No *inicio;
};
Deve-se notar que se trata de uma estrutura auto-referenciada, pois, além do campo que 
armazena a informação (no caso, um número inteiro), há um campo que é um ponteiro para uma próxima 
estrutura do mesmo tipo. Pode-se operar sobre esta lista encadeada, inserindo-se nós no começo, no meio 
ou no final de uma lista.
● Para inserir no início da lista, deve-se criar um novo nó, por exemplo "9", e acrescentá-lo ao 
início da lista, conforme ilustrado na Figura 2.
2
Figura 2. Inserção de um novo nó "9" no início da lista encadeada.
● Ao remover o elemento, por exemplo "1", do início da lista, o início deve apontar para o 
próximo nó apontado por início, conforme ilustrado na Figura 3. Depois da última atribuição, já 
é seguro "destruir" o "1".
Figura 3. Remoção do elemento "1" do início da lista.
● Ao inserir um nó "4" no final da lista, o último nó "7" deve apontar para o novo nó da lista, 
conforme ilustrado na Figura 4.
Figura 4. Inserção de um novo nó "4" no final da lista.
● Ao remover o nó "7" do final da lista, o penúltimo nó "8" deve apontar para o nó apontado 
3
por "7" que é o nó nulo; assim o nó "7" pode ser destruído, conforme ilustrado na Figura 5.
Figura 5. Remoção do último nó da lista encadeada.
2. Implementação de uma Lista Simplesmente Encadeada
#include <cstdlib>
#include <iostream>
using namespace std;
struct No
{
    int info;
    struct No *prox;
};
No* criarNo(int in)
{
    No *no = new No();
    if (no != NULL)
    {
        no­>info = in;
        no­>prox = NULL;
        return no;
    }
    return NULL;
}
bool listaVazia(No *lista)
{
    if (lista == NULL)
        return true;
    return false;
}
void insereNoInicioLista (No **lista, No *no)
{
    if (listaVazia(*lista))
        *lista = no;
    else
    {
        no­>prox = *lista;
        *lista = no;
    }
}
void insereNoFinalLista(No **lista, No *no)
4
{
    if (listaVazia(*lista))
        *lista = no;
    else
    {
        No *t = *lista;
        while (t­>prox != NULL)
            t = t­>prox;
        t­>prox = no;
    }
}
void removeNoInicioLista(No **lista)
{
    if (!listaVazia(*lista))
    {
        No *noRemovido = *lista;
        *lista = (*lista)­>prox;
        noRemovido­>prox = NULL;
        delete noRemovido;
    }
}
void removeNoFinalLista(No **lista)
{
    if (!listaVazia(*lista))
    {
        No *anterior, *atual;
        anterior = NULL;
        atual = *lista;
        while (atual­>prox != NULL)
        {
            anterior = atual;
            atual = atual­>prox;
        }
        if (atual == *lista)
        {
            delete *lista;
            (*lista) = NULL;
        }
        else
        {
            anterior­>prox = atual­>prox;
            atual­>prox = NULL;
            delete atual;
            atual = NULL;
        }
    }
}
void imprimirLista(No *lista)
{
    if (!listaVazia(lista))
    {
        for(No *t = lista; t != NULL; t = t­>prox)
        {
            cout << t­>info << "\t";
        }
        cout << endl;
    }
}
int main()
5
{
    No *inicioLista = NULL;
    for (int i = 0; i < 10; i++)
    {
        insereNoInicioLista(&inicioLista, criarNo(rand() % 100));
        imprimirLista(inicioLista);
    }
    for (int i = 0; i < 10; i++)
    {
        removeNoInicioLista(&inicioLista);
        imprimirLista(inicioLista);
    }
    for (int i = 0; i < 10; i++)
    {
        insereNoFinalLista(&inicioLista, criarNo(rand() % 100));
        imprimirLista(inicioLista);
    }
    for (int i = 0; i < 10; i++)
    {
        removeNoFinalLista(&inicioLista);
        imprimirLista(inicioLista);
    }
    if (inicioLista)
        delete inicioLista;
    return 0;
}
6