PRG29003: Introdução a Listas

[Próxima aula]

• Um video introdutório da Khan Academy
• Estruturas de dados
• Um guia sobre estruturas de dados
• Leis de desenvolvimento de software famosas

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. Pode-se fazer um paralelo com listas reais, que aparecem em diversas situações do dia-a-dia, como estas:

Uma playlist

Uma lista de tarefas

Do ponto de vista computacional, podem-se citar estas aplicações de listas:

• Armazenar um conjunto de dados cuja quantidade não pode ser conhecida de antemão. Exemplos são resultados de consultas a bancos de dados, listagens de arquivos de um diretório, resultados de separação de string em substrings.
• Armazenar dados cuja ordem em memória é modificada frequentemente. Exemplos são listas de processos em execução mantidas por sistemas operacionais, listas de mensagens a serem transmitidas cuja ordem depende de suas prioridades, listas de tarefas a serem realizadas por um simulador, listas de reprodução em tocadores de músicas.

Praticamente todas as linguagens de programação usadas atualmente possuem sua própria implementação de lista. Seguem alguns exemplos:

• Java
• Python
• C++
• C#
• Ruby

A lista da prglib

Do ponto de vista de uma estrutura de dados usada em programas, uma lista encadeada se aparenta com estes exemplos:

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 disponibiliza 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

O arquivo de projeto CLion com a biblioteca Prglib

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

Um resumo sobre a notação para complexidade de algoritmos

Figura obtida deste artigo sobre estruturas de dados em Python

Operações quer percorrem a lista

• Exceções: avisos de erros ou situações inesperadas em um programa

A lista encadeada da Prglib ofere outras operações além daquelas para adicionar, obter e remover dados. Duas outras operações são de grande utilidade:

• iteração: possibilita obter sucessivamente de forma eficiente os dados da lista;
• procura: possibilita procurar dados dentro da lista

Iteração

Quando se necessitam acessar em sequência todos (ou uma boa parte) dos dados de uma lista, a melhor forma é por meio da operação de iteração. A lista é capaz de ser iterada por meio dos métodos inicia, proximo e fim. Esses métodos são usados em conjunto para acessar cada dado da lista sucessivamente, a partir do início da lista. O exemplo a seguir mostra como usá-los:

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

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // inicia a iteração
  numeros.inicia();

  // enquanto não chegar ao fim da lista, continua a iteração
  while (! numeros.fim()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.proximo();

    cout << "Numero: " << algo << endl;
  }
}

Essa forma de percorrer os dados de uma lista é muito mais eficiente do que acessar os dados a partir de suas posições (usando o método obtem ou o operador []). Para ter uma ideia, percorrer uma lista com 10 dados é 10 vezes mais rápido com iteração. Se a lista tiver 100 dados, a iteração é 100 vezes mais rápida. Se a lista tiver 1000 dados, a uteração é 1000 vezes mais rápida, e assim por diante. O tempo que se leva para percorrer todos os dados com iteração é proporcional à quantidade de dados, porém se for usado o método obtem (ou operador []), o tempo necessário é proporcional ao quadrado da quantidade de dados.

A iteração pode ser feita também em sentido contrário se forem usados os métodos iniciaPeloFim, anterior, e inicio:

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

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // inicia a iteração pelo fim da lista
  numeros.iniciaPeloFim();

  // enquanto não chegar ao início da lista, continua a iteração
  while (not numeros.inicio()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.anterior();

    cout << "Numero: " << algo << endl;
  }
}

Procura por dados

Uma outra operações da lista útil e genérica diz respeito à busca de todos os dados que atendam algum critério de comparação, retornando uma outra lista com os dados encontrados.

A procura de um dado é uma operação que retorna todos os dados da lista de acordo com uma comparação de igualdade. Assim, os dados armazenados precisam ser comparáveis para que isso possa ser feito. Em outras palavras, o tipo de dados armazenado deve definir o operador de igualdade (==). Essa operação de procura está declarada assim na classe lista da prglib:

  // 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 à própria lista "result" que foi passada como parâmetro.
  lista<T> & procuraMuitos(const T &algo, lista<T> & result) const;

Existem dois métodos para procura de dados na lista:

• procura: procura a primeira ocorrência de um dado que seja igual a algo, retornando uma referência ao dado encontrado. Caso não o encontre, dispara uma exceção.
• procuraMuitos: procura todos os dados que sejam iguais a algo, e os armazena na lista result. Caso nada encontre, não modifica a lista result e termina sem avisar qualquer erro.

O método procura pode ser testado com uma lista de inteiros. O programa de teste a seguir demonstra o uso de procura (obs: o programa depende da lista ter implementado o método escrevaSe):

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

using namespace std;
using prglib::lista;

int main() {
  lista<int> l;

  l.anexa(5);
  l.anexa(1);
  l.anexa(5);
  l.anexa(5);
  l.anexa(1);
  l.anexa(8);
  l.anexa(2);

  // "procura" dispara uma exceção se não encontrar o dado, então 
  // deve-se capturar essa exceção para tratá-la.
  try {
    int res = l.procura(5);
    cout << "Encontrou o valor " << res << " na lista" << endl;
  } catch (...) {
    cout << "NÃO encontrou o valor 5 na lista" << endl;    
  }

  try {
    int res = l.procura(9);
    cout << "Encontrou o valor " << res << " na lista" << endl;
  } catch (...) {
    cout << "NÃO encontrou o valor 9 na lista" << endl;    
  }

  lista<int> lr;

  l.procuraMuitos(5, lr);
  cout << "Encontrou " << lr.comprimento() << " valores iguais a 5" << endl;
  lr.escrevaSe(cout, ",");
  cout << endl;
}

Comparação de igualdade

As operações de procura dependem da comparação de igualdade dos dados contidos numa lista. Isso significa que deve existir o operador == para o tipo desses dados. Esse operador existe na linguagem para tipos básicos, tais como int, float, char e outros. Mas o mesmo não vale para tipos de dados definidos pelo programador, ou mesmo classes. Nesse caso, o programador deve definir o operador == , pois somente ele sabe como valores desses tipos devem ser comparados. Observe-se também que a comparação dos dados não é um problema da lista, que apenas usa a comparação. Em suma, cada tipo e dados ou classe deve saber como comparar seus valores ou objetos.

A linguagem C++ possibilita definir como um determinado operador deve funcionar. Isso aplicado ao operador == resolve o problema da comparação de um tipo de dados definido pelo programador. A implementação de um operador pode ser feita de duas maneiras:

1. Incluindo-o ao tipo struct ou à classe:

   struct Registro {
     // atributos do tipo Registro
   
     bool operator==(const Registro & outro) const;
   };
   

2. Criando uma função:

   // compara "este" com "outro"
   bool operator==(const Registro & este, const Registro & outro) const {
     // implementação da comparação
   }
   

Ambas as formas de implementar um operador são válidas e resolvem o problema. Uma observação diz respeito à implementação com uma função, a qual tem precedência sobre a implementação dentro da struct ou classe. Isso significa que mesmo que já exista o operador em questão definido dentro de uma struct ou classe, ele pode ser substituído por outra implementação desse operador em uma função. A isso se chama sobrecarga de operador.

Atividade

Faça estes exercícios que envolvem iteração e/ou procura por dados:

1. Copiar uma lista usando iteração
2. Filtra valores de uma lista
3. Lista de contadores
4. Palavras repetidas
5. Contador de palavras

Operações que reorganizam a lista

Três operações disponíveis na lista reorganizam a ordem dados dados armazenados:

• ordenamento: ordena os dados de forma eficiente
• embaralhamento: mistura os dados aleatoriamente
• inversão: inverte a ordem dos dados

Ordenamento da lista

A lista possui o método ordena, que ordena seus dados. O ordenamento é feito por um algoritmo com razoável eficiência (ele tem custo de tempo computacional O(n log n)), e isso é importante porque esse tipo de operação tem custo computacional considerável (pode ser proporcional ao quadrado da quantidade de dados se não for bem feito). O único requisito para ordenar uma lista é que os dados armazenados possuam uma relação de precedência. Em outras palavras, que possam ser comparados com operador < (menor que). O exemplo a seguir mostra o ordenamento de uma lista:

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

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // ordena a lista
  numeros.ordena();

  numeros.escrevaSe(cout);

  cout << endl;
}

Como o método ordena depende da existência do operador < para o tipo dos dados armazenados, as mesmas considerações feitas quanto à operação de igualdade se aplicam aqui. A próxima subseção mostra um exemplo de ordenamento de uma lista que contém valores de um tipo definido pelo programador.

Ordenamento de uma lista com valores de um tipo definido pelo programador

Quando um programador define um novo tipo ou classe, seus operadores relacionais ainda não existem. Quer dizer, não se conseguem comparar valores desse novo tipo com operadores tais como <, >, <=, >= e ==, entre outros. O ordenamento da lista depende do operador <, portanto uma lista que contenha valores do novo tipo não pode ser ordenada a menos que esse operador seja declarado e implementado.

O exemplo a seguir mostra um programa que cria uma lista com valores de um novo tipo de dados, e a ordena.

Exemplo com o operador< como um método do novo tipo de dados

// o novo tipo de dados: as coordenadas de um vetor bidimensional struct Vetor { double x, y; Vetor(double X, double Y) { x = X; y = Y; } // calcula o módulo do vetor double modulo() const { return sqrt(x*x + y*y); } // operador < para Vetor: compara os módulos deste vetor com o outro vetor // retorna true se módulo deste vetor for menor que módulo de v2 bool operador<(const Vetor & v2) { return modulo() < m2.modulo(); } }; int main() { lista<Vetor> lv; // acrescenta alguns vetores à lista lv.anexa(Vetor(2,2)); lv.anexa(Vetor(1,3)); lv.anexa(Vetor(3,2)); lv.anexa(Vetor(0,5)); lv.anexa(Vetor(3,3)); // ordena a lista lv.ordena(); // mostra os vetores ordenados lv.inicia(); while (! lv.fim()) { Vetor & v = lv.proximo(); cout << "x=" << v.x << ", " << y=" << v.y << endl; } }

Exemplo com o operador< como uma função

// o novo tipo de dados: as coordenadas de um vetor bidimensional struct Vetor { double x, y; Vetor(double X, double Y) { x = X; y = Y; } // calcula o módulo do vetor double modulo() const { return sqrt(x*x + y*y); } }; // operador < para Vetor: compara os módulos dos vetores v1 e v2 // retorna true se módulo do vetor v1 for menor que módulo de v2 bool operador<(const Vetor & v1, const Vetor & v2) { return m1.modulo() < m2.modulo(); } int main() { lista<Vetor> lv; // acrescenta alguns vetores à lista lv.anexa(Vetor(2,2)); lv.anexa(Vetor(1,3)); lv.anexa(Vetor(3,2)); lv.anexa(Vetor(0,5)); lv.anexa(Vetor(3,3)); // ordena a lista lv.ordena(); // mostra os vetores ordenados lv.inicia(); while (! lv.fim()) { Vetor & v = lv.proximo(); cout << "x=" << v.x << ", " << y=" << v.y << endl; } }

Outro exemplo visto em aula

#include <iostream> #include <string> #include <prglib.h> using namespace std; using prglib::lista; // Tipo Alguem: representa uma pessoa com seu nome e idade struct Alguem { string nome; int idade; Alguem() { idade = 0; } Alguem(const string & umNome, int age) { nome = umNome; idade = age; } // sobrecarga do operador< para o tipo Alguem bool operator<(const Alguem & o) { if (idade == o.idade) { return nome < o.nome; } return idade < o.idade; } }; // sobrecarga do operador << para stream de saída (ostream) // com ele se consegue escrever na stream um valor do // tipo Alguem ostream & operator<<(ostream & out, const Alguem & x) { out << x.nome << ": " << x.idade; return out; } int main() { lista<Alguem> l; Alguem joao("Joao", 20); Alguem ninguem; Alguem x1("Amanda", 15); l.anexa(x1); Alguem x2("Gabriel", 19); l.anexa(x2); l.anexa(Alguem("Isadora", 18)); l.anexa(Alguem("Gustavo", 18)); // ordena a lista l.ordena(); // isto só funciona porque agora existe o operador << // que sabe apresentar o tipo Alguem l.escrevaSe(cout); cout << endl; }

Embaralhamento

O embaralhamento envolve misturar eficientemente os dados da lista de forma aleatória. O algoritmo envolvido tem custo de tempo computacional O(n log n). Esse método está declarado assim na classe lista:

  // embaralha os dados de uma lista
  void embaralha();

Seu uso é direto, e não há dependência a qualquer operador do tipo dos dados armazenados. Um exemplo de uso é este:

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

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // embaralha a lista
  numeros.embaralha();

  numeros.escrevaSe(cout);

  cout << endl;
}

Inversão

A inversão da lista envolve inverter a ordem dos dados nela armazenados: o primeiro se torna o último, o segundo o penúltimo, e assim por diante. O algoritmo envolvido tem custo de tempo computacional O(n). Esse método está declarado assim na classe lista:

  // inverte a ordem dos dados de uma lista
  void inverte();

Seu uso é direto, e não há dependência a qualquer operador do tipo dos dados armazenados. Um exemplo de uso é este:

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

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // ordena a lista
  numeros.ordena();

  // ... e agora a inverte, para obter um ordenamento decrescente
  numeros.inverte();

  numeros.escrevaSe(cout);

  cout << endl;
}

Atividade

Faça estes exercícios que envolvem ordenamento:

1. Lista ordenada de números inteiros
2. Ordenar linhas de um arquivo
3. Ordenar linhas de um arquivo de acordo com comprimentos das linhas