Estruturas de Dados Lineares - Dinâmicas

EDs lineares dinâmicas são implementadas com listas encadeadas. Lista encadeada é aquela cujos elementos possuem apontadores para o próximo elemento (ou pode ter um pro anterior também... enfim, tem ponteiros). Essas listas são ótimas porque podem crescer ou diminuir em tempo de execução, porém a única maneira de acessar os itens é ir seguindo os links entre eles.
A definição de um nodo (célula da lista) é basicamente assim:
struct nodo {
   Item item; //pode ser qualquer coisa, meio que não interessa no momento
   struct nodo *prox; //note que a definição é recursiva

}
As listas podem ter nodos sentinela, que são células vazias opcionais colocadas no início e/ou fim da lista. Eles não contêm elementos válidos e são usados para simplificar as condições de limites. O nodo final sempre tem o valor null ou 0 ou aponta para um sentinela ou para o início da lista, tornando-a circular.

Implementação de uma lista linear simples com um nodo sentinela
● inicialização
lista = new nodo;
lista->prox = lista;

● testa lista vazia
(lista->prox == lista)

● insere t após x
t->prox = x->prox;
x->prox = t;

● remove nodo após x
t = x->prox;
x->prox = x->prox->prox;
delete t;

● loop para percorrer a lista:
t = lista->prox;
while (t!=lista) {
   t->item...; //operação
   t = t->prox;

}