PRG29003: A implementação da lista

Conforme visto na etapa 1, 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. Internamente, cada dado é armazenado em um elemento da lista denominado nodo, que funciona como uma caixa onde se guarda esse dado. Assim, para cada dado armazenado na lista existe um nodo. Cada nodo possui uma referência ao próximo nodo da lista, formando uma sequência parecida com os vagões de um trem. A figura abaixo ilustra uma lista encadeada:

Para se acessar uma lista, basta conhecer a referência para seu primeiro nodo (contida em seus atributos, como mostrado na figura acima). A partir do primeiro nodo pode-se percorrer a lista, seguindo as referências para os nodos subsequentes. Com isso, qualquer nodo da lista pode ser acessado.

Uma lista possui algumas propriedades:

• Os nodos são criados dinamicamente, à medida que for necessário. Assim, 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 nodos são alocados dinamicamente, eles podem ocupar áreas de memória arbitrárias, e não há nenhuma relação entre a localização dos nodos em memória e sua ordem na lista (novamente compare isso com um vetor ou matriz).
• Não é possível indexar os nodos, por isso para acessar um nodo deve-se obrigatoriamente procurá-lo a partir do início da lista, seguindo cada nodo até chegar àquele procurado.
• Para adicionar um nodo, basta modificar a referência do nodo que o antecede na lista. Assim, não é necessário "empurrar" os nodos seguintes para frente (como seria o caso de um vetor).
• Para remover um nodo é a mesma coisa: basta modificar a referência de seu nodo antecessor. Assim, não é necessário "deslocar pra trás" os nodos seguintes (como seria o caso de um vetor).

Listas simplesmente encadeadas

Um primeiro tipo de lista se chama simplesmente encadeada. Como diz seu nome, os nodos são encadeados de forma unidirecional. Pode-se percorrer a lista do primeiro em direção ao último nodo, mas não em direção contrária. A explicação apresentada na seção anterior focou nesse tipo de lista. Sua implementação no geral é mais simples.

Com base no que foi introduzido, a estrutura de dados lista pode ser definida da seguinte forma:

• atributos: pelo menos referências ao primeiro e ao último nodo
• operações: ao menos operações para adicionar, obter e remover dados da lista; mais especificamente:
  • 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

A tradução dessa definição para a linguagem C++ pode ser vista a seguir:

Declaração e implementação da lista como uma classe template

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 ~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 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". std::shared_ptr<lista<T>> procuraMuitos(const T &algo) const; 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 void inicia(); void iniciaPeloFim(); bool fim() const; bool inicio() const; T & proximo(); T & anterior(); // inverte a ordem dos dados da 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; private: // declaração do tipo Nodo: privativa, porque // é de uso exclusivo da lista // Este Nodo visa uma lista duplamente encadeada struct Nodo { Nodo * proximo, * anterior; T dado; // construtor do Nodo: prático para uso nos métodos // da lista Nodo(const T & algo) { dado = algo; proximo = nullptr; anterior = nullptr; } }; // ponteiros para primeiro e último nodos Nodo * primeiro, * ultimo; // ponteiro para nodo atual da iteração Nodo * atual; // comprimento da lista long len; }; Arquivo libs/lista.h

OBS: a implementação dos métodos da lista está em libs/lista-impl.h.

Uma vez implementada essa lista básica, ela pode ser testada com este programa:

Programa para testar a lista
#include <iostream> #include <string> #include <prglib.h> using prglib::lista; using namespace std; int main() { lista<string> list; list.anexa("Uma"); list.anexa("coisa"); list.anexa("legal"); cout << "Comprimento: " << list.comprimento() << endl; for (int pos=0; pos < list.comprimento(); pos++) { cout << "Posicao " << pos; cout << ": " << list.obtem(pos) << endl; } }

Outros modelos de listas

Listas encadeadas podem ser implementadas com algumas variações. Duas delas bem conhecidas são:

• Lista duplamente encadeada: cada nodo aponta seu sucessor e antecessor. Esse tipo de lista facilita operações de inserção e remoção de nodos.

• Lista com guardas: guardas são nodos que não contém dados, mas servem para marcar lugares de interesse da lista. O caso mais comum é usar guardas no início e fim da lista, o que facilita a implementação de operações de inserção e remoção de nodos, pois essas operações não precisam tratar os casos último nodo ou primeiro nodo. Esse tipo de lista pode ser simplesmente ou duplamente encadeada.

CURIOSIDADE: como um processo usa a memória

Um processo, que é um programa em execução, usa memória para guardar tanto seus dados (variáveis e constantes) quanto suas instruções (o programa em si). A forma com que cada processo ocupa a memória depende do sistema operacional. No caso do Linux, o diagrama abaixo mostra de forma simplificada como um processo se organiza em memória (maiores detalhes no link abaixo da figura, e nas disciplina de Sistemas Operacionais da 5a fase ... e Microprocessadores da 4a fase também ajuda a entender essa questão).

Anatomia de um processo em memória
(obtido de http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/)

Segundo esse diagrama, um processo aloca regiões de memória para diferentes finalidades. Por exemplo, as instruções de programa ficam no segmento Text, as variáveis dinâmicas alocadas com malloc (linguagem C) ou operador new (C++) ficam no segmento heap, e as variáveis locais e argumentos de função ficam em stack.

Experimento: alocação de memória

Compile e use os dois programas a seguir para comparar as limitações na alocação de memória na pilha e no heap.

• Alocação na pilha
• Alocação no heap

Atividade

Implemente as operações da lista necessárias para que o programa de teste funcione.

Operações que acrescentam e removem conteúdo

Como visto na [[PRG29003:_Introdução_a_Listas#A_lista_da_prglib|etapa 1], existem operações que acrescentam ou removem dados da lista. Uma delas já foi vista na introdução, que acrescenta um novo dado ao final da lista (operação anexa). Outras operações desse tipo comumente usadas são:

• insere: inserem um dado no início ou em uma posição qualquer
• remove: remove um dado de uma posição qualquer
• esvazia: esvazia a lista

Um exemplo de uso dessas operações pode ser vista neste pequeno programa:

#include <iostream>
#include <string>
#include <prglib.h>
 
using prglib::lista;
 
using namespace std;
 
int main() {
  lista<string> list;
 
  list.anexa("Uma");
  list.anexa("coisa");
  list.anexa("legal");
  list.insere("Mais");

  cout << "Comprimento: " << list.comprimento() << endl;
  for (int pos=0; pos < list.comprimento(); pos++) {
    cout << "Posicao " << pos;
    cout << ": " << list.obtem(pos) << endl;
  }
 
}

Outro programa de teste para a lista: anexa, insere, obtem, remove, esvazia

#include <iostream> #include <string> #include <prglib.h> using prglib::lista; using namespace std; void mostraLista(lista<string> & l) { int len = l.comprimento(); cout << "Comprimento: " << len << endl; int pos = 0; while (pos < len) { string algo = l.remove(0); l.anexa(algo); cout << "Posicao " << pos; cout << ": " << algo << endl; pos++; } } int main() { lista<string> l; l.anexa("coisa"); l.anexa("legal"); l.insere("Uma"); mostraLista(l); cout << endl; l.insere("muito", 2); mostraLista(l); cout << endl; string palavra = l.remove(2); cout << "Removeu: " << palavra << endl; mostraLista(l); cout << endl; l.esvazia(); cout << "Após esvaziar: " << endl; mostraLista(l); cout << endl; return 0; }

Atividade

Implemente as operações insere, remove e esvazia, de forma que os programas de teste funcionem.