Listasencadeadas

INF1007 – Programação 2

Tema 8 – Listas Encadeadas

04/11/09

(c) Dept. Informática - PUC-Rio

1

Tópicos Principais
• Motivação • Listas encadeadas • Implementações recursivas • Listas de tipos estruturados

04/11/09

(c) Dept. Informática - PUC-Rio

2

Tópicos Complementares
• Listas circulares • Listas duplamente encadeadas • Listas de tipos estruturados

04/11/09

(c) Dept. Informática - PUC-Rio

3

Motivação
• Vetor
– ocupa um espaço contíguo de memória – permite acesso randômico aos elementos – deve ser dimensionado com um número máximo de elementos

VETOR

04/11/09

(c) Dept. Informática - PUC-Rio

4

Motivação
• Estruturas de dados dinâmicas:
– crescem (ou decrescem) à medida que elementos são inseridos (ou removidos) – Exemplo:
• listas encadeadas:
– amplamente usadas para implementar outras estruturas de dados

04/11/09

(c) Dept. Informática - PUC-Rio

5

Listas Encadeadas lst Info1 Info2 Info3

...

InfoN

NULL

• Lista encadeada:
– seqüência encadeada de elementos, chamados de nós da lista – nó da lista é representado por dois campos:
• a informação armazenada e • o ponteiro para o próximo elemento da lista

– a lista é representada por um ponteiro para o primeiro nó – o ponteiro do último elemento é NULL
04/11/09 (c) Dept. Informática - PUC-Rio 6

Estrutura com ponteiro para ela mesma struct elemento { int info; ... void* prox; struct elemento* prox; }; typedef struct elemento Elemento;

info

info

04/11/09

(c) Dept. Informática - PUC-Rio

7

Exemplo: Lista de inteiros struct elemento { int info; ... void* prox; struct elemento* prox; }; typedef struct elemento Elemento;

• Lista é uma estrutura auto-referenciada, pois o campo prox é um ponteiro para uma próxima estrutura do mesmo tipo. • uma lista encadeada é representada pelo ponteiro para seu primeiro elemento, do tipo Elemento*
04/11/09 (c) Dept. Informática - PUC-Rio 8

Listas Encadeadas de