Estrutura de dados

Universidade Paulista UNIP
Ciência da Computação

Estrutura de Dados

Brasília – DF
2014

Universidade Paulista UNIP

Listas Lineares

Trabalho de DP que será avaliado como nota da NP1.

Brasília – DF
2014
Listas Lineares

É uma lista de dados no qual elementos de mesmo tipo de dados são organizados de maneira sequencial. Não necessariamente, esses elementos estão fisicamente em sequência, mas a ideia é que exista uma ordem entre eles. Cada elemento é chamado de NÓ.
Alocação de uma Lista

Quanto as formas de se alocar memória para o armazenamento de seus elementos, uma lista pode ser:
Sequencial :
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.

Encadeada :

Em listas lineares encadeadas, diferentemente das listas lineares sequenciais (ou contíguas), os elementos não estão necessariamente armazenados sequencialmente na memória. Assim, para manter a ordem lógica entre os elementos, as listas lineares encadeadas podem ser implementadas de duas formas:
Simplesmente encadeada
Numa lista linear simplesmente encadeada cada elemento possui, além do espaço para armazenamento da informação, um espaço para armazenar uma referência da localização na memória onde o próximo elemento da lista (ou o anterior) se encontra.

Duplamente encadeada
Numa lista linear duplamente encadeada cada elemento possui, além do espaço para armazenamento da informação, um espaço para armazenar a referencia da localização de memória onde se encontra o próximo elemento da lista e outro espaço para armazenar a referencia da localização de memória onde se encontra o elemento anterior.

Tipos de Listas

Pilhas : Onde o primeiro elemento a