Listas Lineares

1. Listas Lineares
1.1. Por que usar listas lineares (ou simplesmente listas)?

No cotidiano lidamos com conjunto de dados que se relacionam entre si de algum modo, de acordo com as propriedades que esse dados apresentam. Quando criarmos estruturas de dados que representam tais características no computador devemos fazer de modo que preservemos tais relacionamentos, quando a solução algorítmica que adotarmos assim o exigir.

Para os problemas necessitam de conhecermos a ordem dos dados, por exemplo a ordem cronológica dos nascimentos durante um determinado período para levantarmos a função que expressa o fenômeno; ou a seqüência de chegada de maratonistas ao término de uma corrida ou ainda a prioridade no atendimento de portadores de senhas de uma fila de clientes; geralmente usamos as listas lineares para implementarmos suas estruturas de dados.

Sem contar com as estruturas de dados primitivas, as listas lineares são as de manipulação mais simples.

1.2. Conceito

Lista linear é uma estrutura de dados que corresponde a uma seqüência ordenada de elementos de mesmo tipo. Esses elementos, denominados nós, podem conter, cada um, um dado primitivo ou um dado composto.

Uma lista linear é um conjunto de n  0 nós, X1,X2, ..., Xn, organizados de forma a refletir as posições relativas 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 de Xk+1; e Xn é o último nó. quando n = 0 dizemos que a lista é vazia.

1.3. Operações

Uma lista pressupõe um conjunto de operações que permitem a sua criação e manipulação. As operações básicas que podemos executar sobre uma lista são, entre outras:

Construção da lista
Percurso por todos os nós.
Busca de um nó para obter e/ou alterar o dado nele contido.
Inserção de um nó.
Remoção de um nó.
Destruição da lista.

1.4. Representações

Podemos representar uma lista de várias formas, porém a duas formas mais utilizadas são:

Representação por