PRG29003: Introdução a Listas

• Um video introdutório da Khan Academy

Uma lista encadeada é uma estrutura de dados em que os dados são armazenados dinamicamente em memória, de forma a se organizarem em uma sequência. Qualquer dado em uma lista pode ser acessado, independente de sua posição, assim como pode ser adicionados ou removidos de uma posição qualquer. Além disso, a ordem dos dados em uma lista pode ser modificada de diferentes maneiras (ordenamento, embaralhamento, inversão, ...). Tudo isso graças à forma com que uma lista encadeia os dados, em que cada dado armazenado possui referências tanto a seu sucessor quanto seu antecessor. A figura abaixo ilustra uma lista encadeada:

Uma lista possui algumas características:

• Os dados são armazenados dinamicamente, por isso a quantidade total de memória usada para a lista depende da quantidade de dados nela armazenados (compare isso com um vetor ou matriz).
• A lista não precisa ocupar uma área de memória contígua: como dados são armazenados dinamicamente, eles podem ocupar áreas de memória arbitrárias, e não há nenhuma relação entre a localização dos dados em memória e sua ordem na lista (novamente compare isso com um vetor ou matriz).
• Não é possível indexar os dados, por isso para acessar um dado deve-se obrigatoriamente procurá-lo a partir do início ou fim da lista, seguindo cada sucessor ou antecessor até chegar àquele procurado.
• Para adicionar um dado, basta modificar a referência ao sucessor do dado que deve antecedê-lo na lista. Assim, não é necessário "empurrar" os dados seguintes para frente (como seria o caso de um vetor).
• Para remover um dado é a mesma coisa: basta modificar a referência de seu antecessor. Assim, não é necessário "deslocar pra trás" os dados seguintes (como seria o caso de um vetor).

As operações elementares de uma lista definem como dados podem ser adicionados, obtidos e removidos da lista, e também que informações sobre a lista podem ser obtidas. São elas:

• anexa: adiciona um dado ao final da lista
• insere: adiciona um dado em uma determinada posição da lista
• remove: remove um dado de uma determinada posição da lista
• obtem: obtém um dado de uma determinada posição da lista
• comprimento: obtém o comprimento da lista
• esvazia: esvazia a lista (remove todos os dados)

A biblioteca Prglib possui uma lista,cuja declaração é apresentada a seguir:

A lista encadeada da biblioteca Prglib

#ifndef LISTA_H #define LISTA_H #include <cstddef> #include <ostream> #include <string> #include <list> #include <algorithm> #include <random> using std::shared_ptr; namespace prglib { template <typename T> class lista { public: //construtor: não precisa de parâmetros para criar uma nova lista lista(); // construtor de cópia lista(const lista &outra); // destrutor virtual ~lista(); // insere "algo" no inicio da lista void insere(const T & algo); // adiciona "algo" no final da lista void anexa(const T & algo); // insere "algo" em uma posição específica da lista void insere(const T & algo, int posicao); void insereOrdenado(const T & algo); // remove o dado que está na "posicao" na lista, e retorna // uma cópia desse dado virtual T remove(int posicao); // remove todos os dados que forem equivalentes a "algo" void retira(const T & algo); // estas duas operações são idênticas: retorna // uma referência ao dado que está na "posicao" na lista T& obtem(int posicao) const; T& operator[](int pos) const; // atribuição: torna esta lista idêntica à outra lista virtual lista& operator=(const lista<T> & outra); // compara duas listas: são iguais se tiverem mesmo comprimento // E todos os dados armazenados forem iguais e na mesma ordem bool operator==(const lista<T> & outra) const; // Retorna uma referência a um dado que seja equivalente a "algo" T& procura(const T &algo) const; // Procura todos os dados equivalentes a "algo", e os // anexa a "lista". Retorna uma referência a "lista". lista<T> & procuraMuitos(const T &algo, lista<T> & lista) const; // retorna a quantidade de dados armazenados na lista int comprimento() const; // retorna true se lista estiver vazia bool vazia() const; // Esvazia a lista void esvazia(); // apresenta o conteúdo da lista no stream "out" void escrevaSe(std::ostream & out) const; void escrevaSe(std::ostream & out, const std::string & delim) const; // ordena a lista void ordena(); // iteração do início pro fim void inicia(); T & proximo(); bool fim() const; // ... e do fim pro início void iniciaPeloFim(); T & anterior(); bool inicio() const; // inverte a ordem nos nodos na lista void inverte(); // embaralha os dados de uma lista void embaralha(); // obtém uma sublista lista<T> * sublista(unsigned int pos1, unsigned int pos2) const; lista<T> & sublista(unsigned int pos1, unsigned int pos2, lista<T> & outra) const; };

Abaixo segue um exemplo de uso de algumas operações de uma lista:

#include <cstdlib>
#include <prglib.h>
#include <iostream>
#include <string>

using namespace std;
using prglib::lista;

int main(int argc, char** argv) {
    // cria uma lista de string
    lista<string> nomes;
    
    // anexa três dados ao final da lista
    nomes.anexa("manuel");
    nomes.anexa("maria");
    nomes.anexa("bilica");
    
    // mostra comprimento e conteúdo da lista
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
    
    // insere dado no início da lista
    nomes.insere("maneca");
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;

    // insere dado na posição 2 da lista
    nomes.insere("joaquim", 2);
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;

    // remove dado do início da lista
    nomes.remove(0);
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
    
    // remove dado da posição 2 da lista
    nomes.remove(2);
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
    
    // esvazia a lista
    nomes.esvazia();
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
        
    // ao final, lista é automaticamente destruída, e a memória utilizada
    // é liberada
    return 0;
}

Atividade

1. Faça os exercícios sobre listas que estão no Moodle, para se familiarizar com listas