- Entrou
- Set 23, 2006
- Mensagens
- 1,690
- Gostos Recebidos
- 0
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:
vou só descrever o método que penso ser mais importante: insert().
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
TUT_IntSList
De seguida encontra-se a declaração da classe TUT_IntSList:
Na listagem está tudo comentadinho. Por isso para poupar espaço (e trabalhoclass 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;
};