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
A implementação de lista dinâmeica completa está 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_;
};
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.
Nenhum comentário:
Postar um comentário