LISTA LINEARES
Fabrício Sousa
Lista
2
Bastante útil e eficiente no dia a dia.
Lista Lineares
3
Uma das estruturas de dados mais empregadas no
desenvolvimento de programas.
Lista Lineares
4
É uma coleção L: [a1,a2, ..., an], n 0 cuja
propriedade estrutural baseia-se apenas na
posição relativa dos elementos, que são dispostos
linearmente. S
Se n=0, dizemos que a lista L é vazia, caso
contrário, são válidos as seguintes propriedades.
a1
é o primeiro elemento de L.
an é o último elemento de L.
Ak, 1<k<n, é precedido pelo elemento ak-1 e seguido
por ak+1 em L.
Lista Lineares: Operações
5
Acessar um elemento qualquer da lista;
Inserir um elemento numa posição específica da
lista;
Remover um elemento;
Combinar duas listas em uma;
Particionar uma lista em duas;
Obter cópias de uma lista;
Determinar o total de elementos;
Lista Lineares: Operações (cont.)
6
Ordenar os elementos da lista;
Procurar um determinado elemento da lista;
Apagar uma lista;
Etc.
Lista Lineares: casos especiais
7
Considerando-se somente operações de acesso,
inserção e remoção , tais casos especiais recebem
nomes especiais:
Pilha:lista linear onde todas as inserções, remoções
e acessos são realizados em um único extremo. LIFO
(Last-In/First-Out) – (Último que entra/primeiro que
sai).
Lista Lineares: casos especiais
8
Fila: lista linear onde todas as inserções são feitas
num certo extremo e todas as remoções e acessos
são realizados no outro. FIFO (First-In/First-Out)
(Primeiro que entra/Primeiro que sai).
Fila Dupla: lista linear onde as inserções, remoções
ou acessos são realizados em qualquer extremo.
Lista Lineares: casos especiais
9
Fila Dupla: lista linear onde as inserções, remoções
ou acessos são realizados em qualquer extremo.
DEQUE (Double-Ended/ QUEue) (Fila de
extremidade dupla)
Casos
Fila
especiais
dupla de entrada restrita (se a inserção for restrita a
um único extremo).
Fila dupla de saída restrita ( se a remoção for restrita a um
único extremo).
Alocação de memória
10
Como podemos armazenar os elementos da lista,
dentro do computador?
O
computador carrega seu código executável para a
memória
Uma
parte é usada para armazenar as instruções a serem
executadas, e;
Outra é destinada ao armazenamento dos dados.
Alocar
área para armazenamento de dados é
responsabilidade do programador, já a da instruções,
o compilador que faz.
A alocação de memória do ponto de
vista do programador.
11
Sequencial
Encadeada
Estática
Sequencial
Estática
Encadeada
Dinâmica
Dinâmica Sequencial
Dinâmica
Encadeada
Estática
Alocação Estática versus Dinâmica
12
Alocação Estática:
a
quantidade total de memória utilizada pelos dados
é previamente conhecida e definida de modo
imutável, no código-fonte do programa. Ex. declaração
de um variável.
Alocação dinâmica
O
programa é capaz de criar novas variáveis
enquanto executa, isto é , áreas de memória que não
foram declaradas no programa passam a existir
durante a sua execução.
Alocação Sequencial
13
Alocação Sequencial
14
A forma mais natural de armazenar uma lista
dentro do computador consiste em colocar os seus
elementos em células de memória consecutivas,
um após o outro. Assim, se cada célula tem um
endereço único.
Vantagem
Dado
o endereço inicial B da área alocado e o índice i
de um elemento qualquer elemento da lista, podemos
acessá-lo imediatamente com um simples e rápido
cálculo.
Alocação Sequencial
15
Desvantagem
Quando
precisamos inserir ou suprimir elementos no
meio da lista, um certo esforço será necessário para
movimentar os elementos, de modo a abrir espaço
para inserçaõ, ou de modo a ocupar espaço liberado
por um elemento que foi removido.
Alocação Encadeada
16
Ao invés de manter os elementos agrupados numa
área contínua, isto é, ocupando células consecutivas,
na alocação encadeada os elementos podem
ocupar quaisquer células (não necessariamente
consecutivas) e, para manter a relação de ordem
linear, juntamente com cada elemento é
armazenado o endereço do próximo elemento da
lista.
Alocação Encadeada
17
Os elementos são armazenados em blocos de
memória denominados nodos, sendo que cada nodo
é composto por dois campos:
Um
para armazenar os dados e;
Outro para armazenar endereço.
•
Dois endereços especiais devem ser
destacados:
endereço
do primeiro elemento da Lista (L);
endereço do elemento fictício que segue o último
elemento da lista (ɸ)
Alocação Encadeada
18
Vantagem:
Facilidade
de inserir ou remover elementos do meio da
lista, bastando atualizar o campo de ligação do
elemento que precede aquele removido ou inserido.
•
Desvantagem
Quando desejamos acessar uma posição específica dentro da
lista. Devemos partir do primeiro elemento e ir seguindo os
campos de ligação, uma a um, até atingir a posição
desejada. Esta operação pode ter um alto custo em relação
a tempo.
Exemplo:
19
Compartilhando a Memória disponível
20
Para cada variável do tipo pilha que é criada, um
vetor com capacidade para Max elementos é
alocado.
Ex: int[] x, y, z : Pilha
Se
Max=50, agora imagine a seguinte situação:
A
pilha x nunca terá mais do que 20 elementos.
A pilha y não terá mais do que 10 elementos.
A pilha z, em determinado momento, chegará a armazenar
70 elementos.
Qual deverá ser o tamanho da variável Max?
Classes Especiais: Class Objetct
21
A linguagem Java provê algumas classes básicas para formar uma
base sólida para todas as demais classes, inclusive aquelas criadas
pelo programador. Dentre essas classes, seguramente as mais
importantes são as classes Object, Class e String.A classe Object
A classe Object é uma classe que serve de superclasse para todas
as classes existentes em Java. Isso significa que ao criar uma
classe, se não for especificada nenhuma superclasse após a
palavra extends, então a classe Object será assumida
automaticamente como superclasse. Portanto toda classe é subclasse
de Object, e com isso herda alguns métodos automaticamente.
Um método muito interessante presente na classe Object é o equals.
Suponha que haja duas instâncias de uma mesma classe e
desejamos testar se elas contém a mesma informação.
Classes Especiais: Class Objetct (cont.)
22
O operador == nos daria o valor true apenas se seus
operandos forem precisamente o mesmo objeto. Porém, o
operador equals nos diria quando os objetos contém o
mesmo estado, através da comparação campo-a-campo.
Por exemplo, eu e você podemos ter carro do mesmo
modelo. Nesse caso meuCarro ==
seuCarro seria false pois embora nossos carros sejam do
mesmo modelo, são carros diferentes.
Entretanto, meuCarro.equals(seuCarro) poderia sertrue se
os atributos de ambos os carros fossem idênticos, por
exemplo, mesmo ano, mesma cor, etc.Um outro método
interessante da classe Object é o método getClass, que
retorna uma referência a um objeto contendo informações
sobre a classe a que é aplicado. Isto será visto logo abaixo.
Referência
23
PEREIRA, Silvio L. Estrutura de Dados Fundamentais.
Érica:1996.