Índice >
Lista >
Estática Seqüencial
Instituto de Ciências Matemáticas de São Carlos
Departamento de Computação e Estatística
SCE182 - Algoritmos e Estruturas de Dados 1
Profs. Resp.: Graça Pimentel e Maria Cristina
Lista Estática Sequencial
Uma lista estática sequencial é um arranjo de registros onde
estão estabelecidos regras de precedência entre seus elementos
ou é uma coleção ordenada de componentes do
mesmo tipo.
O sucessor de um elemento ocupa posição física
subsequente.
Ex: lista telefônica, lista de alunos
A implementação de operações pode ser feita
utilizando array e record, onde o vetor associa o elemento
a(i) com o índice i (mapeamento sequencial).
Características de Lista Estática Sequencial
-
elementos na lista estão ordenados;
-
armazenados fisicamente em posições consecutivas;
-
inserção de um elemento na posição a(i) causa
o deslocamento a direita do elemento de a(i) ao último;
-
eliminação do elemento a(i) requer o deslocamento à
esquerda do a(i+1) ao último;
Mas, absolutamente, uma lista estática sequencial ou é vazia
ou pode ser escrita como ( a(1), a(2), a(3), ... a(n) ) onde a(i) são
átomos de um mesmo conjunto S.
Além disso, a(1) é o primeiro elemento, a(i) precede a(i+1),
e a(n) é o último elemento.
Assim as propriedades estruturadas da lista permitem responder a questões
como:
-
qual é o primeiro elemento da lista
-
qual é o último elemento da lista
-
quais elementos sucedem um determinado elemento
-
quantos elementos existem na lista
-
inserir um elemento na lista
-
eliminar um elemento da lista
Consequência: As quatros primeiras operações
são feitas em tempo constante. Mas, as operações de
inserção e remoção requererão mais cuidados.
Veja algumas operações
básicas relacionadas com lista estática sequencial.
Vantagem:
-
acesso direto indexado a qualquer elemento da lista
-
tempo constante para acessar o elemento i - dependerá somente
do índice.
Desvantagem:
-
movimentação quando eliminado/inserido elemento
-
tamanho máximo pré-estimado
Quando usar:
-
listas pequenas
-
inserção/remoção no fim da lista
-
tamanho máximo bem definido
Vamos tentar evitar as desvantagens anteriores e usar endereços não
consecutivos (Lista
Encadeada Estaticamente).
Exercício e programa exemplo
Lista