2.

1Introdução

Dentre as estruturas de dados não primitivas, as listas lineares são as de manipulação mais
simples. Neste capítulo, são discutidos seus algoritmos e estruturas de armazenamento.

Uma lista linear agrupa informações referentes a um conjunto de elementos que, de alguma
forma, se relacionam entre si. Ela pode se constituir, por exemplo, de informações sobre os
funcionários de uma empresa, sobre notas de compras, itens de estoque, notas de alunos etc.
Na realidade, são inúmeros os tipos de dados que podem ser descritos por listas lineares.

Uma lista linear, ou tabela, é então um conjunto de n ≥ 0 nós L[1], L[2], …, L[n] tais que suas
propriedades estruturais decorrem, unicamente, da posição relativa dos nós dentro da
sequência linear. Tem-se:

–se n > 0, L[1] é o primeiro nó,

–para 1 < k ≤ n, o nó L[k] é precedido por 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, o que, aliás, ocorre na maioria das estruturas de dados. Tais operações
podem ser consideradas como básicas e, por essa razão, é necessário que os algoritmos que as
implementem sejam eficientes. Outras operações, também importantes, podem ser
mencionadas: a alteração de um elemento da lista, a combinação de duas ou mais listas
lineares em uma única, a ordenação dos nós segundo um determinado campo, a determinação
do primeiro (ou do último) nó da lista, a determinação da cardinalidade da lista e muitas
outras, dependendo do problema em estudo.

Casos particulares de listas são de especial interesse. Se as inserções e remoções são

permitidas apenas nas extremidades da lista, ela recebe o nome de deque (uma abreviatura do
inglês double ended 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. Operações referentes a esses casos
particulares serão analisadas individualmente.

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. O primeiro
caso corresponde à alocação sequencial de memória, enquanto o segundo é conhecido como
alocação encadeada. A escolha de um ou outro tipo depende essencialmente das operações
que serão executadas sobre a lista, do número de listas envolvidas na operação, bem como
das características particulares dessas listas. Nas seções que se seguem, tais alocações e suas
características serão discutidas.

O capítulo está organizado da seguinte maneira. O estudo é iniciado pela alocação sequencial,
apresentada na Seção 2.2. Em seguida, são examinadas as listas lineares estruturadas sob
forma sequencial. São descritos os algoritmos básicos de busca e efetuado o cálculo da
complexidade média. Nessa mesma seção é também apresentada a busca binária. As pilhas e
filas são estudadas na Seção 2.4. A Seção 2.5 apresenta, como aplicação, a notação polonesa
para expressões aritméticas. A alocação encadeada é objeto da Seção 2.6. O estudo das listas
lineares em alocação encadeada é efetuado na Seção 2.7. São examinadas as listas
simplesmente encadeadas: pilhas e filas em alocação encadeada, as listas circulares, bem
como as listas duplamente encadeadas. Ainda nessa seção é estudado, como aplicação, o
problema da ordenação topológica. A seção se encerra com o exame de listas com nós de
tamanho variável.

2.2Alocaçã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. A correspondência entre o índice da tabela e o
endereço real é feita automaticamente pela linguagem de programação quando da tradução
do programa.

Como a implementação da alocação sequencial em linguagens de alto nível é geralmente

realizada com a reserva prévia de memória para cada estrutura utilizada, a inserção e a
remoção de nós não ocorrem de fato. Em vez disso utiliza-se algum tipo de simulação para
essas operações (por exemplo, variáveis indicando os limites da memória realmente utilizada).
Por essa razão, pode-se considerar tal alocação como uma alocação estática.

O armazenamento sequencial é particularmente atraente no caso de filas e pilhas porque,

nessas estruturas, as operações básicas podem ser implementadas de forma bastante
eficiente. Esse tratamento pode, contudo, se tornar oneroso em termos de memória quando
se empregam diversas estruturas simultaneamente. Nesse caso, a utilização ou não do
armazenamento sequencial dependeria de um estudo cuidadoso das opções existentes.

De início serão apresentadas as operações para listas genéricas.

2.3Listas Lineares em Alocação Sequencial

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. A chave, quando presente, se constitui em um dos campos do nó. Os nós podem se
encontrar ordenados, ou não, segundo os valores de suas chaves. No primeiro caso a lista é
denominada ordenada, e não ordenada no caso contrário.

Suponha uma lista linear, de nome L, que possui n elementos. Um exemplo da constituição
dessa tabela é apresentado na Figura 2.1.

O Algoritmo 2.1 apresenta a busca de um nó na lista L, conhecendo-se sua chave. A variável x

corresponde à chave do nó procurado. A função busca1 informa, ao final, o índice do nó que se
deseja buscar; se este não for encontrado, o índice é nulo.

FIGURA 2.1 Exemplo de um nó.

■ Algoritmo 2.1Busca de um elemento na lista L

função busca1(x)

i := 1; busca1 := 0

enquanto i≤ n faça

se L[i] . chave = x então

busca1 := i % chave encontrada

i := n + 1

senão i := i + 1 % pesquisa prossegue

Observe que, para cada elemento da tabela referenciado na busca, o algoritmo realiza dois
testes: i ≤ n e L[i] . chave = x. Muitas vezes um pequeno artifício pode contribuir para a
melhoria do processo. Por exemplo, o Algoritmo 2.2 se propõe a efetuar a mesma busca que o
Algoritmo 2.1. A diferença entre os dois é a criação de um novo nó, que possui o valor
procurado no campo chave, na posição n + 1. Dessa forma, o algoritmo sempre encontra um
nó da tabela com as características desejadas, evitando o teste de fim de tabela.

■ Algoritmo 2.2Busca de um elemento na lista L

função busca(x)

L[n + 1] . chave := x; i := 1

enquanto L[i] . chave ≠ x faça

i := i + 1

se i ≠ n + 1 então

busca := i % elemento encontrado

senão busca := 0 % elemento não encontrado

A complexidade de pior caso dos Algoritmos 2.1 e 2.2 é O(n). Entretanto, o segundo é de
execução mais rápida, pois a cada iteração correspondem dois testes no Algoritmo 2.1 e
apenas um no 2.2.

As complexidades médias dos Algoritmos 2.1 e 2.2 também são idênticas. Para determiná-las,
seja q a probabilidade de sucesso no resultado da busca. Além disso, suponha que sejam
idênticas as probabilidades de a chave procurada se encontrar em posições distintas da lista. A
observação fundamental para calcular a complexidade média é que, para o algoritmo,
entradas distintas que tenham a chave procurada na mesma posição podem ser consideradas
como idênticas. Assim, o algoritmo só reconhece n + 1 entradas distintas, a saber: entradas em
que a chave procurada se encontra na posição 1, posição 2, …, posição n e entradas em que a
chave não se encontra na lista.

Pelo Capítulo 1, sabe-se que a complexidade média é dada por ∑ p(Ek)t(Ek). No caso, há
somente n + 1 entradas a considerar. Seja Ei, 1 ≤ i ≤ n, uma entrada em que a chave procurada
ocupa a i-ésima posição da lista, e E0 a entrada que corresponde à busca sem sucesso. Logo, as
probabilidades das entradas são

p(Ek) = q/n, 1 ≤ k ≤ n

p(E0) = 1 – q,

enquanto o número total de passos efetuados pelo algoritmo é

t(Ek) = k, 1 ≤ k ≤ n

t(E0) = n.
Logo, a expressão da complexidade média é

Como casos particulares, se q = 1, isto é, a chave se encontra sempre na lista, então a

complexidade é ≈n/2. Se q = 1/2, esta cresce para ≈3n/4. Se q = 0, isto é, todas as buscas são
sem sucesso, a complexidade média atinge o valor n.

Quando a lista está ordenada, pode-se tirar proveito desse fato. Se o número procurado não
pertence à lista não há necessidade de percorrê-la até o final. A exemplo do Algoritmo 2.2, a
dupla comparação no bloco principal do algoritmo também pode ser evitada por meio da
criação de um novo nó. O Algoritmo 2.3 mostra essa busca.

■ Algoritmo 2.3Busca de um elemento na lista L, ordenada

função busca-ord(x)

L[n + 1] . chave := 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-ord := 0

senão busca-ord := i

A complexidade de pior caso do algoritmo acima é, evidentemente, igual à dos algoritmos

anteriores. Contudo, a maior eficiência do algoritmo se traduz na expressão da complexidade
média. No seu cálculo, utilizam-se as mesmas premissas. Isto é, q é a probabilidade de sucesso
do resultado da busca. Além disso, entradas em que a chave procurada se encontra em
posições distintas da lista possuem a mesma probabilidade de ocorrência. Contudo, ao
contrário do caso anterior, o algoritmo, agora, é sensível a um total de 2n + 1 entradas
distintas, uma vez que, no Algoritmo 2.3, também o insucesso pode ser reportado em
situações distintas. Com isso, o número de passos efetuados t por uma busca sem sucesso
torna-se variável. Por hipótese, os diferentes valores de t possuem a mesma probabilidade de
ocorrência.
Para resolver o problema do caso médio, é necessário introduzir as definições seguintes. Sejam
R0, …, Rn conjuntos de elementos não pertencentes à lista, representando os “espaços” entre
as chaves da lista em que a chave procurada poderia se encontrar. Isto é, R0 representa todos
os valores possíveis menores do que a primeira chave de L, Rn corresponde aos valores
maiores do que a última chave de L, enquanto Rk, 1 ≤ k < n, é o conjunto dos valores maiores
do que a k-ésima e menores do que a (k + 1)-ésima. No caso de uma busca sem sucesso, a
chave procurada se encontra em um dos conjuntos Rk.

As 2n + 1 entradas distintas podem ser descritas como:

Ek = entrada em que a chave procurada é L[k] . chave, 1 ≤ k ≤ n;

= entrada em que a chave procurada pertence a Rk, 0 ≤ k ≤ n.

As probabilidades das entradas são:

p(Ek) = q/n, 1 ≤ k ≤ n

p() = (1 – q)/(n + 1), 0 ≤ k ≤ n,

enquanto os números de iterações correspondentes são:

t(Ek) = k, 1 ≤ k ≤ n

t() = k + 1, 0 ≤ k ≤ n

Logo, a expressão da complexidade média é:

Para efeito de comparação com os Algoritmos 2.1 e 2.2, observe que o valor da complexidade
média correspondente ao Algoritmo 2.3 é aproximadamente n/ 2, para qualquer probabilidade
q.
Ainda no caso de listas ordenadas, um algoritmo diverso e bem mais eficiente pode ser
apresentado: a busca binária. A ideia básica do algoritmo é percorrer a tabela como se folheia,
por exemplo, uma lista telefônica, abandonando-se as partes do catálogo onde o nome
procurado, com certeza, não será encontrado. Em tabelas, o primeiro nó pesquisado é o que
se encontra no meio; se a comparação não é positiva, metade da tabela pode ser abandonada
na busca, uma vez que o valor procurado se encontra ou na metade inferior (se for menor), ou
na metade superior (se for maior). Esse procedimento, aplicado recursivamente, esgota a
tabela. O Algoritmo 2.4 apresenta a busca.

■ Algoritmo 2.4Busca binária

função busca-bin(x)

inf := 1; sup := n; busca- bin := 0

enquanto inf ≤ sup faça

meio := ⎣(inf + sup)/2⎦ % índice a ser buscado

se L[meio] . chave = x então

busca- bin := meio % elemento encontrado

inf := sup + 1

senão se L[meio] . chave < x então

inf := meio + 1

senão sup := meio – 1

A complexidade do algoritmo pode ser avaliada da seguinte forma. O pior caso ocorre quando
o elemento procurado é o último a ser encontrado, ou mesmo não é encontrado, isto é,
quando a busca prossegue até a tabela se resumir a um único elemento. Na primeira iteração,
a dimensão da tabela é n, e algumas operações são realizadas para situar o valor procurado.
Na segunda, a dimensão se reduz a ⎣n/2⎦, e assim sucessivamente. Ora, ao final, a dimensão da
tabela é 1 (observe o teste inf ≤ sup). Então, no pior caso:

1a iteração: a dimensão da tabela é n,

2a iteração: a dimensão da tabela é ⎣n/2⎦,

3a iteração: a dimensão da tabela é ⎣(⎣n/2⎦)/2⎦,

…

ma iteração: a dimensão da tabela é 1.

Ou seja, o número de iterações é, no máximo, 1 + ⎣log2 n⎦. O tempo consumido pelas

operações em cada iteração é constante. Logo, a complexidade da busca binária é O(log n).

Ambas as operações de inserção e remoção utilizam o procedimento de busca. No primeiro

caso, o objetivo é evitar chaves repetidas e, no segundo, a necessidade de localizar o elemento
a ser removido. A construção desses algoritmos implica tarefas complementares, uma vez que
a ação de um é o inverso da ação do outro. A implementação dessas operações deve,
naturalmente, respeitar tal fato. O Algoritmo 2.5 apresenta a inserção de um nó contido na
variável novo de chave x. O Algoritmo 2.6 efetua a remoção de um nó sendo conhecido um de
seus campos, no caso a chave x. Ambos os algoritmos consideram tabelas não ordenadas. A
memória pressuposta disponível tem M posições (na realidade M + 1, porque é necessária uma
posição extra para o procedimento de busca). Devem-se levar em conta as hipóteses de se
tentar fazer inserções numa lista que já ocupa M posições (situação conhecida como
overflow), bem como a tentativa de remoção de um elemento de uma lista vazia (underflow).
A atitude a ser tomada em cada um desses casos depende do problema tratado. Por essa
razão, os procedimentos overflow e underflow são apenas indicados.

Como pode ser observado, o procedimento de inserção propriamente dito é bem simples,
porém depende da busca que tem complexidade de O(n). O algoritmo de remoção, além da
busca, em geral efetua movimentação de nós, o que o torna ainda mais lento, se bem que
também de complexidade O(n).

■ Algoritmo 2.5Inserção de um nó na lista L

se n < M então

se busca(x) = 0 então

L[n + 1] := novo-valor

n := n + 1

senão “elemento já existe na tabela”

senão overflow

Uma alternativa ao algoritmo de remoção é efetuar o deslocamento do último elemento da

lista para a posição vaga. Nesse caso, entretanto, a sequência dos elementos fica alterada.
■ Algoritmo 2.6Remoção de um nó da lista L

se n ≠ 0 então

indice := busca(x)

se indice ≠ 0 então

valor- recuperado := L[indice]

para i := indice, n – 1 faça

L[i] := L[i + 1]

n := n – 1

senão “elemento não se encontra na tabela”

senão underflow

No caso de tabelas ordenadas, o algoritmo de remoção não se modifica. O algoritmo de

inserção, entretanto, precisa ser refeito, uma vez que, nesse caso, a posição do nó se torna
relevante. Isso implica movimentar parte da tabela, para permitir a inserção na posição
correta, de maneira análoga à efetuada na remoção em listas não ordenadas (Algoritmo 2.6). A
complexidade de ambos os algoritmos (inserção e remoção) é, então, O(n).

Observe que a utilização da busca binária diminui a complexidade da busca, mas não a da
inserção ou da remoção. A complexidade dessas últimas operações é determinada pela
movimentação dos nós.