Juliana Jenny Kolb
Home > Simulados on-line > Questões de Concursos > Tecnologia da Informação (TI) > Algoritmos e Estruturas de Dados > Estruturas de Dados
Listas Lineares Sequenciais
É a lista linear na qual a ordem (lógica) dos elementos da lista coincide com sua posição física (em memória). Ou seja, elementos adjacentes da lista ocupam posições contíguas de memória.
A forma mais comum de implementação de uma lista sequencial é através de um vetor de elementos (A) do tipo REGISTRO de tamanho máximo possível definido pela constante MAX.
O vetor é conjugado a um contador de número de posições efetivamente ocupadas (nroElem). A ocupação do vetor se dá sempre em posições contíguas, ou seja, nroElem-1 indica o último elemento existente na estrutura.
typedef struct
{
REGISTRO A[MAX];
int nroElem;
} LISTA;
Os registros contêm campos de informações variadas que são dependentes da aplicação. Por exemplo, um registro de aluno conteria campos como nome, idade, NroUSP etc. Para efeito de demonstração da busca em estruturas ordenadas e outras operações de identificação de elementos, definimos também um campo chave em cada registro.
Vantagens
- Acesso direto a qualquer elemento com base no seu índice. O tempo é constante O(1). No entanto, em muitas aplicações o índice do dado procurado não é conhecido, o que faz desta uma vantagem apenas relativa.
- Se a lista estiver ordenada pela chave em questão, a busca por uma chave pode ser efetuada através de busca binária O(lg n), que é excelente.
Desvantagens
- Mesmo em uma estrutura ordenada, o pior caso de inserção e exclusão (na frente da lista) exige movimentação de todos os n elementos da lista, ou seja, O(n). Isso pode ser inadequado para aplicações em que ocorrem muitas atualizações, e é principalmente por causa disso que a lista sequencial é muitas vezes substituída por uma estrutura de dados mais complexa.
- Implementação estática, exigindo que o tamanho do vetor seja previamente estabelecido. Embora algumas linguagens de programação (como C) permitam a expansão posterior de um vetor deste tipo, esta operação requer cópia de áreas de dados inteiras em memória, a um custo O(n) que inviabiliza sua aplicação no caso geral.
Referência Bibliográfica
Honda, Willian Yukio; Paraboni, Ivandré. ACH2023 – ALGORITMOS E
ESTRUTURAS DE DADOS I. Trabalho Acadêmico, 2011.