Uma Lista linear é um conjunto de n >= 0 elementos L[1], L[2], ..., L[n]. Tal que:
- se n > 0, L[1] é o primeiro elemento
- para 1 <= k <= n, o nó L[k] é precidido pelo L[k-1].
As operações mais frequentes em listas são a busca, a inclusão e a remoção de um determinado elemento.
Se as inserções e remoções são permitidas apenas nas extremidades da lista, ela recebe o nome de deque (double end queue). Se as inserções e as remoções são realizadas somente em um extremo, a lista é chamada pilha, sendo denominada fila no caso em que inserções são realizadas em um extremo e remoções em outro.
O tipo de armazenamento de uma lista linear pode ser classificado de acordo com a posição relativa (sempre contígua ou não) na memória de dois nós consecutivos na lista.
Alocação sequencial
A maneira mais simples de se manter uma lista linear na memória do computador é colocar seus nós em posições contíguas. Nesse caso, o endereço real do (j + 1)-ésimo nó da lista se encontra c unidades adiante daquele correspondente ao j-ésimo. A constante c é o número de palavras de memória que cada nó ocupa.
Seja uma lista linear. Cada nó é formado por campos, que armazenam as características distintas dos elementos da lista. Além disso, cada nó da lista possui, geralmente, um identificador, denominado chave. Para evitar ambiguidades supõe-se que todas as chaves são distintas. Os nós podem ser ordenadso ou não, segundo suas chaves.
Busca por um nó conhecendo sua chave
busca1(x):
i := 1; busca1 := 0
enquanto i <= n faça
se L[i].chave == x então
busca1 := i
i := n+1
senão
i := i+1
Algoritmo que cria um novo nó com a chave procurada
busca(x):
L[n+1] := x; i := 1
enquanto L[i].chave != x faça
i := i+1
se i != n+1
busca := i
senão
busca := 0
Ambos algoritmos tem complexidade do pior caso O(n). Mas o segundo é mais rápido por fazer menos comparações.
Busca por um elemento na lista ordenada
busca-ordenada(x):
L[n+1] := x; i := 1
enquanto L[i].chave < x faça
i := i+1
se i == n+1 ou L[i].chave != x então
busca-ordenada := 0
senão
busca-ordenada := i
Complexidade O(n).
Busca Binária
busca-bin(x):
inf := 1; sup := n; busca-bin := 0
enquanto inf <= sup faça
meio := (inf+sup)/2
se L[meio].chave == x então
busca-bin:=meio
inf := sup+1
senão se L[meio].chave < x então
inf := meio+1
senão
sup := meio-1
Complexidade O(log n).
As operações de inserção e remoção utilizam a busca, tanto para evitar chaves duplicadas quanto para encontrar o elemento a ser removido. Os algoritmos de inserir e remover a seguir consideram uma lista não ordenada. A memória pressuposta disopnível tem M posições (M+1 pois é necessária uma posição extra para a busca).
Inserção de um nó com chave x
se n < M então
se busca(x) == 0 então
L[n+1] := novo-valor
n := n+1
senão "elemento já existe"
senão overflow
Remoção de um nó com chave x
se n != 0 então
indice := busca(x)
se indice != 0 então
valor-recuperado:=L[indice]
para i := indice até n-1 faça
L[i] := L[i+1]
n := n-1
senão "elemento não existe"
senão underflow
Complexidade de ambos é O(n).
Alocação encadeada
Também conhecida por aloção dinamica uma vez que as posições de memória são alocadas conforme o necessário. Os nós de uma lista então encontram-se dispersos na memória e são interligados por ponteiros.
Qualquer estrutura, inclusive listas, que seja armazenada em alocação encadeada requer o uso de um ponteiro que indique o endereço de seu primeiro nó. O percurso de uma lista é feito então a partir desse ponteiro.
Imprimir uma lista encadeada
*ptlista é o ponteiro para o primeiro nó.
pont := ptlista
enquanto pont != null faça
imprimir(pont->.info)
pont := pont->.prox
Busca em uma lista ordenada
*pont é retornado apontando para o elemento procurado, ant aponta para o anterior e ptr vai percorrer a lista
busca-enc(x, pont, ant)
ant := ptlista; pont := null
ptr := ptlista->.prox
enquanto ptr != null faça
se ptr->.chave < x então
ant := ptr
ptr := ptr->.prox
senão se ptr->.chave == x então
pont := ptr
ptr := null
Complexidade O(n).
Inserção de um nó novo
busca-enc(x, pont, ant)
se pont == null então
// alocar pt
pt->.info := novo-valor
pt->.chave := x
pt->.prox := ant->.prox
ant->.prox := pt
senão "elemento já existe"
Remoção de um nó
busca-enc(x, pont, ant)
se pont != null então
ant->.prox := pont->.prox
// desalocar pt
senão "nó não encontrado"
Complexidade de ambos é O(n).
Busca em uma lista não ordenada
busca-enc(x, pont, ant)
ant := ptlista; pont := null
ptr := ptlista->.prox
enquanto ptr != null faça
se ptr->.chave == x então
pont := ptr
ptr := null
senão
ant := ptr
ptr := ptr->.prox
Complexidade O(n).
Referência
Livro Estruturas de Dados e Seus Algoritmos
Top comments (0)