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 STL

A STL apresenta a estrutura de dados list para armazenamento de sequências de dados, os quais podem ser acessados randomicamente. Em uma lista, dados podem ser adicionados e removidos de qualquer posição com eficiência, porém são acessados de forma iterativa (sempre a partir do início ou final da lista). Em list, cada dado ocupa uma área de memória sob medida, e para formar uma sequência essas áreas de memória são encadeadas (ligadas). Como consequência, os dados não ficam contíguos em memória. Por exemplo, supondo que tenha sido criada uma lista chamada numeros, e nela tenham sido adicionados os números 10, 20, 30 e 40 (nessa ordem), o armazenamento desses números em memória poderia ser este:

Uma lista com alguns dados

Em geral, list é adequada quando a quantidade de dados a serem armazenados é variável e desconhecida, e quando dados precisam ser inseridos e removidos de qualquer posição. Os pontos listados a seguir buscam esclarecer melhor o que está em jogo.

• Não é necessária 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.
• 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.
• Acrescentar um dado implica 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.
• 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.

As operações elementares de list são:

• push_back: Adicionar um dado ao final
• push_front: Adicionar um dado no início
• pop_front: Remover um dado do início
• pop_back: Remover um dado do final
• insert: Inserir um dado em uma determinada posição
• erase: Remover um ou mais dados a partir de uma determinada posição
• front: Acessar o dado que está no início
• back: Acessar o dado que está no final
• size: Obter a quantidade de dados armazenados
• clear: Remover todos os dados (esvaziar)

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

#include <cstdlib>
#include <list>
#include <iostream>
#include <string>

using namespace std;

void mostra_lista(list<string> & lista) {
    // itera a lista
    for (auto & dado: lista) {
      cout << dado << ",";
    }
    cout << endl;
}

int main(int argc, char** argv) {
    // cria uma lista de string
    list<string> nomes;
    
    // anexa três dados ao final da lista
    nomes.push_back("manuel");
    nomes.push_back("maria");
    nomes.push_back("bilica");
    
    // mostra comprimento e conteúdo da lista
    cout << "Comprimento: " << nomes.size() << ", dados: ";
    mostra_lista(nomes);

    // insere dado no início da lista
    nomes.push_front("maneca");
    cout << "Comprimento: " << nomes.size() << ", dados: ";
    mostra_lista(nomes);

    // remove dado do início da lista
    nomes.pop_front();
    cout << "Comprimento: " << nomes.size() << ", dados: ";
    mostra_lista(nomes);
    
    // ao final, lista é automaticamente destruída, e a memória utilizada
    // é liberada
    return 0;
}

Ao usar essa nova estrutura de dados, existem algumas novidades em comparação com a fila e a pilha. A primeira delas diz respeito à iteração da lista. Tanto a fila quanto a pilha possibilitavam acessar apenas os dados em suas extremidades. A lista é muito mais flexível, possibilitando acessar dados em qualquer posição. No entanto, devido à forma como os dados ficam armazenados dentro da lista, para acessá-los é necessário usar um iterador.

Iteradores

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

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 de um iterador. Um iterador é um objeto que se assemelha a um ponteiro, e que possibilita acessar um dado da lista, além de avançar para o dado seguinte ou retroceder para o dado anterior. As operações begin e end da lista retornam, respectivamente, iteradores para o início ou fim da lista. O exemplo a seguir mostra como usá-los:

#include <iostream>
#include <list>

using namespace std;

int main() {
  list<int> numeros;

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

  // Itera do início ao fim da lista
  // A variável "it" é o iterador, que será usado para acessar os dados da lista
  // Note como ao final de cada repetição do laço o iterador é incrementado ... isso
  // faz com que se avance para o próximo dado da lista

  for (auto it = numeros.begin(); it != numeros.end(); it++) { 
    // acessa o dado atual da iteração: ele é referenciado pelo iterador,
    // como se este fosse um ponteiro

    cout << "Numero: " << *it << endl;
  }
}

Para fins de simplicidade, existe uma sintaxe na linguagem para iterar sequências de dados. Veja o exemplo anterior com essa forma de iterar:

#include <iostream>
#include <list>

using namespace std;

int main() {
  list<int> numeros;

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

  // Itera do início ao fim da lista
  // O iterador é usado implicitamente. Por isso, no laço a variável de controle 
  // acessa diretamente o dado atual da iteração (no caso, a variável "x").

  for (auto & x: numeros) { 
    // "x" contém o dado atual da iteração
    cout << "Numero: " << x << endl;
  }
}

Deve-se observar que isso é específico de C++: não há algo parecido na linguagem C ! Porém, essa forma simplificada de iterar sequências aparece em outras linguagens (ex: Python).

Iteração reversa

A iteração pode ser feita também em sentido contrário, se for usado um iterador reverso. Os métodos rbegin e rend de list retornam, respectivamente, iteradores reversos para o fim e início da lista:

#include <iostream>
#include <list>

using namespace std;

int main() {
  list<int> numeros;

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

  // Itera do início ao fim da lista
  // A variável "it" é o iterador, que será usado para acessar os dados da lista
  // Note como ao final de cada repetição do laço o iterador é incrementado ... isso
  // faz com que se retorceda para o próximo dado da lista

  for (auto it = numeros.rbegin(); it != numeros.rend(); it++) { 
    // acessa o dado atual da iteração: ele é referenciado pelo iterador,
    // como se este fosse um ponteiro

    cout << "Numero: " << *it << endl;
  }
}

A sintaxe para iteração simplificada não se aplica à iteração reversa !

Atividade

Objetivo: escrever um programa que mescle as informações contidas em diferentes arquivos, eliminando informações repetidas

• Descrição: existe um conjunto de arquivos, os quais contêm dados sobre alunos de uma escola. Cada arquivo corresponde a uma disciplina de algum curso dessa escola. Cada linha desses arquivos tem este formato:

matrícula aluno

... sendo matrícula um número com 8 dígitos, e aluno o nome completo de um aluno.

Há a necessidade de obter uma relação dos alunos matriculados nessas disciplinas, sendo que cada aluno deve aparecer uma única vez.

Para se familiarizar com o uso de listas, resolva primeiro estes exercícios:

1. Lista de números inteiros
2. Copiar uma lista usando iteração
3. Junta strings contidas em uma lista
4. Filtra valores de uma lista
5. Lista de contadores
6. Palavras repetidas
7. Contador de palavras
8. A função separa usando lista
9. Compactador de endereço IPv6

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

Figura obtida deste artigo sobre estruturas de dados em Python

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 sort, 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 <list>

using namespace std;

int main() {
  list<int> numeros;

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

  // ordena a lista
  numeros.sort();

  // mostra o conteúdo da lista
  for (auto & x: numeros) {
    cout << x << endl;
  }

  cout << endl;
}

Como o método sort 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

A operação sort depende da comparação de precedência dos dados contidos numa lista. Isso pode ser feito usando o operador < para o tipo desses dados (caso exista), ou uma função de comparação específica para essa finalidade. O 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, ou deve existir uma função para fazer essa comparação.

O caso mais simples envolve escrever uma função que compare valores do tipo de dados em questão. O exemplo a seguir mostra como essa função deve ser declarada, e depois como ela pode ser utilizada para fazer o ordenamento.

// compara duas strings de acordo com seus comprimentos
bool comp_comprimento(cons string & s1, const string & s2) {
  return s1.size() < s2.size();
}

int main() {
  list<string> l;

  l.push_back("banana");
  l.push_back("caju");
  l.push_back("laranja");
  l.push_back("cajamanga");

  // ordena lista de string de acordo com comprimentos das string
  l.sort(comp_comprimento);

  // mostra conteúdo da lista na tela
  for (auto & w: l) {
    cout << w << endl;
  }
}

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: verifica se "este" < "outro"
   }
   

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.

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

#include <iostream> #include <string> #include <list> using namespace std; // 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; } }; int main() { list<Alguem> l; Alguem joao("Joao", 20); l.push_back(joao); Alguem x1("Amanda", 15); l.push_back(x1); Alguem x2("Gabriel", 19); l.push_back(x2); l.push_back(Alguem("Isadora", 18)); l.push_back(Alguem("Gustavo", 18)); // ordena a lista l.sort(); // mostra a lista ... for (auto & pessoa: l) { cout << pessoa.nome << ": " << pessoa.idade << endl; } cout << endl; }

Exemplo do operador< como uma função

#include <iostream> #include <string> #include <list> using namespace std; // 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 & este, const Alguem & outro) { if (este.idade == outro.idade) { return este.nome < outro.nome; } return este.idade < outro.idade; } int main() { list<Alguem> l; Alguem joao("Joao", 20); l.push_back(joao); Alguem x1("Amanda", 15); l.push_back(x1); Alguem x2("Gabriel", 19); l.push_back(x2); l.push_back(Alguem("Isadora", 18)); l.push_back(Alguem("Gustavo", 18)); // ordena a lista l.sort(); // mostra a lista ... for (auto & pessoa: l) { cout << pessoa.nome << ": " << pessoa.idade << endl; } cout << endl; }

Inversão

A inversão da lista, implementada pela operação reverse, 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).

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

using namespace std;

int main() {
  list<int> numeros;

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

  // ordena a lista
  numeros.sort();

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

  // apresenta a lista
  for (auto & x: numeros) {
    cout << x << 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

Curiosidade: contando quantas vezes cada valor existe em uma lista

Em um projeto sobre estatísticas sobre filmes e atores, ralizado em 2019.2, o requisito "listar os atores que mais atuaram, por ordem decrescente de atuações em filmes" poderia ser resolvido de mais de uma maneira. Uma abordagem é criar uma lista contendo todos os nomes de atores que atuaram nos filmes, de forma que, se um ator trabalhou em três filmes, seu nome apareceria três vezes nessa lista. Basicamente isso implica listar os atores de cada filme, e acrescentá-los a essa nova lista. Ao final, bastaria contar quantas vezes cada ator aparece na lista.

Ao menos dois algoritmos podem ser pensados para esse problema:

1. Para cada ator da lista, iterar a lista para contar quantas vezes seu nome aparece. Há que cuidar para realizar essa procura somente para a primeira vez em que cada ator é avaliado.
2. Ordenar a lista de atores, e então iterá-la. Os nomes de atores ficarão contíguos, o que facilita contá-los. Se o próximo ator da iteração for diferente do anterior, então registra-se a contagem do ator anterior e reinicia-se o contador.

Qual dos dois algoritmos é melhor, do ponto de vista de custo computacional (tempo para que concluam) ? O gráfico abaixo responde essa questão !

Custo computacional dos algoritmos para contar valores repetidos em uma lista, para listas de números inteiros

Uma alternativa à lista: vetor dinâmico

A STL apresenta uma outra estrutura de dados linear chamada vector. Essa estrutura se apŕesenta como um vetor dinâmico, em que dados são armazenados de forma parecida com um vetor, porém cuja área de armazenamento em memória pode ser expandida automaticamente. Em vector, os dados estão sempre contíguos em memória. Um vector usa uma área de memória capaz de guardar a quantidade de dados armazenados, estando os dados gravados sequencialmente ali dentro. A figura a seguir mostra como um vector usa memória para armazenar dados.

Um vector com alguns dados armazenados

Em geral, vector é adequado quando os dados são armazenados e removidos do final da área de armazenamento, e também quando se precisam acessá-los diretamente (por suas posições) e/ou aleatoriamente. Com list é o contrário, pois ela é adequada quando dados precisam ser inseridos e removidos de qualquer posição. Cabe ao programador escolher a estrutura mais adequada em cada situação. Os pontos listados a seguir buscam esclarecer melhor o que está em jogo.

• Com list, não é necessária 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. No caso de vector, a localização dos dados em memória está diretamente ligada a suas posições na área de armazenamento.
• Com list 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.
• Com vector podem-se indexar os dados, acessando-os diretamente por suas posições, uma vez que suas localizações em memória podem ser calculadas em função de suas posições.
• Com list, acrescentar uma dado implica 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 quando se usa vector).
• 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 vector).

As operações que podem ser feitas em vector são parecidas com as operações de list.

• push_back: Adicionar um dado ao final
• insert: Inserir um dado em uma determinada posição
• erase: Remover um ou mais dados a partir de uma determinada posição
• front: Acessar o dado que está no início
• operador []: Acessar um dado em uma posição qualquer
• back: Acessar o dado que está no final
• size: Obter a quantidade de dados armazenados
• clear: Remover todos os dados (esvaziar)

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

#include <cstdlib>
#include <vector>
#include <iostream>
#include <string>

using namespace std;

void mostra_vetor(vector<string> & v) {
    // itera o vetor
    for (auto & dado: v) {
      cout << dado << ",";
    }
    cout << endl;
}

int main(int argc, char** argv) {
    // cria um vector de string
    vector<string> nomes;
    
    // anexa três dados ao final do vector
    nomes.push_back("manuel");
    nomes.push_back("maria");
    nomes.push_back("bilica");
    
    // mostra comprimento e conteúdo do vector
    cout << "Comprimento: " << nomes.size() << ", dados: ";
    mostra_vetor(nomes);

    // Acessa um dado por sua posição
    for (int i=0; i < v.size(); i++) {
      cout << "Dado na posição " << i << ": " << nomes[i] << endl;
    }

    // remove dado do final do vector
    nomes.pop_back();
    cout << "Comprimento: " << nomes.size() << ", dados: ";
    mostra_vetor(nomes);
    
    // ao final, vector é automaticamente destruído, e a memória utilizada
    // é liberada
    return 0;
}

Nem tudo que se pode fazer com list está disponível em vector:

• Ordenamento: não há uma operação de ordenamento para vector, porém é possível ordená-los por meio de um algoritmo existente na STL.
• Embaralhamento: não existe uma operação para embaralhar os dados em um vector, mas também há um algoritmo para essa finalidade na STL.
• Reversão: não há operação para inverter as ordens dos dados, o que também depende de um algoritmo da STL.
• ... e algumas outras operações de list !

Por fim, assim como emlist, iteradores são úteis para acessar dados e percorrer vector.