Lista Linear

Muitos problemas computacionais possuem soluções algorítmicas semelhantes. Por exemplo,

um spool de impressão, atendimentos de um caixa de banco ou a lista de e-mails pendentes em

uma caixa de saída são problemas em que a ordem de entrada dos elementos é a mesma ordem

de saída, ou seja, uma aplicação típica de FILA.

Assim também abrir menus e submenus, criar uma pilha de produtos em um supermercado

ou simular uma torre de Hanói são algoritmos em que a ordem de entrada é o contrário da

ordem de saída, ou seja, aplicação típica de PILHA.

Portanto, faz-se necessário entender como essas estruturas funcionam, como usar a

implementação dos algoritmos para servir como ferramenta na hora em que um problema

exigir uma solução semelhante.

Não só entender a parte teórica, mas também saber implementar, utilizando um Tipo Abstrato

de Dados, em uma linguagem POO, como Java, e um tipo de alocação de memória estudado

é fundamental para poder usar o conteúdo aprendido.

Uma lista linear é um tipo abstrato de dado (TAD) que representa uma coleção L:[a1,a2,...,an],

n>=0 cuja propriedade estrutural baseia-se apenas na posição relativa dos elementos, que são

dispostos linearmente. Se n=0, dizemos que a lista L é vazia; caso contrário, são válidas as

seguintes propriedades:

» a1 é o primeiro elemento da lista L;

» an é o último elemento da lista L;

» ak, 1<k<n, é precedido pelo elemento ak-1 e seguido por ak+1 na lista L.

Ou seja, a característica fundamental de uma lista linear é o sentido de ordem unidimensional

dos elementos que a compõem; uma ordem que nos permite dizer com precisão onde a coleção

inicia e onde termina, sem possibilidade de dúvida. Temos alguns casos especiais de Listas

Lineares que são frequentemente utilizadas na modelagem de problemas a serem resolvidos

computacionalmente. Elas são: Pilhas, Filas e Listas Ordenadas.

Para podermos implementar as listas lineares, devemos avaliar como armazenaremos os

elementos da lista na memória do computador. A alocação de memória, do ponto de vista do

programador, pode ser classificada em duas categorias. A primeira refere-se à quantidade de

memória usada para armazenar os dados na estrutura; nesse caso a alocação pode ser Estática

ou Dinâmica. A segunda refere-se à forma como os elementos estão alocados em relação