Algoritmos Listas Lineares

Algoritmos e
Estruturas de Dados I
Listas Lineares versão 1.8

Prof. D.Sc. Fabiano Oliveira [e-mail] Listas Lineares
● Lista Linear é o nome dado a uma estrutura que agrupa diversos elementos que, de alguma forma, relacionam-se entre si
○ Cada elemento possui um identificador distinto chamado de chave e possivelmente outros campos
Ex.: Lista Linear de Alunos (chave: matrícula), Logs de
Acesso a Sistemas (chave: data/hora e usuário), etc.

Listas Lineares
● Para decidir como uma Lista Linear deve ser implementada, devemos considerar quais operações serão exigidas da lista
● Operações comuns:
○
○
○
○
○

Impressão
Inserção
Remoção
Busca
Ordenação (veremos adiante no curso)

Listas Lineares
● Dependendo das operações que uma lista linear deve atender, a lista pode ser classificada como:
○ Deque: inserções e remoções apenas em pontas da lista ■ Pilha: inserções e remoções numa mesma ponta da lista
■ Fila: inserções numa ponta, remoções em outra

Aplicações de Pilhas e Filas?

Listas Lineares
● Dependendo da forma de alocação dos elementos em memória, outra classificação pode ser feita:
○ Alocação Sequencial: elementos ocupam memória em posições contíguas. Os elementos admitem acesso aleatório, pois suas posições podem ser calculadas
○ Alocação Encadeada: elementos não necessariamente ocupam posições contíguas em memória. Elementos devem ser consultados a partir das posições de elementos já conhecidos, avançando-se ou retrocedendo-se a partir destes

Listas Lineares
● As listas podem além ser classificadas como ordenadas ou não-ordenadas, dependendo se os elementos são mantidos ordenados por chave

Listas Lineares
● Qual tipo de lista é o melhor? A resposta será sempre "DEPENDE!". O uso dos elementos (ou seja, as operações sobre a lista) é que determinará qual é o melhor tipo de lista para o problema em questão

Alocação Sequencial
Impressão, Busca, Inserção, Remoção