Listas Lineares

Páginas: 5 (1051 palavras) Publicado: 20 de maio de 2014
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çãoalgorí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 usamosas 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 emanipulaçã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 porcontigüidade dos nós
Representação por encadeamento dos nós.

A decisão de optar por qual forma dependerá do número de vezes que se executa determinadas operações sobre a lista, como as citadas acima. Pois sua arquitetura interna dirá a necessidade de um maior ou menor esforço computacional para sua execução.

1.4.1. Representação por Contigüidade

Essa representação se aproveita dadisposição em seqüência da memória do computador, de modo que os nós da lista sejam armazenados em endereços de memória contíguos ou igualmente espaçados entre si. De modo que o endereço de um nó pode ser determinado matematicamente.


Figura 1 – Representação por contigüidade
Normalmente, essa representação lança mão de vetores para sua implementação, o que exigem um maior esforço computacionalpara executarmos a operações de inserção e remoção de nós. Além de necessitarmos de superdimensionar tais vetores a fim de evitarmos a falta de espaço em memória para o crescimento da lista.

1.4.2. Representação por Encadeamento

A representação por encadeamento torna desnecessária a necessidade de estimava, a priori, para o crescimento da lista pois sua limitação é física, ou seja, depende daquantidade de memória disponível.
Além disso, diminui sensivelmente o esforço computacional das operações de inserção e remoção de nós.
Isso porque nas listas encadeadas, cada nó possui, além do dado que desejamos armazenar, uma indicação do nó seguinte, caso exista. Assim o endereço de memória não mais é determinado matematicamente, dizemos então que a contigüidade da lista é lógica.
Narepresentação por encadeamento, normalmente, utilizamos registros de dados com pelo menos um dos campos de cada registro usado para indicar o próximo nó da lista.

Figura 2 - Representação por encadeamento

1.4.2.1. Tipos Básicos de Listas Encadeadas

Há muitas formas de implementarmos listas com encadeamento, a escolha dependerá de critérios como a eficiência desejada do algoritmo, a memória...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Listas lineares
  • Listas lineares
  • Listas lineares
  • Listas lineares
  • Listas Lineares
  • Lista lineares
  • Listas lineares
  • Lista de algebra linear

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!