Lista Simplesmente Ligada

Este é o exemplo mais simples de lista que conheço, uma lista simplesmente ligada. Não é a mais viável mas serve para apreender as bases de uma lista.
Mas o que é mesmo uma lista?... Num array todos os seus elementos estão dispostos na memória uns a seguir aos outros, numa lista, estão em posições completamente aleatórias.
Uma lista é composta por diversos nós, nós esses que são estruturas que contém a informação pretendida e um pointer para o nó seguinte. Na implementação da lista que vou aqui fazer, o último nó aponta sempre para NULL. Quando a lista é inicializada, o head aponta sempre para para NULL, tal como o tail. Esqueci-me de por o tail no desenho acima Quando a lista tem elementos, o head aponta sempre para o primeiro elemento da lista e o tail para o último.
TUT_IntSList

De seguida encontra-se a declaração da classe TUT_IntSList:

class TUT_IntSList {


// definição de Node
struct Node {
Node* next;
int data;
Node( Node* _next = NULL, int d = 0 )
: next(_next), data(d) {}
};


/* atributos privados */
Node* head;
Node* tail;
int sz;


/* métodos privados */
Node* newNode( int d = 0 ) const;


public:


TUT_IntSList();
~TUT_IntSList();


int size() const { return sz; }
void insert( int d );
int remove();
void clear();
void printOn( std:stream &os ) const;
};

Clique para expandir...

Na listagem está tudo comentadinho. Por isso para poupar espaço (e trabalho vou só descrever o método que penso ser mais importante: insert().

insert

void TUT_IntSList::insert( int d ) // insere à cauda
{
Node* novo = newNode(d); // criar um novo nó
if( tail->next != NULL ) // para o caso da lista estar vazia!
tail->next->next = novo; // o último nó passa a apontar para o novo
else head->next = novo; // head aponta para o primeiro


tail->next = novo; // actualizar tail
++sz; // acrescentar 1 ao tamanho da lista
}

Clique para expandir...

Penso que com os comentários se percebe bem, não me lembro de mais nada para dizer. Não esquecer que quando a lista é inicializada head->next = tail->next = NULL.
Na listagem tenho todo o código comentado como este que aqui passei, por isso penso que não é difícil de perceber.