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. 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:
Uma lista possui algumas características:
- 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 ou fim 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).
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 |
---|
/*
* File: lista.h
* Author: msobral
*
* Created on 11 de Agosto de 2016, 08:56
*/
#ifndef LISTA2_H
#define LISTA2_H
#include <cstddef>
#include <ostream>
#include <string>
#include <list>
#include <algorithm>
#include <random>
#include <memory>
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".
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 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:
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/*
* File: main.cpp
* Author: msobral
*
* Created on 20 de Fevereiro de 2017, 17:32
*/
#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