Arvore

Universidade Tecnológica Federal do Paraná UTFPR

LT33B Estruturas de dados I

Listas Encadeadas Parte I:
Listas Encadeadas Simples
Prof. Juliano Henrique Foleiss

Até Agora...
Algoritmos de Ordenação
Algoritmos de Busca

Hoje...
Listas Encadeadas
Lista encadeada simples

Vetores
Até agora a única estrutura de dados estudada no curso é o vetor.
0
V:

1

2

3

4

5

6

7

D1

D2

D3

D4

D5

D6

D7

D8

Vetores
Prós:
Acesso direto aos elementos (por posição)
Elementos encontram-se em posições de memória adjacentes
Melhora o desempenho de acesso à memória

Bons algoritmos de ordenação disponíveis

Vetores
Contras:
Nem sempre é possível saber o tamanho máximo de um vetor de forma antecipada;
Em vetores dinâmicos, o redimensionamento de vetores é ineficiente;
Algoritmos de busca ineficientes ou que necessitam de propriedades onerosas (vetor ordenado). Listas Encadeadas
As listas encadeadas (LE) são conjuntos de elementos organizados em ordem linear.
Além do dado, estes elementos contém um ponteiro para o próximo elemento da lista.
Desta forma, os elementos não precisam estar contíguos em memória e podem ser criados a qualquer momento.

Listas Encadeadas
Assim, não é necessário conhecer a quantidade máxima de elementos em uma lista no ato de sua criação.
Listas encadeadas necessitam de uma biblioteca de alocação dinâmica de memória.

Representação gráfica

TAD
As listas encadeadas podem ser implementadas como Tipos Abstratos de
Dados (TAD).
Um TAD é uma abstração de estrutura de dados onde a estrutura é definida, juntamente com operações que modificam o estado da lista de forma homogênea.

LE Operações básicas
Inicializar lista
Inserir no início da lista
Inserir no final da lista
Procurar elemento
Limpar lista
Verificar se a lista encontra-se vazia
Percorrer a lista

Lista Encadeada Simples (LES)
Uma lista encadeada simples é uma lista encadeada que: