Estruturas de Dados Lineares — Lista Linear

Definição

Estrutura linear de dados é a disciplina que estuda as técnicas computacionais para a organização e manipulação eficiente de quaisquer quantidades de informação.

Considerações em um projeto de software

Em um projeto de software, dois aspectos devem ser considerados:

• De que forma estão organizados os dados, qual a sua estrutura.
• Quais procedimentos atuam sobre estes dados, que operações podem ser realizadas sobre eles.

Conceitos fundamentais

Ao estudar estruturas de dados teremos sempre este par:

• Um conjunto estruturado de informações.
• Uma classe de objetos ou um tipo de dados.
• Um conjunto definido de operações sobre estes dados:
• Um conjunto de métodos ou funções.

O que é uma Lista Linear

A Lista Linear é a estrutura que permite representar um conjunto de dados de forma a preservar a relação de ordem existente entre eles.

Tipos de listas lineares

Listas Lineares Gerais - sem restrição para inserção e remoção de elementos.

Listas Lineares Privadas (Pilhas, Filas) - com restrição para inserção e remoção de elementos.

As listas gerais podem ser ordenadas ou não ordenadas.

• Lista Ordenada: os nós encontram-se ordenados segundo os valores de suas chaves.
• Lista Não Ordenada: os nós não estão ordenados.

Propriedades formais de uma lista linear

Uma lista linear é um conjunto de n ≥ 0 nós L[1], L[2], ..., L[n], onde:

• Se n > 0, L[1] é o primeiro nó.
• Para 1 < k <= n, o nó L[k] é precedido por L[k-1].

Observe que existe uma ordenação implícita: se n > 0 temos que:

• L[1] é o primeiro nó da lista.
• L[n] é o último nó da lista.
• Se 1 < k < n, L[k] é precedido por L[k-1] e seguido por L[k+1].
• Se n = 0, dizemos que a lista é vazia.

Estrutura dos nós

Cada nó da lista é formado por campos que armazenam as características distintas das listas.

Cada nó possui uma chave (campo): identificador. Todas as chaves são distintas.

Operações em Listas Lineares

Listas Lineares: operações

• Criar uma lista vazia.
• Verificar se uma lista está vazia.
• Obter o tamanho de uma lista.
• Obter/modificar o valor do elemento de uma determinada posição na lista.
• Obter a posição de elemento cujo valor é dado.
• Inserir um novo elemento após (ou antes) de uma determinada posição na lista.
• Remover um elemento de uma determinada posição na lista.
• Exibir os elementos de uma lista.
• Concatenar duas listas.

Implementação de listas: arranjos

Implementação de Listas: Arranjos - Os itens da lista são armazenados em posições contíguas de memória. A lista pode ser percorrida em qualquer direção.

Os itens são armazenados em um array de tamanho suficiente para armazenar a lista. O i-ésimo item da lista está armazenado na i-ésima posição do array, 1 ≤ i ≤ n.

O armazenamento sequencial em arranjos (estático) é útil quando as estruturas sofrem poucas remoções ou inserções ou ainda quando inserções e remoções não acarretam grande movimentação de nós: Filas, Pilhas e Deques.