Alocaçao dinamica

Alocação Dinâmica - Listas Ligadas Mac122 – Marcilio – Revisado 16Set12

Alocação Dinâmica – Listas Ligadas
1. Listas seqüenciais versus listas ligadas Lista seqüencial Chamamos de lista seqüencial um conjunto de elementos contíguos na memória. Um vetor é o melhor exemplo de lista seqüencial. O elemento i é precedido pelo elemento i-1 e seguido pelo elemento i+1. Como os elementos são contíguos, para se acessar um elemento só é necessário o seu índice, pois o índice indica também o deslocamento a partir do início, onde se encontra o elemento. A vantagem é o acesso direto a qualquer dos elementos da lista. A desvantagem é que para inserir ou remover elementos, temos que deslocar muitos outros elementos. ..... (i-1) i (i+1) inserir remover ......

Listas Ligada Chamamos de lista ligada um conjunto de elementos onde cada elemento indica qual o próximo. Não existe contigüidade entre os elementos. Elementos vizinhos podem estar em posições físicas bem separadas. A vantagem é a flexibilidade na inserção e remoção de elementos. A desvantagem é que não temos acesso direto aos elementos. Não existe algo equivalente ao índice para se acessar diretamente o elemento. ..... .....

2. Listas ligadas - definições É um conjunto de itens, onde cada elemento contém uma informação e um ponteiro para o próximo item. Possui também um ponteiro para o seu início e o ponteiro do último elemento tem um valor especial (NULL). P (inicio)

Alocação Dinâmica - Listas Ligadas Mac122 – Marcilio – Revisado 16Set12

Alocação Dinâmica - Listas Ligadas Mac122 – Marcilio – Revisado 16Set12

O campo de informação pode conter qualquer tipo ou conjunto de tipos de elementos. O ponteiro para o próximo item é um ponteiro para um item do mesmo tipo. Exemplos: a) campo de informação = int:

struct item { int info; struct item *prox; } b) campo de informação = 2 ints e 1 double: struct novoitem { int i, j; double a; struct novoitem *prox; } c) campo de informação = vetor de char:

struct no