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. 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 estes exemplos:

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

O arquivo de projeto do Netbeans com a biblioteca Prglib

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

Outras operações da lista

A lista encadeada da Prglib ofere outras operações além daquelas para adicionar, obter e remover dados. Duas outras operações são de grande utilidade:

iteração: possibilita obter sucessivamente de forma eficiente os dados da lista;
ordenamento: ordena os dados de forma eficiente

Iteração

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 dos métodos inicia, proximo e fim. Esses métodos são usados em conjunto para acessar cada dado da lista sucessivamente, a partir do início da lista. O exemplo a seguir mostra como usá-los:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

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

  // inicia a iteração
  numeros.inicia();

  // enquanto não chegar ao fim da lista, continua a iteração
  while (not numeros.fim()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.proximo();

    cout << "Numero: " << algo << endl;
  }
}

Essa forma de percorrer os dados de uma lista é muito mais eficiente do que acessar os dados a partir de suas posições (usando o método obtem ou o operador []). Para ter uma ideia, percorrer uma lista com 10 dados é 10 vezes mais rápido com iteração. Se a lista tiver 100 dados, a iteração é 100 vezes mais rápida. Se a lista tiver 1000 dados, a uteração é 1000 vezes mais rápida, e assim por diante. O tempo que se leva para percorrer todos os dados com iteração é proporcional à quantidade de dados, porém se for usado o método obtem (ou operador []), o tempo necessário é proporcional ao quadrado da quantidade de dados.

A iteração pode ser feita também em sentido contrário se forem usados os métodos iniciaPeloFim, anterior, e inicio:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

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

  // inicia a iteração pelo fim da lista
  numeros.iniciaPeloFim();

  // enquanto não chegar ao início da lista, continua a iteração
  while (not numeros.inicio()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.anterior();

    cout << "Numero: " << algo << endl;
  }
}

Ordenamento da lista

A lista possui o método ordena, que ordena seus dados. O ordenamento é feito por um algoritmo com razoável eficiência, 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 <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

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

  // ordena a lista
  numeros.ordena();

  numeros.escrevaSe(cout);

  cout << endl;
}

Atividade

Faça estes exercícios que envolvem iteração:

... e estes sobre ordenamento:

PRG29003: Introdução a Listas

Índice

Atividade

Outras operações da lista

Iteração

Ordenamento da lista

Atividade

Menu de navegação

Pesquisa