Listas Lineares

Listas Lineares

Lista linear é uma estrutura de dados na qual elementos de um mesmo tipo de dado estão organizados de maneira sequencial. Não necessariamente, estes elementos estão fisicamente em sequência, mas a idéia é que exista uma ordem lógica entre eles. Um exemplo disto seria um consultório médico: as pessoas na sala de espera estão sentadas em qualquer lugar, porém sabe-se quem é o próximo a ser atendido, e o seguinte, e assim por diante. Assim, é importante ressaltar que uma lista linear permite representar um conjunto de dados afins (de um mesmo tipo) de forma a preservar a relação de ordem entre seus elementos. Cada elemento da lista é chamado de nó, ou nodo.

Definição:
Conjunto de N nós, onde N ≥ 0, x1, x2, ..., xn, organizados de forma a refletir a posição relativa dos mesmos. Se N ≥ 0, então x1 é o primeiro nó. Para 1 < k < n, o nó xk é precedido pelo nó xk-1 e seguido pelo nó xk+1 e xn é o último nó. Quando N = 0, diz-se que a lista está vazia. Exemplos de listas lineares:
Pessoas na fila de um banco;
Letras em uma palavra;
Relação de notas dos alunos de uma turma;
Itens em estoque em uma empresa;
Dias da semana;
Vagões de um trem;
Pilha de pratos;
Cartas de baralho.

Alocação de uma lista
Quanto a forma de alocar memória para armazenamento de seu elementos, uma lista pode ser:
1. Sequencial ou Contígua
Numa lista linear contígua, os nós além de estarem em uma sequência lógica, estão também fisicamente em sequência. A maneira mais simples de acomodar uma lista linear em um computador é através da utilização de um vetor.

A representação por vetor explora a sequencialidade da memória de tal forma que os nós de uma lista sejam armazenados em endereços contíguos.
Tipos de Listas Lineares
Os tipos mais comuns de listas lineares são as: pilhas Uma pilha é uma lista linear do tipo LIFO - Last In First Out, o último elemento que entrou, é o primeiro a sair. Ela possui apenas uma entrada, chamada de topo, a partir da qual os dados entram e