PRG29003: Introdução a Listas
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 de uma estrutura de dados usada em programas, uma lista encadeada se aparenta com isto:
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).
Algumas 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.
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
- Faça os exercícios sobre listas que estão no Moodle, para se familiarizar com listas