PRG29003: Introdução a Listas

• Um video introdutório da Khan Academy

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

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