Listas lineares

Universidade Estadual de Mato Grosso do Sul - Curso de Ciência da Computação Disciplina: Estruturas de Dados Profª. Raquel Marcia Müller

1

Listas Lineares
Dentre as estruturas de dados não primitivas, as listas lineares são as de manipulação mais simples. Uma lista linear agrupa informações referentes a um conjunto de elementos que, de alguma forma, se relacionam entre si. Ela pode se constituir, por exemplo, de informações sobre os funcionários de uma empresa, sobre notas de compras, itens de estoque, notas de alunos, etc. Uma lista linear, ou tabela, é então um conjunto de n ≥ 0 nós L[1], L[2], ..., L[n] tais que suas propriedades estruturais decorrem, unicamente, da posição relativa dos nós dentro da seqüência linear. Tem-se: • se n > 0, L[1] é o primeiro nó; • para 1 < K ≤ n, o nó L[k] é precedido por L[k-1]; • Operações Mais Freqüentes Em Listas: • busca; • inclusão; • remoção; São operações básicas, que precisam de algoritmos eficientes. • Outras Operações: • • • • alteração; combinação de duas listas; ordenação; determinação do primeiro e do último nó da lista.

• Casos Particulares de Lista: • • • deque (inserção e remoção só nas extremidades da lista); pilha (inserção e remoção só em um extremo); pilha( inserção em um extremo e remoções no outro).

• Tipo de armazenamento de uma lista: • • alocação seqüencial; alocação encadeada.

Alocação Seqüencial Maneira mais simples de se manter uma lista na memória. Como a implementação de alocação seqüencial em linguagens de alto nível é geralmente realizada com reserva de memória ⇒ alocação estática. Obs.: Inserção e Remoção de nós não ocorrem de fato: simulação. Ideal para filas e pilhas. Seja uma lista linear. Cada nó é formado por campos, que armazenam as características distintas dos elementos da lista. Além disso, cada nó da lista possui, geralmente, um identificador, denominado chave. Para evitar ambigüidades, supõe-se

Universidade Estadual de Mato Grosso do Sul - Curso de Ciência da