Estrutura dados Aula5 listas

Aula 5 – Lista linear
1. Lista Linear: Definição e representação.
Sequencia de zero ou mais itens x1, x2, · · · , xn, na qual xi é de um determinado tipo e n representa o tamanho da lista linear.Ou seja, uma lista linear é uma sequencia com zero ou mais elementos de um mesmo tipo.
Sua principal propriedade estrutural envolve as posições relativas dos itens em uma dimensão.
– Assumindo n >= 1, x1 é o primeiro item da lista e xn é o último item da lista.
– xi precede xi+1 para i = 1, 2, · · · , n − 1
– xi sucede xi−1 para i = 2, 3, · · · , n
– o elemento xi é dito estar na i-ésima posição da lista.
a) Algumas aplicações:







Forma simples de interligar os elementos de um conjunto.
Agrupa informações referentes a um conjunto de elementos que se relacionam entre si de alguma forma.
São úteis em aplicações tais como manipulação simbólica, gerência de memória, simulação e compiladores.
Inúmeros tipos de dados podem ser representados por listas. Alguns exemplos de sistemas de informação são: informações sobre os funcionários de uma empresa, notas de alunos, itens de estoque, etc.
Podem crescer ou diminuir de tamanho durante a execução de um programa, de acordo com a demanda.
Podem ser adequadas quando não é possível prever a demanda por memória, permitindo a manipulação de quantidades imprevisíveis de dados, de formato também imprevisível.

b) Implementações de Listas Lineares
Várias estruturas de dados podem ser usadas para representar listas lineares, cada uma com vantagens e desvantagens particulares. As duas representações mais utilizadas são as implementações
– Usando alocação sequencial e estática (com vetores).
– Usando alocação não sequencial e dinâmica (com ponteiros), denominadas por Estruturas Encadeadas.
O conjunto de operações a ser definido depende de cada aplicação. Um conjunto de operações necessário a uma maioria de aplicações é:
1. Criar uma lista linear vazia.
2. Inserir um novo item imediatamente após o i-ésimo item.
3. Retirar o i-ésimo item.