Listas Lineares

Listas lineares são estruturas que permitem representar um conjunto de dados e afins de forma a preservar a relação de ordem linear de seus elementos.

A maneira mais simples de acomodar uma lista linear em computador é através da utilização de um vetor. A representação por vetor explora a sequencia da memória de tal forma que os nós de uma lista sejam armazenados em endereços contíguos, ou igualmente distanciados um do outro.

Quando falamos em listas, filas e pilhas, pode se dizer que todas, na verdade são listas de informações, por exemplo, para incluir, excluir e localizar uma ou mais informações.

Segundo Puga e Risseti (2004, p.183), uma lista é uma coleção de elementos do mesmo tipo, dispostos linearmente, podem ou não seguir uma organização por exemplo [E1,E2,E3,E4,E5,...,En], onde não devemos ser o maior numero ou igual a zero.

FIFO

Em engenharia da computação, FIFO, acrônimo para First In, First out, que no português significa primeiro a entrar, primeiro a sair) refere-se a estrutura de dados do tipo fila. Tem uma estrutura diferente da estrutura de uma LIFO ( que significa Last In, First Out, as pilhas).

As listas são amplamente utilizadas em programação para implementar filas de espera. Em uma fila de tipo FIFO os elementos vão sendo colocados na fila e retirados (ou processados) por ordem de chegada. A ideia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início.

LIFO

Em ciência da computação, LIFO (acrônimo para a expressão inglesa Last In,First Out que, em português significa último a entrar, primeiro a sair) refere-se a estruturas de dados do tipo pilha. É equivalente a FILO, que significa First In, Last Out.

O conceito de pilha é amplamente utilizado na informática, como por exemplo, durante a execução de um programa, para armazenamento de valores de variável local a um bloco e também para conter o endereço de retorno do trecho de programa que chamou a função ou procedimento atualmente em execução.

Usa-se os termos push e pop para denominar a inserção e remoção de elementos de pilha, respectivamente. Usa-se o termo top para consultar o elemento do topo da pilha, sem o remover.

Uma pilha é uma lista linear na qual o primeiro elemento a entrar é o ultimo elemento a sair. Ela possui apenas uma entrada, chama de topo, a partir da qual os dados entram e saem dela.

Por exemplo, as Pilhas também são conhecidas como uma lista LIFO (Last In, First Out), que em português significa “Ultimo a entrar e primeiro a sair”. É uma lista linear em que todas as operações de inserção e remoção são feitas por um único extremo denominado topo. Um exemplo bastante comum em que se aplica o conceito de pilhas é o de uma pilha de pratos que estão guardados no armário: quando a pessoa vai utilizar um deles pega sempre o prato que se encontra no topo da pilha, assim como, quando um novo prato vai ser guardado, é colocado no topo. Isso acontece porque apenas uma das extremidades da pilha está acessível.

Encadeamento Simples

Os elementos da lista possuem apenas um ponteiro que aponta para o elemento sucessor ou próximo.

Uma alternativa para esta desvantagem é o uso de listas encadeadas, que permitem a criação de arrays sem um número de “N” elementos fixo.

Uma lista é formada por nós. Nó é um objeto composto que armazena uma referência para um elemento ou objeto qualquer e uma referência next (próximo) que permite fazer a ligação com o próximo nó da lista até que o último aponte para uma região de memória nula (null).

...