aula_listas

Prévia do material em texto

Listas
Estrutura de Dados I
Profª Valéria de Carvalho Santos
Universidade Estadual Paulista “Júlio de Mesquita”
Definição
Conceitos básicos
• Exemplos de listas lineares
• Lista do supermercado
• Lista telefonica
• Fila do banco
• Pilha de pratos
• etc
Definição
Conceitos básicos
• Lista linear: é um conjunto de zero ou mais itens x1, 
x2,..., xn na qual xi é de um determinado tipo e n
representa o tamanho da lista. 
• Sua principal propriedade estrutural diz respeito às 
posições relativas dos itens.
• Se n >= 1, x1 é o primeiro item e xn é o ultimo.
X1 X2 X3 ... xi-1 xi xi+1 ... xn
Operações
Conceitos básicos
• As operações mais comuns sobre lista são:
• Criar lista
• Limpar lista
• Inserir item (última posição)
• Inserir item (por posição)
• Remover item (última posição)
• Remover item (dada uma chave)
• Buscar item (por posição)
• Buscar item (dada uma chave)
• Verificar se a lista está vazia
• Verificar se a lista está cheia
•Imprimir lista
Tipos de representação
Representação de listas
• Estática
• Itens contíguos de memória
• Alocação prévia de espaço
•
• Dinâmica
• Itens encadeados
• Alocação sob demanda
Tipos de representação
Representação de listas
• Estática
• Os itens da lista são armazenados em posições 
contíguas de memória
• A lista pode ser percorrida em qualquer direção
• A inserção de um novo item pode ser realizada após o 
último item com custo constante 
• Ter acesso fácil a um xk qualquer
Tipos de representação
Representação de listas
• Representação estática
Operações
Operações em representação estática
• Inserir item (última posição)
Operações
Operações em representação estática
• Buscar item (dada uma chave)
Operações
Operações em representação estática
• Remover item (dada uma chave)
Operações
Operações em representação estática
• Exercício
•Implementar a inserção no meio da lista
•Implementar a remoção de um item, dada a posição