Aula 01

FACEMA – Faculdade de Ciência e Tecnologia do
Maranhão
ADS - Análise e Desenvolvimento de Sistemas

Estrutura de Dados
Jeovane Reges | [e-mail]

Roteiro
• UNIDADE I
− Cartilha de Java

• UNIDADE II
– Listas

• UNIDADE III
– Pilhas e Filas

• UNIDADE IV
– Collections

• UNIDADE V
− Árvores
2

Link Copy bit.do/facema-estrdados 3

Listas
Simplesmente
Encadeadas

4

Unidade II
•

Listas
Encadeadas

Simplesmente

• Introdução
• Uma Lista Encadeada, em sua forma mais simples, é uma coleção de nós que juntos formam uma “lista linear”.
• Cada nó é um objeto que armazena uma referência para um elemento e uma referência para o próximo nó.
• A referência que aponta para outro nó é
5
chamada de NEXT.

Cada nó da lista deverá conter, além de informações a seu respeito, uma referência para o nó seguinte.

6

Unidade II
•

Listas
Encadeadas

Simplesmente

• Introdução
• A principal vantagem de se utilizar listas encadeadas está no fato de não ser preciso reservar um tamanho fixo.
• Nas operações de inserção/remoção não é necessário deslocamentos na lista.
• Entretanto, um nó da lista encadeada ocupa mais espaço em memória do que
7
um elemento de um “vetor”.

Unidade II
•

Listas
Encadeadas

Simplesmente

• Introdução head THE

TIM

tail
CNT

CAX

COD

Ø

Os ponteiros next de cada nó são representados como setas. O objeto null é denotado como ∅.

8

Unidade II
•

Listas
Encadeadas

Simplesmente

• Introdução
• A referência NEXT dentro de um nó pode ser vista como uma ligação/ponteiro para outro nó.
• O primeiro e o ultimo nó de uma lista encadeada são normalmente chamados de cabeça (head) e cauda (tail).
• Identifica-se a cauda por ser o nó que possui uma referência next nula,9 que indica

Implementação

10

Unidade II
•

Listas
Encadeadas

Simplesmente

• Implementação
• Para implementar uma lista simplesmente encadeada, será definido uma classe
Node.
• A qual especifica o tipo dos objetos que serão armazenados nos nós da lista.
• Aqui, assume-se