Estrutura de dados

Lista Ligada (http://www.di.ufpb.br/liliane/aulas/listas.html – 2:59)
Listas ligadas ou encadeadas são conjuntos de elementos (nós) ligados, onde cada elemento contém uma ou mais ligações com um ou mais elementos da lista.

Cada um dos elementos de uma lista ligada é composto por duas partes: a primeira representa informação específica do elemento e a última representa conexões com outros elementos.

(Nó figura 1)

O primeiro e o último elementos (nós) de uma lista ligada ou encadeada são designados por cabeça e cauda respectivamente.

(Goodrich figura 3.10)

Características
A ordem dos elementos constituintes da lista pode ser diferente da sua ordem de armazenamento na memória;
As listas não tem tamanho fixo predeterminado;
O acesso de seus elementos é feito de forma sequencial;

Operações com listas
As listas possuem uma quantidade enorme de operações, entretanto, pelo facto de muitas da operações possuir natureza semelhante é possível dividí-las em três categorias principais, e tais categorias são:
Operação de inserção;
Operação de remoção;
Operação de consulta.

Operação de Inserção
A operação de inserção consiste em incluir novos elementos (nós) em uma lista, incluindo também a sua criação. A inserção de elementos numa lista pode ocorrer em três casos distintos nomeadamente:

Inserção de elementos no início da lista (antes do primeiro nó);
Inserção de elementos no fim da lista (depois do último nó);
Inserção de elementos no meio da lista (entre dois nós quaisquer).

Operação de Consulta
As operações de consulta constituem na verdade o encapsulamento de um conjunto de operações possíveis sobre listas, tais operações devem retornar informação corrente de uma dada lista. Para o presente caso, as operações destacadas serão:

Verificação da existência de algum elemento específico na lista;
Verificação da quantidade de elementos existentes na lista;

As demais operações de consulta são derivadas das operações acima citadas.