LinkedList

Listas Encadeadas (Linked List)

Tópicos

Introdução

Uma lista encadeada é uma estrutura de dados que consiste em nós ligados em uma sequência, onde cada nó contém campos: um campo de dados para armazenar informações e para ponteiros.

Baixar, Compilar e Executar Código de Repositório via Terminal

Pré-requisitos

Antes de prosseguir, certifique-se de que você tenha o seguinte instalado no seu sistema:

Passo 1: Clone o Repositório

Abra seu terminal e execute o seguinte comando para clonar o repositório do GitHub:

git clone https://github.com/classroom-ufersa/LinkedList.git

Passo 2: Navegue para o Diretório do Repositório em que está a TAD que quer compilar

Use o comando cd para navegar para o diretório do repositório que acabou de ser clonado ou simplesmente abra com terminal integrado na pasta.

cd ListaEncadeadaSimples
cd src

Passo 3: Compile o Código

Compile-o usando o compilador C. Por exemplo:

gcc -o main main.c

Passo 4: Execute o Programa

Agora, você pode executar o programa compilado usando o comando ./ no terminal:

./main

Porque utilizar uma TAD?

Listas Encadeadas Simples

Descrição lista simples

Lista encadeada simples

imagem tirada do site: SauloArisa

Estrutura lista simples

struct lista
{
    int info;
    struct lista *prox;
};

Vantagens lista simples

  1. Alocação Dinâmica de Memória: Permite a alocação dinâmica de memória, facilitando a adição e remoção de elementos conforme necessário.

  2. Inserção e Exclusão Eficientes: Inserir ou excluir elementos no início é eficiente, minimizando a necessidade de deslocamento de dados.

  3. Redimensionamento Dinâmico: A lista pode crescer ou encolher conforme necessário, adequando-se a tamanhos variáveis de dados.

Desvantagens lista simples

  1. Acesso direto ineficiente: O acesso a um elemento específico requer percorrer a lista, o que é menos eficiente que arrays para acesso direto por índice.

  2. Gasto de memória extra por elemento: Cada nó requer espaço extra para o ponteiro, aumentando o consumo de memória em comparação com arrays.

  3. Complexidade de implementação: Implementar operações pode ser mais complexo devido à gestão de ponteiros e alocação dinâmica de memória.

Algumas funções da TAD Lista:

lst_cria

Lista *lst_cria(void)
{
    return NULL;
}

Lista *lista = lst_cria();

lst_insere

Lista *lst_insere(Lista *l, int v)
{
    Lista *novo = (Lista *)malloc(sizeof(Lista));
    if (novo == NULL)
    {
        printf("[ERRO] Memória insuficiente!");
        exit(1);
    }
    novo->info = v;
    novo->prox = l;
    return novo;
}

lista = lst_insere(lista, 42);

lst_vazia

int lst_vazia(Lista *l)
{
    return (l == NULL);
}

if (lst_vazia(lista)) {
    printf("A lista está vazia.\n");
}

lst_imprime

void lst_imprime(Lista *l)
{
    Lista *p;
    for (p = l; p != NULL; p = p->prox)
    {
        printf(" Info = %d \n", p->info);
    }
}

lst_imprime(lista);

lst_busca

Lista *lst_busca(int elemento, Lista *l)
{
    Lista *p;
    for (p = l; p != NULL; p = p->prox)
    {
        if (p->info == elemento)
            return p;
    }
    return NULL;
}

Lista *resultado = lst_busca(42, lista);

lst_retira

Lista *lst_retira(Lista *l, int v)
{
    Lista *ant = NULL;
    Lista *p = l;
    while (p->info != v)
    {
        if (p == NULL)
            return l;
        ant = p;
        p = p->prox;
    }
    if (ant == NULL)
        l = p->prox;
    else
        ant->prox = p->prox;
    free(p);
    return l;
}

lista = lst_retira(lista, 42);

lst_libera

void lst_libera(Lista *l)
{
    Lista *p = l;
    Lista *t;
    while (p != NULL)
    {
        t = p->prox;
        free(p);
        p = t;
    }
}

lst_libera(lista);

lst_insere_ordenada

Lista *lst_insere_ordenada(Lista *l, int v)
{
    Lista *novo;
    Lista *ant = NULL;
    Lista *p = l;
    while (p != NULL && p->info < v)
    {
        ant = p;
        p = p->prox;
    }
    novo = (Lista *)malloc(sizeof(Lista));
    novo->info = v;
    if (ant == NULL)
    {
        novo->prox = l;
        l = novo;
    }
    else
    {
        novo->prox = ant->prox;
        ant->prox = novo;
    }
    return l;
}

lista = lst_insere_ordenada(lista, 42);

lst_ler_arquivo

Lista *lst_ler_arquivo(char *nome_arquivo)
{
    FILE *arquivo;
    int valor;
    Lista *l = lst_cria();
    arquivo = fopen(nome_arquivo, "r");
    if (arquivo == NULL)
    {
        printf("Erro ao abrir o arquivo!\n");
        exit(1);
    }
    while (fscanf(arquivo, "%d", &valor) != EOF)
    {
        l = lst_insere(l, valor);
    }
    fclose(arquivo);
    return l;
}

lista = lst_ler_arquivo("dados.txt");

Listas Encadeadas Duplas

Descrição lista dupla

Uma lista encadeada dupla é uma estrutura de dados que expande a funcionalidade de uma lista encadeada simples, permitindo que cada nó mantenha referências tanto para o próximo quanto para o nó anterior na sequência. Isso significa que, além de apontar para o próximo nó, cada nó também aponta para o nó anterior, criando uma conexão bidirecional entre os elementos.

A principal diferença entre uma lista encadeada simples e uma lista encadeada dupla é que, em uma lista dupla, você pode percorrer a lista em ambas as direções: do início para o fim e do fim para o início.

As listas encadeadas duplas são uma escolha valiosa quando a flexibilidade e a capacidade de travessia bidirecional são necessárias, mas é importante considerar cuidadosamente as vantagens e desvantagens ao escolher essa estrutura de dados para um determinado problema.

Lista encadeada duplas

imagem tirada do site: SauloArisa

Estrutura lista dupla

struct lista_dupla
{
    int info;
    struct lista_dupla *prox;
    struct lista_dupla *ant;
};

Vantagens lista dupla

  1. Travessia Bidirecional: Uma das principais vantagens das listas encadeadas duplas é a capacidade de percorrer a lista em ambas as direções. Isso permite acesso eficiente tanto do início para o fim quanto do fim para o início, o que pode ser útil em muitos cenários, como a necessidade de encontrar elementos próximos ao final da lista.

  2. Inserção e Exclusão Eficiente em Qualquer Posição: As listas encadeadas duplas permitem a inserção e exclusão eficiente de elementos em qualquer posição da lista. Isso ocorre porque cada nó mantém referências para os nós anterior e posterior, facilitando a atualização dos ponteiros durante a inserção ou exclusão.

  3. Flexibilidade: As listas duplas são altamente flexíveis e podem ser usadas em uma variedade de cenários. Elas são especialmente úteis quando a ordem dos elementos é importante e quando operações de inserção e exclusão frequentes são necessárias.

Desvantagens lista dupla

  1. Consumo de Memória: Em comparação com algumas outras estruturas de dados, as listas encadeadas duplas podem consumir mais memória devido à necessidade de manter dois ponteiros (um para o próximo nó e outro para o nó anterior) em cada nó da lista. Isso pode ser uma desvantagem em sistemas com restrições de memória.

  2. Complexidade de Implementação: Implementar e manter listas encadeadas duplas pode ser mais complexo do que listas encadeadas simples ou arrays. Isso ocorre porque é necessário gerenciar os ponteiros de forma mais cuidadosa, garantindo que eles sejam atualizados corretamente durante as operações de inserção e exclusão.

  3. Acesso Direto Ineficiente: Assim como nas listas encadeadas simples, o acesso direto a um elemento específico em uma lista encadeada dupla requer percorrer a lista, o que pode ser menos eficiente do que o acesso direto por índice em arrays.

Algumas Funções da TAD Lista Dupla:

listd_cria

Listad *listd_cria(void)
{
    return NULL;
}

Listad *lista = listd_cria();

listd_libera

void listd_libera(Listad *l)
{
    Listad *p = l;
    while (p != NULL)
    {
        Listad *t = p->prox;
        free(p);
        p = t;
    }
}

listd_libera(lista);

listd_adc

Listad *listd_adc(Listad *l, int v)
{
    Listad *novo = (Listad *)malloc(sizeof(Listad));
    if (novo == NULL)
    {
        printf("[ERRO] Memória insuficiente!");
        exit(1);
    }
    novo->dado = v;
    novo->prox = NULL;
    novo->ant = NULL;

    if (l == NULL)
    {
        return novo;
    }

    Listad *ultimo = l;
    while (ultimo->prox != NULL)
    {
        ultimo = ultimo->prox;
    }

    ultimo->prox = novo;
    novo->ant = ultimo;

    return l;
}

lista = listd_adc(lista, 42);

listd_busca

Listad *listd_busca(Listad *l, int v)
{
    Listad *p;
    for (p = l; p != NULL; p = p->prox)
    {
        if (p->dado == v)
        {
            return p;
        }
    }
    return NULL; // não achou
}

Listad *resultado = listd_busca(42, lista);

listd_retira

Listad *listd_retira(Listad *l, int v)
{
    Listad *p = listd_busca(l, v);

    if (p == NULL)
    {
        return l; // não achou
    }

    // Remove o elemento
    if (l == p) // Testa se é o primeiro elemento
    {
        l = p->prox;
        if (p->prox != NULL)
        {
            p->prox->ant = NULL;
        }
    }
    else
    {
        p->ant->prox = p->prox; // Remove o do meio
        if (p->prox != NULL)
        {
            p->prox->ant = p->ant;
        }
    }
    free(p);
    return l;
}

lista = listd_retira(lista, 42);

listd_vazia

int listd_vazia(Listad *l)
{
    if (l == NULL)
        return 1;
    else
        return 0;
}

if (listd_vazia(lista))
{
    printf("A lista está vazia.\n");
}

listd_imprime

void listd_imprime(Listad *l)
{
    Listad *p;
    for (p = l; p != NULL; p = p->prox)
    {
        printf("Dado = %d\n", p->dado);
    }
}

listd_imprime(lista);

Listas Encadeadas Circulares Simples

Descrição lista circular simples

Uma lista encadeada circular simples é uma estrutura de dados na qual cada nó da lista aponta para o próximo nó, formando um ciclo no final da lista, onde o último nó aponta de volta para o primeiro nó. Isso cria uma sequência contínua de elementos que podem ser percorridos indefinidamente.

Estrutura lista circular simples

A estrutura de um nó em uma lista encadeada circular simples é igual à de uma lista encadeada simples. Cada nó contém um campo de dado e um ponteiro para o próximo nó na lista.

Lista encadeada duplas

imagem tirada do site: SauloArisa

struct lista
{
    int dado;
    struct lista *prox;
};

Vantagens lista circular simples

  1. As mesmas vantagens da lista simples: Sim ela tem as mesmas vantagens da lista simples e algumas extras como a descrita a seguir.

  2. Loop Infinito: A principal vantagem de uma lista encadeada circular simples é a capacidade de criar um loop infinito de elementos. Isso pode ser útil em algoritmos que exigem que a lista seja percorrida continuamente, sem um ponto final.

Desvantagens lista circular simples

  1. As mesmas desvantagens da lista simples: Sim ela também tem as mesmas desvantagens da lista simples e algumas extras como as descritas a seguir.

  2. Dificuldade na Detecção do Fim: Na lista simples, basta verificar se está apontando para NULL. Na lista circular, uma das soluções para detectar o fim é, antes de começar a percorrer, guardar o nó raiz em um ponteiro auxiliar. A cada passo que você der na lista, compare se aquele nó é igual ao nó raiz. Caso seja igual, significa que você já percorreu toda a lista.

  3. Tratamento de casos especiais: A manipulação de casos especiais, como a remoção do último elemento da lista, pode ser mais complexa em uma lista circular do que em uma lista encadeada comum. Você precisa lidar com essas situações de forma cuidadosa para evitar erros.

Algumas funções da TAD Lista Circular Simples:

listc_cria

Lista *listc_cria(void)
{
    return NULL;
}

Lista *lista = listc_cria();

listc_libera

void listc_libera(Lista *l)
{
    Lista *p = l;
    if (p != NULL)
    {
        do
        {
            Lista *t = p->prox;
            free(p);
            p = t;
        } while (p != l);
    }
}

listc_libera(lista);

listc_adc

Lista *listc_adc(Lista *l, int i)
{
    Lista *novo = (Lista *)malloc(sizeof(Lista));
    if (novo == NULL)
    {
        printf("[ERRO] Memória insuficiente!");
        exit(1);
    }
    novo->dado = i;
    if (l == NULL) // Se a lista estiver vazia
    {
        novo->prox = novo; // O próximo aponta para si mesmo
        return novo;       // Retorna a nova célula como primeira e última
    }
    novo->prox = l->prox; // O próximo aponta para a primeira célula
    l->prox = novo;       // Atualiza o próximo da última célula para apontar para a nova célula
    return l;             // Retorna a primeira célula da lista
}

lista = listc_adc(lista, 42);

listc_busca

Lista *listc_busca(Lista *l, int v)
{
    Lista *p = l;
    while (p != NULL && p->prox != l && p->dado != v)
    {
        p = p->prox;
        if (p->dado == v)
            return p;
    }
    return NULL;
}

Lista *resultado = listc_busca(42, lista);

listc_retira

Lista *listc_retira(Lista *l, int v)
{
    Lista *ant = NULL;
    Lista *p = l;
    while (p != NULL && p->dado != v)
    {
        ant = p;
        p = p->prox;
    }
    if (p == NULL)
    {
        return l; // Não achou
    }
    // Retira o elemento
    ant->prox = p->prox;
    free(p);
    return l;
}

lista = listc_retira(lista, 42);

listc_vazia

int listc_vazia(Lista *l)
{
    if (l == NULL)
        return 1;
    else
        return 0;
}

if (listc_vazia(lista))
{
    printf("A lista está vazia.\n");
}

listc_imprime

void listc_imprime(Lista *l)
{
    Lista *p = l;
    do
    {
        printf("Dado = %d\n", p->dado);
        p = p->prox;
    } while (p != l);
}

listc_imprime(lista);

Listas encadeadas circulares duplas

Descrição lista circular dupla

Uma lista encadeada circular dupla é uma estrutura de dados linear que combina as características das listas duplamente encadeadas e das listas circulares simples. Ela consiste em uma sequência de elementos, chamados de nós, onde cada nó armazena um valor (ou dado) e possui ponteiros tanto para o nó anterior quanto para o próximo nó na lista. A característica distintiva dessa estrutura é que o último nó na lista aponta para o primeiro nó, criando um ciclo, enquanto o primeiro nó também aponta para o último.

Estrutura lista circular dupla

struct listad
{
    int dado;
    struct listad *prox;
    struct listad *ant;
};

A estrutura da lista em si consiste em um ponteiro para o primeiro nó (cabeça) e, às vezes, um ponteiro para o último nó (cauda), dependendo da implementação.

Vantagens lista circular dupla

  1. As mesmas vantagens de uma lista dupla: Porém com algumas extras como a descrita a seguir.

  2. Inserção e remoção eficientes: As listas encadeadas circulares duplas permitem inserções e remoções rápidas no início, no final e em qualquer posição da lista, pois aproveitam os ponteiros de nó anterior e próximo.

Desvantagens lista circular dupla

  1. As mesmas desvantagens de uma lista dupla: Porém com algumas extras como as descritas a seguir.

  2. Manutenção do ciclo: Garantir que a lista permaneça circular exige controle rigoroso dos ponteiros de início e fim. Quando você insere ou remove elementos, é necessário garantir que os ponteiros sejam ajustados corretamente para manter a circularidade.

  3. Tratamento de casos especiais: A manipulação de casos especiais, como a remoção do último elemento da lista, pode ser mais complexa em uma lista circular dupla do que em uma lista duplamente encadeada comum. Você precisa lidar com essas situações de forma cuidadosa para evitar erros.

Algumas Funções da TAD Lista Circular Dupla

listdc_cria

Listad *listdc_cria(void)
{
    return NULL;
}

listdc_libera(lista);

listdc_libera

void listdc_libera(Listad *l)
{
    Listad *p = l;
    if (p != NULL)
    {
        do
        {
            Listad *t = p->prox;
            free(p);
            p = t;
        } while (p != l);
    }
}

listdc_libera(lista);

listdc_adc

Listad *listdc_adc(Listad *l, int v)
{
    Listad *novo = (Listad *)malloc(sizeof(Listad));
    if (novo == NULL)
    {
        printf("[ERRO] Memória insuficiente!");
        exit(1);
    }
    novo->dado = v;
    if (l == NULL) // Se a lista estiver vazia
    {
        novo->prox = novo; // O próximo aponta para si mesmo
        novo->ant = novo; // O anterior aponta para si mesmo
        return novo;       // Retorna a nova célula como primeira e última
    }
    novo->prox = l; // O próximo aponta para a primeira célula
    novo->ant = l->ant; // O anterior aponta para a última célula
    l->ant->prox = novo; // Atualiza o próximo da última célula para apontar para a nova célula
    l->ant = novo; // Atualiza o anterior da primeira célula para apontar para a nova célula
    return l;             // Retorna a primeira célula da lista
}

lista = listdc_adc(lista, 7);

listdc_busca

Listad *listdc_busca(Listad *l, int v)
{
    Listad *p = l;
    while (p != NULL && p->prox != l && p->dado != v)
    {
        p = p->prox;
        if (p->dado == v)
            return p;
    }
    return NULL;
}

Listad *resultado = listdc_busca(7, lista);

listdc_retira

Listad *listdc_retira(Listad *l, int v)
{
    Listad *p = listdc_busca(l, v);

    if (p == NULL)
    {
        return l; // Não achou
    }

    // Retira o elemento
    if (l == p)
    { // Testa se é o primeiro elemento
        if (l->prox == l) // Se for o único elemento na lista
        {
            free(l);
            return NULL; // Retorna lista vazia
        }
        else
        {
            l = p->prox; // Atualiza o início da lista
        }
    }

    p->ant->prox = p->prox; // Retira o do meio ou do final
    p->prox->ant = p->ant;

    if (l == p) // Se o último elemento está sendo retirado
    {
        l = NULL; // Define a lista como vazia
    }

    free(p);
    return l;
}

lista = listdc_retira(lista, 7);

listdc_vazia

int listdc_vazia(Listad *l)
{
    if (l == NULL)
        return 1;
    else
        return 0;
}

if (listdc_vazia(lista))
{
    printf("A lista está vazia.\n");
}

listdc_imprime

void listdc_imprime(Listad *l)
{
    if (l == NULL)
    {
        printf("Lista vazia.\n");
        return;
    }
    Listad *p = l;
    do
    {
        printf("Dado = %d\n", p->dado);
        p = p->prox;
    } while (p != l);
}

listdc_imprime(lista);