terça-feira, 19 de novembro de 2013

Matemática de Ponteiros

Hoje vou tratar de um tema que aflinge a maioria dos programadores iniciantes em C e C++: os malvados ponteiros. O objetivo é fazer uma revisão do assunto tratando algumas propriedades que podem passar despercebidas do iniciado, mas que fazem toda a diferença na hora de compreender aquele "bug maluco" que aparece de vez enquando. Entender a fundo como funcionam os ponteiros pode ser a diferença entre passar dias ou meses debugando um código para nunca achar aquele erro, ou escrever um código menos suceptível a erros logo de cara.

Bom, para começar, o que é um ponteiro afinal? Um ponteiro nada mais é do que uma variável que contém um endereço de memória. O que muda de ponteiro para ponteiro é o significado deste endereço. 

O ponteiro é representado pelo símbolo asterísco (*). Também vamos utilizar bastante o operador de endereço (&), que retorna o endereço de memória de uma variável.

Vamos começar com alguns exemplos básicos para ilustrar:

#include <iostream>

using namespace std;

int main()
{
  int  a = 0; // Declaração de uma variável tipo int
  int  *p;    // Declaraçào de um ponteiro para uma variável inteira
  p = &a;     // Atribui a p o endereço de a

  cout << " a = " <<  a << "\t\t *p = " << *p << endl;
  cout << "&a = " << &a << "\t  p = "   <<  p << endl;
  cout << endl;

  return 0;
}

A saída esperada deste programa é a seguinte (os endereços vão variar de máquina para máquina):

 a = 0           *p = 0
&a = 0x28fef4     p = 0x28fef4

O objetivo deste exemplo é mostrar a operação normal com ponteiros. Na primeira parte, declaramos uma variável inteira "a" inicializada com o valor zero e um ponteiro "p" para um inteiro. Na seqüência, fazemos a atribuição do endereço de "a" ao ponteiro "p". Em seguida, utilizamos a saída padrão para mostrar que "p" e "a" são duas visões do mesmo dado, dadas as seguintes ressalvas:

1) para enxergarmos o valor armazenado em "a", basta referenciar a variável pelo nome.
2) para enxergarmos o endereço de "a", precisamos utilizar o operador de endereço &.
3) para enxergarmos o valor que "p" aponta, precisamos desreferenciar o ponteiro, com o operador *.
4) para enxergarmos o endereço contido em "p", basta referenciar "p" pelo nome.

Note que, na observação 4, falamos sobre o "endereço contido em p", e não "o endereço de p". Eu fiz essa diferenciação de propósito, pois "p" também é uma variável que está armazenada no seu próprio endereço. Vamos ver o exemplo modificado:

int main()
{
  int  a = 0; // Declaração de uma variável tipo int
  int  *p;    // Declaraçào de um ponteiro para uma variável inteira
  p = &a;     // Atribui a p o endereço de a

  cout << " a = " <<  a << "\t\t *p = " << *p << endl;
  cout << "&a = " << &a << "\t  p = "   <<  p << endl;
  cout << endl;

  cout << "&p = " << &p << endl;

  return 0;
}

Observe a saída:

 a = 0           *p = 0
&a = 0x28fefc     p = 0x28fefc

&p = 0x28fef8

Basicamente, o valor de "p" é o endereço de "a" (0x28fefc), e o endereço de "p" (0x28fef8) é o local da memória onde está guardado este valor.

Além disso, quando declaramos "p" não atribuímos nenhum valor a ele. Assim como qualquer outra variável declarada sem valor, ele irá conter neste momento um "lixo" qualquer. Considerando que este lixo pode ser um endereço válido, usar este ponteiro sem atribuir-lhe o valor correto pode ter conseqüências catastróficas como os lendários bugs não-determinísticos. Por este motivo, é uma boa prática ao declarar ponteiros sem valor atribuir-lhe o valor zero ou NULL (NULL = 0), pois os sistemas operacionais modernos são capazes de lançar exceções (null pointer exception) quando tentamos acessar o endereço zero, mas eles não necessariamente conseguem diferenciar um endereço "lixo" válido de um endereço "bom" e, acredite, é muito melhor varrer o código em busca de um null pointer exception do que de um erro aleatório.

int *p = NULL; // Sempre!

Uma última observação antes de seguir no tema, ainda dentro da parte básica, é com relação a declaração dos ponteiros. Você observou que o operador * tem duplo significado: se utilizado na declaração da variável, ele nos diz que a variável é um ponteiro, e; se utilizado no escopo do programa, em uma variável de ponteiro, ele nos diz que queremos desreferenciar o ponteiro, ou seja, utilizar o valor para o qual ele aponta, ao invés do seu próprio valor (que é um endereço).

Agora, pensando nisso, como fazemos para declarar vários ponteiros em uma única linha? Num primeiro momento, pensando em variáveis normais, declaramos assim:

int a, b, c;

Então, por conseqüência, declarar ponteiros deve ser igual, certo?

int* p, q, r;

Errado! Na verdade, o operador * faz parte do nome da variável, e não do tipo. Embora seja correto escrever tanto int* p como int *p (mudou apenas a posição do espaço), o * é considerado parte do nome e, portanto, a declaração acima irá produzir um ponteiro para um inteiro "p" e duas variáveis inteiras "q" e "r". A declaração correta é:

int *p, *q, *r;

Uma forma de demonstrar isto seria com o seguinte código:

int main() {
  char* c, d, e;

  cout << "sizeof: c = " << sizeof(c) << " d = " << sizeof(d) << " e = " << sizeof(e) << endl;

  return 0;
}

Saída:

sizeof: c = 4 d = 1 e = 1

Escolhi um tipo char desta vez por que com tipos inteiros não veríamos diferenças no sizeof. Uma maneira de corrigir este problema, além de declarar todos os ponteiros com o devido operador *, seria utilizar um typedef:

typedef char* CharPtr;

int main() {
  CharPtr c, d, e;

  cout << "sizeof: c = " << sizeof(c) << " d = " << sizeof(d) << " e = " << sizeof(e) << endl;

  return 0;
}

Saída:

sizeof: c = 4 d = 4 e = 4

Logo, o typedef garante que todas as variáveis sejam do mesmo tipo.

Equivalência com Arrays

Antes de entrar mais a fundo nas operações com ponteiros, existe uma última questão de sintaxe que vale a pena ser mencionada: a equivalência com arrays. Um array em C/C++ é declarado da seguinte forma:

int a[N];

Onde "a" é o nome do array e "N" é o seu tamanho.

Uma das propriedades do array é que, se utilizarmos apenas o seu nome, sem um índice referenciado, estamos tratando do endereço do primeiro elemento do array. Veja:

int main()
{
  int  a[10] = {0,1,2,3,4,5,6,7,8,9}; // Declaração de uma variável tipo array de int com tamanho 10

  cout << " a[0] = " << a[0] << "\t\t &a[0] = " << &a[0] << endl;
  cout << " a    = " << a    << "\t &a    = " << &a    << endl;
  cout << endl;

  return 0;
}

Saída:

 a[0] = 0                &a[0] = 0x28fed8
 a    = 0x28fed8         &a    = 0x28fed8


Na primeira linha pedimos para imprimir o valor do primeiro elemento (a[0]) e o endereço do primeiro elemento (&a[0]). Na linha seguinte, utilizamos duas notações equivalentes: tanto "a" como "&a" trazem o endereço do primeiro elemento.

Operações com Ponteiros

Espero que esteja tudo tranquilo até agora, pois agora vamos entrar na parte mais complexa. Lembra que o valor de um ponteiro é um endereço, certo? Então observe o seguinte:

int main() {
  int       *a = 0;
  char      *b = 0;
  long long *c = 0;
  float     *d = 0;
  double    *e = 0;

  cout << "sizeof:\n a = " << sizeof(a) << " *a = " << sizeof(*a) << endl
              << " b = " << sizeof(b) << " *b = " << sizeof(*b) << endl
              << " c = " << sizeof(c) << " *c = " << sizeof(*c) << endl
              << " d = " << sizeof(d) << " *d = " << sizeof(*d) << endl
              << " e = " << sizeof(e) << " *e = " << sizeof(*e) << endl;

  return 0;
}

Saída:

sizeof:
 a = 4 *a = 4
 b = 4 *b = 1
 c = 4 *c = 8
 d = 4 *d = 4
 e = 4 *e = 8

Ou seja, embora os tipos de dados que estes ponteiros apontem são totalmente distintos, os tamanhos dos ponteiros são exatamente os mesmos: 4 bytes. Isto se deve ao fato de que eu estou compilando este programa em modo 32 bits (4 bytes * 8 bits = 32 bits) e, portanto, todos os endereços estão dentro deste espaço. Note que se estivéssemos compilando em 64 bits, cada ponteiro teria 8 bytes.

Além disso, tanto em 32 bits como 64 bits nós conseguimos endereçar toda a memória como um bloco contínuo, mas se voltarmos um pouco no tempo e pensarmos em programas de 16 bits, isso não é totalmente verdade. Os processadores x86 em modo 16 bits utilizam uma forma mais complexa de endereçamento, composta por segmentos e offsets que compõem um endereço efetivo de 24 bits. Não vou entrar no detalhe, mas fica aqui como uma curiosidade para quem quiser pesquisar um pouco mais.

Para começar a trabalhar com operações em ponteiros, vamos trabalhar com a associação com arrays, pois desta forma estaremos trabalhando dentro de um espaço válido de endereçamento. Estas operações são possíveis em qualquer ponteiro, mas lembre-se sempre que a responsabilidade destas operações é totalmente do programador, o compilador não tem como checar se os limites estão sendo respeitados ou não, e bugs bizarros podem acontecer. Usando o array sabemos que temos o controle dos endereços de memória dentro daquela faixa.

A primeira operação é a adição:

int main() {
  int a[10] = {0,1,2,3,4,5,6,7,8,9};

  int *p = a;

  cout << "p = " << p << " *p = " << *p << endl;

  p = p + 1;

  cout << "p = " << p << " *p = " << *p << endl;

  return 0;
}

Saída:

p = 0x28fed4 *p = 0
p = 0x28fed8 *p = 1

Note que somar 1 ao ponteiro não somou 1 ao endereço do ponteiro, mas sim 4. Por quê? Porque o compilador sabe que aquele ponteiro aponta para um inteiro que ocupa 4 bytes, e ao somar 1 você está pedindo para o compilador que quer o próximo elemento alinhado com aquele ponteiro.

Por exemplo, se fizessemos o mesmo com um tipo char:

int main() {
  char a[10] = {'0','1','2','3','4','5','6','7','8','9'};

  char *p = a;

  cout << "p = " << (void*) p << " *p = " << *p << endl;

  p = p + 1;

  cout << "p = " << (void*) p << " *p = " << *p << endl;

  return 0;
}

Saída:

p = 0x28fef2 *p = 0
p = 0x28fef3 *p = 1

A diferença entre os endereços é apenas 1 byte, ou o tamanho do char.

Que outras operações são válidas em ponteiros? Basicamente todas operações relacionadas a adição e subtração:

int main() {
  int a[10] = {0,1,2,3,4,5,6,7,8,9};

  int *p = a;

  cout << "p = " << p << " *p = " << *p << endl;

  p++;
  ++p;

  cout << "p = " << p << " *p = " << *p << endl;

  p--;
  p -= 1;
  p += 3;

  cout << "p = " << p << " *p = " << *p << endl;

  return 0;
}

Saída:

p = 0x28fed4 *p = 0
p = 0x28fedc *p = 2
p = 0x28fee0 *p = 3

Sempre observando que o tamanho da variável apontada pelo ponteiro tem efeito direto nos cálculos dos endereços.

Note que, o endereço de um elemento "N" no array será sempre:

e = e0 + N * sizeof(T)

Onde "e0" é o endereço inicial do array e "T" é o tipo de dado do array.

Seguindo esta lógica, podemos ver que o operador [] nada mais é do que um operador de endereçamento, que abstrai estes cálculos para o programador.

Para testar assertiva, vamos fazer o seguinte (cuidado!):

int main() {
  int *p = 0;

  cout << "&p[1] = " << &p[1] << endl;
  cout << "&p[2] = " << &p[2] << endl;
  cout << "&p[3] = " << &p[3] << endl;
  cout << "&p[4] = " << &p[4] << endl;

  return 0;
}

Saída:

&p[1] = 0x4
&p[2] = 0x8
&p[3] = 0xc
&p[4] = 0x10

Note que mesmo declarando a variável "p" como um ponteiro (e não um array), podemos utilizar normalmente o operador []. O importante aqui é ressaltar que embora o programa tenha calculado os endereços corretamente, qualquer tentativa de acessar este espaço de memória pode ser desastrosa (por isso estou apenas imprimindo os endereços, não faço nenhum acesso a valor), logo, todo cuidado é pouco!

Conclusões

O meu objetivo com este artigo era fazer um panorama geral de operações com ponteiros. Eu acredito que uma vez que fique claro que trabalhando com ponteiros estamos trabalhando com endereços de memória grande parte da "mística" que envolve os ponteiros se desfaz e eles deixam de ser instrumentos obscuros para se tornarem ferramentas poderosas para o programador.

Como nota mental, fico devendo alguns tópicos interessantes para uma próxima edição deste artigo: chamadas de funções com ponteiros, arrays de arrays e ponteiros de funções.

segunda-feira, 18 de novembro de 2013

A máquina do tempo (para a internet)

A inspiração de escrever este post veio do seguinte video:


Basicamente, é uma apresentação de 10 minutos sobre como obter informações históricas da internet como tendências, métricas e etc, a partir de duas tecnologias: o HTTP Archive e o Big Query.

Isso me lembrou um "recurso" da internet que pouca gente conhece, e que por sinal é o irmão mais velho do HTTP Archive: o Internet Archive, mais especificamente a Wayback Machine. Enquanto o HTTP Archive tem o objetivo de armazenar, basicamente, metadados sobre as páginas da internet, a Wayback Machine armazena páginas da web completas. Ou seja, é possível, através de uma consulta a Wayback Machine, visualizar uma página hoje como ela era há anos atrás.

A Wayback Machine existe desde 1996 e têm algumas páginas realmente antigas. Por exemplo, eu consegui achar minha lista de item da minha antiga coleção de video games (que infelizmente não existe mais) com um snapshot de 2004:


Porém, se eu for mais para trás, consigo achar versões dela até 1999! Além disso, domínios mortos também podem ser vistos... o próprio SWI onde eu hospedava esta listagem não existe mais. Alguns sítios muito conhecidos e usados no passado como GeoCities e NBCI também podem ser acessados... é literalmente um museu em forma online, o que não poderia ser mais apropriado para a internet! :)

Agora, uma coisa que me deixa intrigado é, se existe uma forma de consolidar o Big Query com o HTTP Archive, será que não existiria uma forma de fazer o mesmo com o Internet Archive? Ou seja, pegar os dados históricos da Internet nos últimos 27 anos (1996-2013) e fazer análises (Hadoop?) para extrair dados históricos sobre a evolução da internet como um todo? Pelo que eu vi a facilidade de fazer isso com o Big Query se deve ao fato de que os dados do HTTP Archive já estão estruturados em bases MySQL (o Biq Query roda uma versão customizada do MySQL pelo Google), porém não encontrei uma forma de fazer o mesmo com a Wayback Machine, imagino que os dados não estejam realmente disponibilizados em nenhum formato similar, embora existam algumas APIs para consultas:


Enfim, fica aí um desafio para as próximas gerações... eu particularmente adoraria meter a mão na massa num projeto de pesquisas desse, mas infelizmente no momento tenho outras prioridades. Quem sabe um dia. De qualquer forma, fica aí a dica para quem quiser dar uma espiada no passado da web.

quarta-feira, 13 de novembro de 2013

Estruturas de Dados - Listas Encadeadas

Eu estou atualmente estudando uma série de principios básicos da engenharia de software em geral, començando desde estruturas de dados e algorítmos até conceitos mais complexos como inteligência artificial e programação de sistemas.

Para aproveitar esta nova tendência, estou abrindo uma nova série de artigos, focando inicialmente em Estruturas de Dados e, futuramente, devo abordar outros temas seguindo esta linha. A idéia é, na verdade, ser menos conceitual e focar mais nos aspectos de implementação de cada estrutura.

Como linguagem de programação estou escolhendo o C++, por questões de familiaridade. Também vou optar por trabalhar com programação genérica (templates) sempre que possível. Como eu sou old school e fiquei algum tempo sem programar, ainda não me adaptei ao C++11, então a maioria dos meus códigos é baseada no C++98. Pretendo utilizar novas features do C++11 a medida que eu for dissecando cada uma delas.

Como IDE e compilador estou utilizando o Code::Blocks com gcc para Windows. Por questões particulares estou sem acesso a um Linux neste momento, mas apenas para ficar registrado, minha preferência pessoal sempre foi pelos Debian-like, como por exemplo, o Ubuntu, embora a interface Unity não me agrada muito e por isso troquei pelo Mint.

Em termos de padrão de codificação, estou procurando seguir o mais próximo possível o Google C++ Style Guide. Digo o mais próximo possível porque ainda não tenho o domínio completo deste estilo e alguns hábitos são difíceis de se perder. Mas estou me esforçando neste caminho.

Bom, chega de preeliminares, vamos ao que interessa: listas encadeadas!

Listas Encadeadas


Listas Encadeadas são estruturas de dados dedicadas para o armazenamento de listas maneira análoga ao array, nativo da maioria das linguagens de programação, porém com algumas características particulares. O array, por definição, é uma coleção de valores de um mesmo tipo de variável num espaço contiguo de memória. Já a lista encadeada, por sua vez, não necessita uma alocação necessariamente contigua, embora possa ser. 

O principio básico de uma lista encadeada é ser uma estrutura de dados onde cada elemento possui (pelo menos) um indice, ponteiro ou referência para o seu sucessor. As listas encadeadas podem ser tanto estáticas como dinâmicas, sendo que as listas estáticas tem um tamanho pré-definido no momento de sua alocação e geralmente são implementadas com arrays.

As listas dinâmicas, por sua vez, possuem a capacidade de alocar memória para os novos elementos sob demanda, bem como liberar memória toda vez que um elemento é apagado. Logo, elas possuem a vantagem de não necessitarem alocar toda a memória no seu primeiro uso e o programador não precisa conhecer o seu tamanho máximo no momento da compilação.

Neste artigo vou tratar especificamente das listas encadeadas dinâmicas, pois vejo pouca vantagem de listas encadeadas estáticas com relação aos arrays, tirando o aspecto didático.

A implementação mais simples de uma lista encadeada dinâmica é a seguinte:

struct ListNode {
  ListNode* next_;
  void*     data_;
};

Neste caso estamos assumindo uma implementação com ponteiros, sendo next_ o ponteiro para o próximo nó e data_ o conteúdo do nó. Claro que nesta estrutura minimalista não estamos considerando as funções para realizar as operações na lista, as quais numa linguagem estruturada como o C justamente implementamos como funções isoladas. 

No C++, com a facilidade de se trabalhar com classes, é muito comum implementarmos as listas como "listas gerenciadas" (std::list é um exemplo de lista gerenciada), onde uma classe manager engloba todas as funções e controles necessários para manter a lista, abstraindo o que muitas vezes é uma interface complexa.

Uma última classificação sobre listas encadeadas dinâmicas é que elas podem ser simples, ou duplamente encadeadas. Listas simples permitem navegação unidirecional, de head para tail, enquanto que as listas duplamente encadeadas permitem navegação bidirecional. Neste primeiro artigo iremos começar com a lista simples, deixando a lista dupla para futuros artigos.

Uma implementação minimalista da classe gerenciadora segue abaixo:

struct List {
  List() : head_(NULL) {}
  ~List() {
   while( head_ ) {    
     ListNode* del_me = head_;
     head_ = head_->next_;
     delete del_me;
   }
  }

  void PushBack(ListNode* node) {
    if( !head_ )
      head_ = node;
    else {
      ListNode* i = head_
      for(; i->next_; i = i->next_) {}
      i->next_ = node;
    }
  }

  ListNode* head_;
};

Note que estamos tratando apenas a inserção de elementos no fim da lista, utilizando o método PushBack. Além disso, uma vez inserido o elemento na lista estamos passando o ownership do objeto ListNode para a lista, ou seja, cabe a lista, em seu destrutor, liberar a memória alocada para os nós. Em um list manager mais robusto, normalmente não queremos tratar a inserção a nível de ListNode, mas sim queremos inserir diretamente o tipo de dado que a lista armazena, como exemplo do push_back() da std::list. Veremos isto mais adiante na implementação.

Antes de partir para a implementação propriamente dita gostaria de comentar sobre algumas características das listas encadeadas dinâmicas em comparação com os arrays.

O primeiro ponto é a performance de busca. Em um array, por se tratar de uma área de memória contigua, a busca de um elemento pelo seu índice é uma operação de tempo constante, ou O(1) em notação big-O. Já numa lista encadeada é uma operação O(n), pois dado uma posição i precisamos partir do nó head e varrer i elementos para encontrar o nosso candidato (considerando o head como i = 0). No array essa indexação é direta, pois, supondo uma posição i, o endereço de memória do elemento alvo pode ser calculado facilmente pela equação endereco = &array + i * sizeof( array[0] ). Nota: Este cálculo é feito automaticamente quando utilizamos a notação de arrays: a[i].

Nos arrays, a inserção também é uma operação em tempo constante O(1), porém não existe um mecanismo nativo para deleção, pois uma vez alocado o espaço ele fica alocado até sair de escopo. Isto geralmente implica em algum tipo de controle adicional caso haja necessidade de representar espaços em branco no array, o que se for o caso pode ser obtido em tempo constante O(1) (por exemplo, atribuir um valor -1 em um array onde se espera apenas números inteiros positivos). Nas listas encadeadas tanto a inserção como a deleção são O(n), pelo mesmo motivo da busca, e a deleção de fato ocorre liberando memória.

Finalmente, uma busca por valor tem performance de O(n) em ambos os casos, pois sempre haverá necessidade de percorrer toda a lista ou todo o array no pior caso.

Implementação de uma Lista Encadeada Dinâmica

Para fins de brevidade, estou tomando como referência a implementação de lista dinâmica encadeada da danicat, disponível em https://gist.github.com/danicat/7049073. Vou comentar passo a passo esta implementação.

template<class T>
class Element {
 public:
  Element(const T& value) : data_(value), next_(NULL) {}
  ~Element() {}

  void        SetValue(const T& value) { data_ = value; }
  const T&    GetValue() const { return data_; }
  void        SetNext(Element<T>* next) { next_ = next; }
  Element<T>* GetNext() const { return next_; }

  void        Print() const { std::cout << data_ << std::endl; }

 private:
  Element();  // Prevent calling the default ctor

  T           data_;
  Element<T>* next_;
};

Primeiro nós definimos o elemento ou nó que irá armazenar os valores. Se comparado com a nossa implementação minimalista logo acima pouco mudou: adicionou-se o construtor e destrutor, os métodos getters e setters para as propriedades do elemento e um método Print() para fins diagnósticos.

Outra mudança, esta sim significativa, foi a abstração do elemento utilizando um template. Esta é uma abordagem mais eficaz do que definir o dado como um void* como fizemos na implementação minimalista. Também declarou-se o construtor padrão como privado, para evitar uma construção de um elemento sem conteúdo.

Em seguida, define-se a classe manager que irá concentrar todas as funcionalidades da lista:

template <class T>
class List {
 public:
  List(): head_(NULL), tail_(NULL) {}
  ~List();

  bool PushFront(const T& value);
  bool PushBack (const T& value);
  bool PopFront(T* value);
  bool PopBack (T* value);

  int  Length() const;
  void Print() const;

  bool Insert(const T& value, const int& position);
  bool Delete(const int& position);

  int  Find(const int& value) const;
  bool Get (const int& position, T* value);

 private:
  Element<T>* head_;
  Element<T>* tail_;
};

Esta classe também pode ser chamada de container, pois ela contém os elementos da lista. A principio ela só precisaria de ter um ponteiro para o primeiro elemento da lista, o head_, porém, uma otimização comum é também manter um ponteiro para o final da lista, o tail_. No estando inicial ambos os ponteiros são nulos e a lista está vazia. A medida que são inseridos e removidos elementos na lista, estes ponteiros precisam ser atualizados.

As primeiras operações implementadas são as operações Push() e Pop(). Estas operações para quem já estudou pilhas são bem familiares. Push() é a operação de colocar um valor numa pilha, e Pop() é a operação de retirar. Operações em pilhas sempre são feitas em uma das suas extremidades, mas como estamos tratando de listas e não pilhas é conveniente utilizar a mesma analogia para inserir e retirar elementos das extermidades. Logo, PushFront() e PopFront() vão inserir e retirar elementos do começo da lista, respectivamente, e PushBack() e PopBack() vão inserir e retirar elementos do fim da lista.

Esta implementação de caso particular é interessante porque são funções de uso bastante comum. Muitas vezes não queremos nos preocupar com a ordem dos elementos que estamos inserindo, queremos apenas extender a lista, situação em que um PushBack(), por exemplo, pode vir bem a calhar.

Em termos de performance, como mantemos um ponteiro para o tail da lista, inserir um elemento no fim da lista é uma operação de tempo constante, ou seja, O(1). O mesmo vale para inserir e remover elementos do começo da lista, pois operações no head também são tempo constante (Se não ficar claro o porque disto agora, talvez na implementação abaixo faça sentido). A única operação O(n) seria retirar um elemento do fim da lista, pois, precisamos atualizar o tail para o elemento tail - 1, mas não conseguimos saber qual elemento aponta para tail sem varrer toda a lista. Note que isto é uma ressalva apenas para listas simples, numa lista duplamente encadeada poderiamos partir do tail e encontrar o tail - 1 em tempo constante através do ponteiro de iteração reversa.

Segue a implementação das rotinas push e pop:

// O(1)
template <class T>
bool List<T>::PushFront(const T& value) {
  Element<T>* element = new( std::nothrow ) Element<T>(value);

  if( element ) {
    if( !head_ ) {
      // Special case, list is empty
      head_ = element;
      tail_ = element;
    }
    else {
      element->SetNext(head_);
      head_ = element;
    }
    return false;
  }
  else {
    return true; // Error allocating memory
  }
}

// O(1)
template <class T>
bool List<T>::PushBack(const T& value) {
  Element<T>* element = new (std::nothrow) Element<T>(value);

  if( element ) {
    if( !head_ ) {
      // Special case, list is empty
      head_ = element;
      tail_ = element;
    }
    else {
      tail_->SetNext(element);
      tail_ = element;
    }
    return false;
  }
  else {
    return true;
  }
}

// O(1)
template <class T>
bool List<T>::PopFront(T* value) {
  if( value && head_ ) {
    *value = head_->GetValue();

    Element<T>* new_head = head_->GetNext();
    delete head_;
    head_ = new_head;

    return false;
  }
  else
    return true; // Error: nullptr passed as parameter or list empty
}

// O(n)
template <class T>
bool List<T>::PopBack(T* value) {
  if( value && tail_ ) {
    *value = tail_->GetValue();

    // Special case: one element list
    if( head_ == tail_ ) {
      delete head_;
      head_ = NULL;
      tail_ = NULL;
    }
    else {
      Element<T>* new_tail;

      new_tail = head_;

      while( new_tail->GetNext() != tail_ ) // Skip elements till the element before tail
        new_tail = new_tail->GetNext();

      new_tail->SetNext(NULL);
      delete tail_;
      tail_ = new_tail;
    }
    return false;
  }
  else
    return true; // Error: nullptr passed as parameteror list empty
}

Em seguida temos algumas funções auxiliares, também de ordem O(n), Lenght() que retorna o tamanho da lista e Print() que imprime os valores da lista. Estas são operações O(n) porque não há outra forma de realizá-las sem varrer todos os elementos da lista.

// O(n)
template <class T>
void List<T>::Print() const {
  Element<T>* e;
  for(e = head_; e; e = e->GetNext() )
    e->Print();
}

// O(n)
template <class T>
int List<T>::Length() const {
  Element<T>* e;
  int count = 0;

  for(e = head_; e; e = e->GetNext() ) ++count;

  return count;
}

Note que uma otimização simples de Lenght() seria criar uma propriedade lenght no container e fazer com que todas as operações de inserção e remoção da lista incrementassem ou decrementassem este contador. Porém, dada a quantidade de operações que podem inserir ou remover elementos, tornaria-se uma otimização um pouco mais complicada de se manter, o que poderia induzir bugs.

Estou fazendo este comentário aqui porque, embora este seja um exercício conceitual, num código comercial decisões como esta podem afetar o esforço de manutenção do código drasticamente. Imagine, por exemplo, quantas vezes esta função vai ser chamada no código final e se vale a pena sacrificar a clareza do código em prol desta otimização. Esta é uma reflexão que deve acompanhar todas as decisões de design envolvendo otimizações.

A próxima operação, Insert(), é uma que demanda uma certa atenção, pois estamos trabalhando com inserção posicional.

// best O(1), avg O(n), wst O(n)
template <class T>
bool List<T>::Insert(const T& value, const int& position) {
  if( position < 0 )
    return true;

  if( !position ) // Special case: position = 0, insert into head
    return PushFront(value);

  Element<T>* element_before = head_;

  for(int count = 0; count < position - 1; ++count ) {
    element_before = element_before->GetNext();

    if( !element_before )
      return true; // Out of bounds
  }

  Element<T>* new_element = new (std::nothrow) Element<T>(value);
  if( !new_element )
    return true;

  new_element->SetNext(element_before->GetNext());
  element_before->SetNext(new_element);

  if( element_before == tail_ ) // Special case: insert at the end
    tail_ = new_element;

  return false;
}

Como era de se esperar, esta operação tem um best case O(1), pois inserir um elemento na posição zero se reduz a fazer uma chamada ao método PushFront(). O average case e worst case são ambos O(n), pois para as demais operações é preciso varrer toda a lista. Se soubessemos o tamanho da lista com antecedência poderiamos prever tentativas de inserir após o fim da lista em tempo constante, e também inserir no fim da lista em tempo constante, porém para isso temos que varrer toda a lista de qualquer forma chamando a função Length(), que tem tempo O(n).

Portanto, tomamos o cuidado de varrer a lista procurando a posição especificada mas sempre checando se não estamos ultrapassando o limite, situação que deve retornar erro.

O mesmo vale para a operação Delete():

template <class T>
bool List<T>::Delete(const int& position) {
  if( position < 0 )
    return true;

  if( !head_ )
    return true; // List empty

  Element<T>* target = head_;

  if( !position ) {// Special case: position = 0, delete head
    head_ = head_->GetNext();
    delete target;

    return false;
  }

  Element<T>* element_before = head_;
  for(int count = 0; count < position - 1; ++count ) {
    element_before = element_before->GetNext();

    if( !element_before )
      return true; // Out of bounds
  }

  target = element_before->GetNext();

  if( !target )
    return true; // Out of bounds

  element_before->SetNext(target->GetNext());

  if( target == tail_ )
    tail_ = element_before;

  delete target;

  return false;
}

Finalmente, as funções Find(), para buscar a posição de um valor na lista e, Get(), para retornar o valor em uma dada posição:

template <class T>
int List<T>::Find(const int& value) const {
  int position = -1;

  Element<T>* e = head_;

  for(int count = 0; e; e = e->GetNext(), ++count ) {
    if( e->GetValue() == value ) {
      position = count;
      break;
    }
  }

  return position;
}

template <class T>
bool List<T>::Get(const int& position, T* value) {
  if( position < 0 || !value )
    return true; // invalid input

  Element<T>* e = head_;

  for(int count = 0; e && count < position; e = e->GetNext(), ++count ) ;

  if( !e )
    return true;

  *value = e->GetValue();

  return false;
}

Ambas são operações O(n) para average e worst case, pois necessitam varrer a lista para encontrar os respectivos valores.

Claro que esta implementação não é exaustiva, e algumas simplificações e omissões foram feitas para torná-la mais didática. Na prática, estaríamos trabalhando preferencialmente com uma lista duplamente encadeada. Além disso, para ser um verdadeiro container comparável aos fornecidos pela biblioteca padrão, no mínimo deveríamos definir semânticas de cópia, move, atribuição e implementar operadores comuns como o de indexação [].

Enfim, espero que estes comentários ajudem, e na próxima vez pretendo dar continuidade ao assunto tratando de outras estruturas de dados.