Capı́tulo 2

Listas Lineares
Edmilson Marmo Moreira
Universidade Federal de Itajubá - UNIFEI
Instituto de Engenharia de Sistemas e Tecnologia da Informação - IESTI

“Os preguiçosos estão sempre a falar do que tencionam fazer, do que hão de realizar;
aqueles que verdadeiramente fazem alguma coisa não têm tempo de falar nem sequer do
que fazem”.

Goethe

1 Considerações Iniciais
Dentre as estruturas de dados não primitivas, as listas lineares são as de manipulação mais
simples. 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 realiade, são inúmeros os tipos de dados que podem ser descritos por listas lineares
(SZWARCFITER; MARKENZON, 1994).
Uma lista linear é 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 deter-

minado elemento, o que, aliás, ocorre na maioria das estruturas de dados. Tais operações são
consideradas como primitivas. Outras operações, também importantes, podem ser menciona-
das: a alteração de um elemento na 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 (SZWARCFITER; MARKENZON, 1994).
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 sequêncial 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.

1
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 2

2 Lista Estática Sequencial

Uma lista estática sequencial, também conhecida como lista por contiguidade, é um
arranjo de registros onde estão estabelecidas regras de precedência entre seus elementos ou é
uma coleção ordenada de componentes do mesmo tipo (PIMENTEL; OLIVEIRA, 2006). Desta
forma, o sucessor de um elemento ocupa posição fı́sica subsequente. Uma lista telefônica é um
exemplo deste tipo de estrutura.
Para a implementação desta estrutura são utilizados vetores e registros, conforme ilustra a
figura 1.

Figura 1: Exemplo de uma lista estática sequencial

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?

Além disso, estas respostas podem ser realizadas em tempo constante, sendo esta a maior
vantagem deste tipo de estrutura. Entretanto, as operações de inserção e remoção exigirão mais
cuidados.
A declaração a seguir especifica uma estrutura para representar uma lista estática sequencial:

#define TAM 10;

struct No {
char Chave;
int Valor;
};
struct ListaSequencial {
No Dados[TAM];
int Fim;
};

Basicamente, há necessidade de um vetor para armazenar os elementos da lista que, neste
caso, são do tipo No. Este tipo, em verdade, apenas sinaliza uma estrutura com as informações
que serão utilizadas pela aplicação. O campo Fim da estrutura ListaSequencial representa a
posição do último elemento válido na lista dentro do vetor.
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 3

2.1 Inserção de um nó em uma lista sequencial

A técnica para inserir um nó em uma lista estática sequencial é relativamente simples. Se
existir espaço disponı́vel na lista, deve-se procurar a posição em que o novo elemento deverá ser
inserido. Esta posição depende do critério de ordenação utilizado como, por exemplo, a ordem
alfabética. Supondo que K seja a posição onde um nó deve ser inserido, então deve-se mover o
elemento K para a posição K + 1, o elemento K + 1 para a posição K + 2, e assim por diante.
Ou seja, deve-se gerar espaço para a inserção do novo elemento. Obviamente, esta sequência de
operações deve ser iniciada pelo final da lista para preservar o conteúdo do vetor.
A função seguinte ilustra o procedimento descrito:

bool InsereListaSeq (ListaSequencial &L, No Novo)

{
if ([Link] == TAM - 1)
return false;
else {
int i = 0, p;
while ((i <= [Link]) && ([Link][i].Chave < [Link]))
i++;
p = i;
i = [Link];
while (i > p-1) {
[Link][i+1] = [Link][i];
i--;
}
[Link][p] = Novo;
[Link]++;
return true;
}
}

É preciso destacar o fato de que a lista deve ser inicializada. Neste caso, basta atribuir o
valor -1 ao campo Fim, sinalizando que a lista está vazia.

2.2 Remoção de um nó da lista sequencial

O procedimento para remover um nó da lista estática sequencial é análogo ao descrito para
inserção. Deve-se, primeiramente, procurar a posição onde se encontra o nó que se deseja
remover. Se este nó for encontrado, deve-se substituir o conteúdo desta posição (supondo K)
pelo conteúdo da próxima posição no vetor (K+1), a posição seguinte (K+1) deve ser preenchida
com o conteúdo da posição subsequente (K + 2) e assim sucessivamente.
A função seguinte implementa o procedimento descrito:

bool RetiraListaSeq (ListaSequencial& L, No& N)

{
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 4

int i = 0;
while ((i <= [Link]) && ([Link][i].Chave != [Link]))
i++;
if (i > [Link])
return false;
N = [Link][i];
while (i < [Link]) {
[Link][i] = [Link][i+1];
i++;
}
[Link]--;
return true;
}

A função de remoção utiliza o campo Chave da estrutura No para localizar a informação

desejada, preservando as informações do nó que está sendo removido na variável parâmetro N.

3 Lista Estática Encadeada

A representação das listas lineares por continguidade dos nós, apresenta dois problemas:

1. O número máximo de nós na lista é limitado ao tamanho do vetor.

2. Algumas das primitivas implementadas para representação por contiguidade comprome-

tem o desempenho da lista por representar um grande esforço computacional em algumas
operações. Por exemplo, para a inserção de um nó na primeira posição de uma lista com
2000 nós, serão necessários duas mil atribuições (deslocamento de 2000 nós uma posição
adiante) e mais uma atribuição para a inserção efetiva do nó.

Para resolver o segundo problema, pode-se utilizar um mecanismo conhecido como encade-
amento dos nós. A figura 2 ilustra esta estrutura. Cada elemento da lista no vetor será um
registro com dois campos: o campo Info (informação), que será utilizado para armazenar os
valores na lista, e o campo Lig (ligação), utilizado para propiciar o encadeamento na lista, ou
seja, este campo irá indicar a posição do próximo nó na lista.
Existem duas listas nesta estrutura. A lista de disponı́veis, indicada pela variável Dispo, e
a lista propriamente dita, indicada pela variável Com. O valor -1 indica o fim das duas listas
mantidas nesta estrutura.
A próxima declaração especifica uma estrutura para representar uma lista estática encadeada:

#define TAM 10;

struct No {
char Info;
int Lig;
};
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 5

Figura 2: Exemplo de uma lista estática encadeada

struct ListaEstaticaEncadeada {
int Com;
int Dispo;
No Dados[TAM];
};

Nesta nova representação, o número de nós na lista continua sendo limitado, uma vez que a
lista está implementada utilizando vetor, no entando os processos de inserção e remoção dos nós
serão simplificados pelo acerto de apontadores (campo de ligação). A figura 3 ilustra o acerto
dos apontadores após a inserção de um nó e a figura 4 ilustra o procedimento de remoção.

Figura 3: Exemplo de inserção em uma lista encadeada

3.1 Primitiva de inserção

Como foi dito, o processo de inserção de um nó foi simplificado pelo acerto de apontadores.
Para a primitiva InsereLista, é preciso se preocupar com as seguintes situações:

• Se a lista estiver vazia. Neste caso, passará a ter um único nó e a lista começará neste nó.
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 6

Figura 4: Exemplo de remoção em uma lista encadeada

• Inserção de um nó como primeiro da lista (menor critério de ordem). Aqui, o novo nó será
o começo da lista.

• Se a inserção do novo nó ocorrer no meio ou no fim da lista. Neste caso, será feito um
acerto de apontadores como descrito anteriormente.

A função seguinte ilustra o procedimento de inserção:

bool InsereLista (ListaEstaticaEncadeada& L, char Novo)

{
if ([Link] == -1)
return false;
else {
if ([Link] == -1) {
[Link] = [Link];
[Link] = [Link][[Link]].Lig;
[Link][[Link]].Info = Novo;
[Link][[Link]].Lig = -1;
} else {
int Ant = -1;
int Aux = [Link];
while ((Aux != -1) && ([Link][Aux].Info < Novo)) {
Ant = Aux;
Aux = [Link][Aux].Lig;
}
Aux = [Link];
[Link] = [Link][[Link]].Lig;
[Link][Aux].Info = Novo;
if (Ant == -1) {
[Link][Aux].Lig = [Link];
[Link] = Aux;
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 7

} else {
[Link][Aux].Lig = [Link][Ant].Lig;
[Link][Ant].Lig = Aux;
}
}
return true;
}
}

3.2 Inicialização da lista estática encadeada

Na lista estática sequencial a única ação que deve ser executada para iniciar a lista é atribuir
o valor -1 ao seu campo Fim. Isso não é o mesmo na lista encadeada. Para utilizar uma lista
estática encadeada é necessário que as ligações estejam estabelecidas para a lista de disponı́veis,
ou seja, ao iniciar uma lista estática encadeada, a lista representada pela variável Com deve
estar vazia (valendo -1) e todos os elementos do vetor estão disponı́veis para serem utilizados,
formando uma lista de disponı́veis.
Por conseguinte, um procedimento de inicialização deve ser acionado antes da inserção de
nós na lista. Este procedimento irá atualizar as ligações da lista de disponı́veis, conforme ilustra
o código a seguir:

void IniciaLista (ListaEstaticaEncadeada& L)

{
for (int i=0; i<TAM; i++)
[Link][i].Lig = i+1;
[Link][TAM-1].Lig = -1;
[Link] = 0;
[Link] = -1;
}

3.3 Primitiva de remoção

Para remover um nó de uma lista estática encadeada, é preciso atenção para as seguintes
situações:

• Remoção do primeiro nó da lista. Neste caso, deve-se mudar o apontador de começo da
lista para o segundo nó.

• O nó a ser removido está no meio da lista. Aqui, as ligações devem ser refeitas conforme
discutido anteriormente.

• A lista está vazia ou o nó a ser removido não se encontra na lista. Neste caso, a função
deve retornar false indicando que a remoção não pode ser realizada.

É importante considerar ainda que a remoção de um nó implica na inserção deste nó na lista
de disponı́veis, ou seja, após a atualização das ligações da lista principal, o espaço ocupado pelo
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 8

nó deve voltar para a lista de disponı́veis. Portanto, também será preciso atualizar as ligações
da lista de disponı́veis.
A função seguinte apresenta a codificação do método de remoção:

bool RetiraLista (ListaEstaticaEncadeada& L, char Novo)

{
int Ant = -1;
int Aux = [Link];
while ((Aux != -1) && ([Link][Aux].Info != Novo)) {
Ant = Aux;
Aux = [Link][Aux].Lig;
}
if (Aux == -1)
return false;
if (Aux == [Link])
[Link] = [Link][[Link]].Lig;
else
[Link][Ant].Lig = [Link][Aux].Lig;
[Link][Aux].Lig = [Link];
[Link] = Aux;
return true;
}

4 Lista Dinâmica
Foi possı́vel, através do encadeamento, resolver o problema do desempenho dos algoritmos
de inserção e remoção da lista sequêncial. Para solucionar o problema do limite de elementos,
provocado pela estrutura de vetor, é possı́vel a utilização de ponteiros, ou seja, alocação dinâmica
de memória.
Para utilizar alocação dinâmica de memória será preciso alterar a estrutura No. Este tipo
de estrutura deve ser autorreferente, isto é, deve conter um membro ponteiro que armazena o
endereço de outra estrutura do mesmo tipo. Por exemplo, o trecho de código abaixo define um
tipo No que é uma estrutura autorreferente:

struct No {
char Info;
No * Lig;
};

4.1 Primitiva de inserção em listas dinâmicas

A lógica utilizada para inserir um nó em uma lista dinâmica é semelhante àquela usada na
lista estática, entretanto, ao contrário da lista estática, os parâmetros passados para a função
são:
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 9

• o ponteiro para o inı́cio da lista; e

• o dado a ser inserido.

Portanto, não há mais necessidade de passar o vetor que representa a lista encadeada e nem o
apontador de disponı́veis, pois toda a memória está disponı́vel para a alocação. Neste contexto,
também não é preciso se preocupar com o controle dos nós disponı́veis.
A função seguinte apresenta o código, semelhante ao da estrutura estática, para a lista
encadeada dinâmica:

void InsereLista (NoPtr& L, char Novo)

{
if (L == NULL) {
L = new No;
L->Info = Novo;
L->Lig = NULL;
} else {
NoPtr Ant = NULL;
NoPtr Aux = L;
while ((Aux != NULL) && (Aux->Info < Novo)) {
Ant = Aux;
Aux = Aux->Lig;
}
Aux = new No;
Aux->Info = Novo;
if (Ant == NULL) {
Aux->Lig = L;
L = Aux;
} else {
Aux->Lig = Ant->Lig;
Ant->Lig = Aux;
}
}
}

Para facilitar a manipulação do ponteiro de inı́cio da lista, foi definido um novo tipo para
um ponteiro de nó (typedef No * PtrNo). Além disso, a função InsereLista não possui valor
de retorno (void), pois não há necessidade de testar se a lista está cheia.

4.2 Primitiva de remoção em listas dinâmicas

A remoção em listas dinâmicas também segue o mesmo fundamento utilizado na inserção.
O código utilizado deriva naturalmente da estrutura estática.

bool RetiraLista (NoPtr& L, char N)

 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 10

{
NoPtr Ant = NULL;
NoPtr Aux = L;
while ((Aux != NULL) && (Aux->Info != N)) {
Ant = Aux;
Aux = Aux->Lig;
}
if (Aux == NULL)
return false;
if (Aux == L)
L = L->Lig;
else
Ant->Lig = Aux->Lig;
delete Aux;
return true;
}

Finalmente, é preciso considerar que não há necessidade de uma função para iniciar a lista
dinâmica, basta fazer com que o ponteiro de inı́cio da lista comece valendo NULL.

5 Listas Duplamente Encadeadas

Nos algoritmos vistos anteriormente para listas lineares utilizando alocação encadeada, o
ponteiro Ant se mostrou sempre útil. Sua função é “rastrear” o ponteiro que percorre a lista,
permitindo sempre o retorno ao nó anterior. Algumas vezes, entretanto, isto não é suficiente,
pois, pode-se desejar o percurso da lista nos dois sentidos indiferentemente. Nestes casos, o gasto
de memória imposto por um novo campo de ponteiro pode ser justificado pela economia em não
reprocessar praticamente a lista inteira (SZWARCFITER; MARKENZON, 1994).
A figura 5 apresenta uma lista duplamente encadeada. A principal caracterı́stica deste
tipo de estrutura é a possibilidade de, a partir de qualquer nó, percorrer a lista para o nó anterior
ou posterior.

Figura 5: Ilustração de lista duplamente encadeada

Devido à semelhança entre as funções de inserção e remoção das listas simplesmente e du-
plamente encadeada será apresentado apenas o algoritmo de inserção, ficando a primitiva de
remoção como sugestão de exercı́cio.

struct No {
char Info;
No * Ant;
No * Pos;
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 11

};
typedef No * NoPtr;

void InsereLista (NoPtr& L, char Novo)

{
if (L == NULL) {
L = new No;
L->Info = Novo;
L->Ant = L->Pos = NULL;
} else {
NoPtr Aux = L;
NoPtr Ant = NULL;
while ((Aux != NULL) && (Aux->Info < Novo)) {
Ant = Aux;
Aux = Aux->Pos;
}
Aux = new No;
Aux->Info = Novo;
if (Ant == NULL) {
Aux->Pos = L;
Aux->Ant = NULL;
L->Ant = Aux;
L = Aux;
} else {
Aux->Pos = Ant->Pos;
Aux->Ant = Ant;
if (Ant->Pos != NULL)
Aux->Pos->Ant = Aux;
Ant->Pos = Aux;
}
}
}

É importante destacar as modificações que foram realizadas na estrutura de dados No. Os

campos de ponteiros tomam os nomes de Ant (apontando para o nó anteriror) e Pos (apontando
o nó seguinte). Além disso, na função de inserção da lista simplesmente encadeada apenas duas
situações foram consideradas para o acerto dos ponteiros com o novo nó:

1. Quando o novo nó é o primeiro da lista. Neste caso, há a necessidade de acertar o ponteiro
de inı́cio da lista (ponteiro L).

2. Quando o novo nó não é o primeiro da lista.

Na lista duplamente encadeada o último nó não pode ser trabalhado de forma idêntica aos
nós internos da lista. Por conseguinte, três situações foram tratadas na primitiva:
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 12

1. Quando o novo nó é o primeiro da lista.

2. Quando o novo nó fará parte dos nós internos da lista, ou seja, não será nem o primeiro
nem o último.

3. Quando o novo nó será o último nó da lista.

6 Lista com Descritores

Um nó descritor de uma lista é aquele que descreve informações gerais da lista. Este nó
reúne as referências ao inı́cio e ao fim da lista. O acesso aos elementos da lista será sempre
efetuado através do seu descritor (VELOSO et al., 1986).
O nó descritor pode conter outras informações sobre a lista, a critério do projetista, tais
como: quantidade de nós na lista, descrição dos dados contidos nos nós, etc.
A figura 6 mostra esquematicamente uma lista encadeada com nó descritor, no qual foi
incluı́do um campo que indica a quantidade de nós existentes na lista. Nesta nova estrutura, a
variável lista aponta para o nó descritor e não para o primeiro nó da lista.

Figura 6: Esquema de lista encadeada com nó descritor

O nó descritor, neste caso, é um dado com a seguinte definição:

struct NoDescritor {
No * Com;
int Nro;
No * Fim;
};
typedef NoDescritor * DescritorPtr;

Usando esta nova estrutura de lista, passa a ser necessária a existência de uma nova operação:
criar uma lista vazia. Esta operação consiste em alocar um nó do tipo descritor, tornar as suas
referências nulas, e fazer a variável que indica o inı́cio da lista apontar para o nó. A rotina
CriarDescritor, a seguir, implementa esta operação:

void CriarDescritor (DescritorPtr& D)

{
D = new NoDescritor;
D->Com = D->Fim = NULL;
D->Nro = 0;
}
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 13

A seguir, são apresentados outras funções para manipulação de listas encadeadas com des-
critor. A primeira, InsereEsquerda, implementa a operação de inserção de um nó com o dado
valor à esquerda da lista cujo descritor é apontado pela variável D.

void InsereEsquerda (DescritorPtr& D, char Novo)

{
NoPtr P = new No;
P->Info = Novo;
if (D->Nro == 0) {
D->Com = D->Fim = P;
P->Lig = NULL;
} else {
P->Lig = D->Com;
D->Com = P;
}
D->Nro++;
}

O procedimento seguinte, InsereDireita, implementa a operação de inserção de um nó com

o dado valor à direita da lista cujo descritor é apontado por D.

void InsereDireita (DescritorPtr& D, char Novo)

{
NoPtr P = new No;
P->Info = Novo;
P->Lig = NULL;
if (D->Nro == 0)
D->Com = D->Fim = P;
else {
D->Fim->Lig = P;
D->Fim = P;
}
D->Nro++;
}

Para remover o nó da esquerda de uma lista, pode-se utilizar a função RemoveEsquerda, a
seguir. Esta rotina remove o primeiro nó da lista, se houver, e retorna o dado que o nó removido
continha através do parâmetro Valor.

bool RemoveEsquerda (DescritorPtr& D, char& Valor)

{
if (D->Nro == 0)
return false;
else {
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 14

NoPtr P = D->Com;
Valor = P->Info;
D->Com = P->Lig;
D->Nro--;
if (D->Nro == 0)
D->Fim = NULL;
}
}

A operação de remoção do nó à direita da lista com descritor envolve o mesmo problema
apresentado para o caso de listas sem descritor: a necessidade de percorrer todos os nós da lista,
sequencialmente, a partir do primeiro (da esquerda), até atingir o nó da direita. Este problema
pode ser evitado com o uso de listas duplamente encadeadas.

7 Listas com Sentinelas

Durante a busca por um nó em uma lista encadeada, o código utilizado foi algo similar a:

while ((Aux != NULL) && (Aux->Info != Valor))

Aux = Aux->Lig;

Entretanto, esta estrutura apresenta um problema sutil. No caso do ponteiro Aux ser NULL,
o comando pode ser inválido, pois Aux->Info não existe. Se o compilador não realiza o segundo
teste no caso do primeiro falhar, não haveria problema. Em nı́vel de algoritmo, é melhor resolver
o problema evitando a possibilidade desse tipo de erro ocorrer, ao invés de usar soluções que
dependem do compilador (PIMENTEL; OLIVEIRA, 2006).
Uma possibilidade de solução para o problema exposto seria um código semelhante ao descrito
a seguir:

Acabou = false;
while ((Aux != NULL) && (!Acabou))
if (Aux->Info == Valor)
Acabou = true;
else
Aux = Aux->Lig;

Apesar de resolver o problema do ponteiro nulo, este código adiciona novos testes o que pode
diminuir a eficiência do método de busca.
Um elemento sentinela pode ser utilizado na busca em listas encadeadas. Basta, para isso,
usar um registro no final da lista. Neste contexto, uma lista vazia não será aquela cujo apontador
é NULL, mas aquela cujo ponteiro tem o endereço do nó sentinela.
A função a seguir ilustra o procedimento de inicialização de uma lista com sentinela:

void CriarLista (NoPtr& L, NoPtr& Sentinela)

{
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 15

Sentinela = new No;

L = Sentinela;
}

O código seguinte implementa uma busca por um elemento Valor na lista apontada por L
não ordenada. Esta função retorna NULL caso o elemento não seja encontrado; caso contrário,
a função retorna o endereço do registro que contém o elemento.

NoPtr Busca (NoPtr L, char Chave, NoPtr Sentinela)

{
NoPtr Aux = L;
Sentinela->Info = Chave;
while (Aux->Info != Chave)
Aux = Aux->Lig;
if (Aux == Sentinela)
return NULL;
else
return Aux;
}

Observa-se como o uso de sentinelas pode melhorar o desempenho da busca. Antes de

percorrer a lista, é inserido no campo Info da sentinela o elemento que está sendo procurado.
Nesta situação, a informação sempre será encontrada e, assim, não há necessidade de testar o
final da lista.

8 Listas Circulares
Em algumas situações é necessário o uso de uma lista circular, na qual os nós formam um
anel: a lista é finita e cada nó tem um sucessor. Um exemplo de tal situação é quando diversos
processos de um Sistema Operacional estão usando os mesmos recursos ao mesmo tempo, sendo
necessário assegurar que nenhum processo acesse o recurso antes de todos os outros processos.
Em consequência, todos os processos são colocados em uma lista circular, acessı́veis através do
ponteiro de inı́cio da lista, conforme ilustra a figura 7. Depois que um nó da lista é acessado e o
número do processo é recuperado do nó para ativar esse processo, o ponteiro de inı́cio se move
para o próximo nó de modo que o próximo processo possa ser ativado a seguir (DROZDEK,
2002).

Figura 7: Ilustração de lista circular

O conceito de lista circular pode ser aplicado às listas simplemente encadeadas, bem como
às listas duplamente encadeadas.
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 16

9 Outros Tipos de Listas

As listas encadeadas lineareas são os tipos de listas mais comuns, entretanto, o mecanismo
de encadeamento permite criar estruturas mais complexas, que podem ser usadas nas soluções
de diversos problemas. Esta seção apresenta as caracterı́sticas gerais de três destas estruturas:
listas generalizadas, listas de salto e listas cruzadas.

9.1 Lista generalizada

Uma lista tı́pica na linguagem LISP é da forma L1 = (a, (b, c)) e uma tı́pica lista da linguagem
PROLOG é da forma L2 = [a, [b, c]]. Nestes exemplos, ambas as listas contêm dois elementos:
o primeiro elemento é o átomo a e o segundo elemento é a lista formada pelos elementos b e c.
Para representar essas listas, é necessário uma estrutura que permita dizer quando um ele-
mento é um átomo ou um ponteiro para outra lista.
Uma lista generalizada é aquela que pode ter como elemento um átomo ou um outra lista
(sub-lista). Toda lista pode ser apresentada usando-se a estrutura de nó onde cabeça é um atomo
ou um ponteiro para outra lista, cauda é o ponteiro para a cauda da lista (próximo elemento) e
o campo (Tag) sinaliza se a cabeça é um átomo ou um ponteiro. Por conseguinte, este campo é
do tipo lógico (PIMENTEL; OLIVEIRA, 2006).
A figura 8 apresenta algumas listas generalizadas e ilustra as suas representações na memória.

Figura 8: Exemplos de listas generalizadas

O código a seguir apresenta um exemplo de declaração para a estrutura nó de uma lista
generalizada. Destaca-se o uso do construtor union das linguagens C/C++, que permite imple-
mentar o conceito de campo variável. Neste caso, o espaço ocupado pelo campo Cab será capaz
de armazenar um ponteiro ou um átomo. Como, no exemplo, o átomo é uma variável do tipo
char, o compilador reservará o espaço para um ponteiro, pois este ocupa um tamanho maior
que apenas um caracter.

struct No;
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 17

typedef No * NoPtr;
union Cabeca {
char Atomo;
NoPtr Ponteiro;
};
struct No {
bool Tag;
Cabeca Cab;
NoPtr Cauda;
};

A função ConstroiListaGeneralizada, a seguir, apresenta um código recursivo que permite

a um usuário entrar com a representação literal da lista generalizada e, por conseguinte, a função
irá construir a estrutura na memória.

void ConstroiListaGeneralizada (NoPtr& L)

{
char dado;
cin >> dado;
if ((dado != ’[’) && (dado != ’]’)) {
L = new No;
L->Tag = false;
L->[Link] = dado;
ConstroiListaGeneralizada(L->Cauda);
} else if (dado == ’[’) {
L = new No;
L->Tag = true;
ConstroiListaGeneralizada(L->[Link]);
ConstroiListaGeneralizada(L->Cauda);
} else
L = NULL;
}

9.2 Listas de salto

As listas encadeadas apresentam um sério problema: exigem varredura sequencial para loca-
lizar um elemento que está sendo procurado. A busca inicia no começo da lista e pára quando
encontra-se o elemento procurado ou quando o fim da lista é atingido sem encontrá-lo. A orde-
nação dos elementos na lista pode agilizar a busca, mas a busca sequencial ainda é exigida. Em
consequência, pode-se pensar em listas que permitam saltar certos nós para se evitar o processa-
mento sequencial. Uma lista de salto é uma variante interessante da lista encadeada ordenada
que torna uma busca não sequencial possı́vel (DROZDEK, 2002).
Em uma lista de salto de n nós, para cada k e i tal que 1 ≤ k ≤ blognc e 1 ≤ i ≤ bn/2k−1 c−1,
o nó na posição 2k−1 .i aponta para o nó na posição 2k−1 .(i + 1). Isso significa que cada segundo
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 18

nó aponta para o nó duas posições à frente, cada quarto nó aponta para o nó quatro posições à
frente e assim por diante, como mostrado na figura 9a. Isso é realizado com diferentes números
de ponteiros em nós na lista: metade dos nós tem somente um ponteiro, um quarto dos nós tem
dois ponteiros, um oitavo dos nós tem três ponteiros e assim por diante. O número de ponteiros
indica o nı́vel de cada nó, e o número de nı́veis é maxLevel = blgnc + 1.

Figura 9: Exemplos de listas de salto

A busca pelo elemento el consiste em seguir os ponteiros no nı́vel mais alto até que um
elemento seja encontrado, o que finaliza a busca com sucesso. No caso de se atingir o final da
lista ou de encontrar um elemento chave que seja maior do que el, a busca é reiniciada a partir
do nó que precede aquele contendo a chave, mas agora fixando um ponteiro num nı́vel mais
baixo do que antes. A busca continua até que el seja encontrado ou que os ponteiros do primeiro
nı́vel atinjam o final da lista, ou encontrem um elemento maior do que el.
Por exemplo, se for necessário encontrar o número 16 na lista da figura 9b, o nı́vel quatro
é tentado primeiro, o que não tem sucesso porque o primeiro nó nesse nı́vel tem valor 28. A
seguir, tenta-se a sublista do terceiro nı́vel, começando a partir da raiz: isso leva a 8 e, então,
a 17. Por isso, tenta-se a sublista de segundo nı́vel que se origina no nó contendo 8: isso leva a
10 e então novamente a 17. A última tentativa é iniciar a sublista do primeiro nı́vel que começa
no nó 10; esse primeiro nó da sublista tem 12, o próximo número é 17 e, desde que não haja um
nı́vel mais baixo, a busca é declarada como sem sucesso.
O código para o procedimento de busca é dado a seguir:

NoPtr BuscaEmListaDeSalto (NoPtr Raiz[], int maxNivel, char Chave)

{
NoPtr Ant, Aux;
int nvl;
for (nvl = maxNivel-1; nvl >= 0 && !Raiz[nvl]; nvl--);
if (nvl < 0)
return NULL;
Ant = Aux = Raiz[nvl];
while (true) {
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 19

if (Chave == Aux->Info)
return Aux;
else if (Chave < Aux->Info) {
if (nvl == 0)
return NULL;
else if (Aux == Raiz[nvl])
Aux = Raiz[--nvl];
else Aux = *(Ant->Lig + --nvl);
} else {
Ant = Aux;
if (*(Aux->Lig + nvl) != NULL)
Aux = *(Aux->Lig + nvl);
else {
for (nvl--; nvl >= 0 && *(Aux->Lig + nvl)==NULL; nvl--);
if (nvl >= 0)
Aux = *(Aux->Lig + nvl);
else
return NULL;
}
}
}
}

A busca parece ser eficiente. No entanto, o projeto de listas de salto pode levar a proce-
dimentos de inserção e remoção ineficientes. Para inserir um novo elemento, todos os nós que
seguem o nó inserido têm que ser re-estruturados; o número de ponteiros e os valores dos pon-
teiros têm que ser mudados. De modo a reter algumas das vantagens que as listas de salto
oferecem com relação à busca e evitar problemas em re-estruturar as listas ao inserir e remover
nós, a exigência sobre as posições dos nós de diferentes nı́veis é agora abandonada e somente a
exigência sobre o número de nós de diferentes nı́veis é mantida. Por exemplo, a lista na figura
9a se torna a lista da figura 9b: ambas têm seis nós com somente um ponteiro, três nós com dois
ponteiros, dois nós com três ponteiros e um nó com quatro ponteiros. A nova lista é pesquisada
exatamente do mesmo modo que a lista original. A inserção não exige re-estruturação da lista, e
os nós são gerados de modo que a distribuição deles em diferentes nı́veis seja mantida adequada
(DROZDEK, 2002).
Por exemplo, assumindo que maxN ivel = 4. Para 15 elementos, o número exigido de nós de
um ponteiro é oito, nós de dois ponteiros é quatro, nós de três ponteiros é dois e nós de quatro
ponteiros é um. Cada vez que um nó é inserido, um número não-sequencial r entre 1 e 15 é
gerado e, se r < 9, um nó de nı́vel um é inserido. Se r < 13, um nó de segundo nı́vel é inserido;
se r < 15, é um nó do terceiro nı́vel; se r = 15, um nó de nı́vel quatro é gerado e inserido. Se
maxN ivel = 5, então, para 31 elementos, a correspondência entre o valor de r e o nı́vel de nó é
esta:
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 20

r Nı́vel do nó a ser inserido

31 5
29-30 4
25-28 3
17-24 2
1-16 1

Para determinar tal correspondência entre r e o nı́vel do nó para qualquer maxN ivel, a
função DefinirLimites inicializa a matriz Limites[], colocando limites inferiores para cada
intervalo. Por exemplo, para maxN ivel = 4 a matriz é [1, 9, 13, 15] e para maxN ivel = 5,
[1, 17, 25, 29, 31]. A função EscolherNivel usa Limites[] para determinar o nı́vel do nó a ser
inserido. A seguir os códigos para DefinirLimites e EscolherNivel:

void EscolherLimites(int Limites[], int maxNivel)

{
Limites[maxNivel-1] = (2 << (maxNivel-1)) - 1;
for (int i = maxNivel-2, j = 0; i >= 0; i--, j++)
Limites[i] = Limites[i+1] - (2 << j);
}

int EscolherNivel(int Limites[], int maxNivel)

{
int i, r = rand() % Limites[maxNivel-1] + 1;
for (i = 1; i < maxNivel; i++)
if (r < Limites[i])
return i-1;
return i-1;
}

É importante considerar ainda que o modo mais simples de implementar cada nó é fazer cada
nó ter maxN ivel ponteiros, mas isso é um desperdı́cio. O ideal é utilizar somente a quantidade
de ponteiros que o nı́vel do nó exige. Para realizar isso, o membro Lig de cada nó não é um
ponteiro para o próximo nó, mas para uma matriz de ponteiro(s) ao(s) próximo(s) nó(s). O
tamanho dessa matriz é determinada pelo nı́vel do nó. Assim, a lista na figura 9b é realmente
uma lista cujos quatro primeiros nós são mostrados na figura 9c. O procedimento de inserção
para este caso é apresentado a seguir:

void InsereListaDeSalto (NoPtr Raiz[], int Limites[], int maxNivel, char Chave)
{
NoPtr Aux[maxNivel], Ant[maxNivel], P;
int nvl, i;
Aux[maxNivel-1] = Raiz[maxNivel-1];
Ant[maxNivel-1] = 0;
for (nvl = maxNivel-1; nvl >= 0; nvl--) {
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 21

while ((Aux[nvl] != NULL) && (Aux[nvl]->Info < Chave)) {

Ant[nvl] = Aux[nvl];
Aux[nvl] = *(Aux[nvl]->Lig + nvl);
}
if (nvl > 0)
if (Ant[nvl] == NULL) {
Aux[nvl-1] = Raiz[nvl-1];
Ant[nvl-1] = NULL;
} else {
Aux[nvl-1] = *(Ant[nvl]->Lig + nvl-1);
Ant[nvl-1] = Ant[nvl];
}
}
nvl = EscolherNivel (Limites, maxNivel);
P = new No;
P->Lig = new NoPtr[nvl+1];
P->Info = Chave;
for (i = 0; i <= nvl; i++) {
*(P->Lig + i) = Aux[i];
if (Ant[i] == NULL)
Raiz[i] = P;
else
*(Ant[i]->Lig + i) = P;
}
}

Finalmente, é preciso destacar a utilização de um ponteiro duplo para o próximo elemento

da lista, visto se tratar de um vetor de ponteiros, conforme declaração a seguir:

struct No {
char Info;
No ** Lig;
};

9.3 Listas cruzadas

Em muitas aplicações, a escolha de uma matriz parece ser mais natural, mas considerações de
espaço podem impedir essa escolha. Isso é particularmente verdadeiro se somente uma pequena
fração da tabela é usada. Uma tabela desse tipo é chamada de matriz esparsa, uma vez que a
tabela é povoada esparsamente por dados e a maioria das células fica vazia.
Por exemplo, seja a matriz abaixo, a qual contém 5 linhas e 6 colunas. Apenas 5 de seus
elementos são diferentes de zero (não nulos).
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 22

 
0 0 0 0 6 0
 0 3 0 0 0 0 
 
 
 0 0 0 0 4 0 
 
 5 0 1 0 0 0 
 

0 0 0 0 0 0

É necessário encontrar outra representação que evite o armazenamento de tantas posições nu-
las. Uma das soluções para este tipo de situação é a utilização de listas cruzadas (PIMENTEL;
OLIVEIRA, 2006).
Para não representar os valores nulos, será necessário criar listas de linhas e listas de
colunas tais que o elemento Mi,j diferente de zero pertence à lista dos elementos da linha i e
à lista dos elementos da coluna j. Então, se a matriz possui nl linhas e nc colunas, tem-se nl
listas de linhas e nc listas de colunas. Graficamente esta estrutura pode ser representada pela
figura 10.

Figura 10: Estrutura das listas cruzadas

A figura 11 ilustra esta estrutura para o exemplo da matriz anterior.

O trecho de código a seguir, apresenta a declaração para listas cruzadas:

#define NL 10;
#define NC 10;

struct No {
int Lin;
int Col;
int Valor;
No * PL;
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 23

Figura 11: Exemplos de listas cruzadas

No * PC;
};
struct ListasCruzadas {
No * Linha[NL];
No * Coluna[NC];
};

Além de armazenar matrizes esparsas, as aplicações normalmente exigem a realização de

operações sobre essas matrizes, como, por exemplo, multiplicar uma dada linha ou coluna por
uma constante, somar uma constante a todos os elementos de uma linha ou coluna, somar
duas matrizes esparsas de igual dimensão, etc. Entretanto, a realização destas operações pode
resultar em novos elementos nulos, além daqueles que podem deixar de sê-lo. Por conseguinte,
o uso deste tipo de estrutura deve ser bem avaliado, pois pode resultar em perda significativa
de desempenho da aplicação.
Em adição, dependendo da quantidade de elementos não nulos, o ganho de memória pode
não ser significativo. Por exemplo, supondo o caso de uma matriz esparsa que armazena números
inteiros e, supondo ainda que um ponteiro de memória ocupe o mesmo espaço de um inteiro.
Nesta situação, o espaço ocupado por uma matriz esparsa de nl linhas e nc colunas e n valores
não-nulos corresponde a:

• 5 × n espaços para armazenar os membros de cada nó (um para cada campo do registro:
Lin, Col, Valor, PL e PC);

• nl espaços para os ponteiros do vetor Linha;

• nc espaços para os ponteiros do vetor Coluna.

Portanto, o espaço total ocupado por essa estrutura seria 5n+nl +nc. Como a representação
matricial ocuparia um total de nl×nc, conclui-se que, em termos de espaço ocupado, há vantagem
em utilizar-se a representação de listas cruzadas quando:
 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 24

n < [(nl − 1) × (nc − 1) − 1]/5

Como (nl −1)×(nc−1) é aproximadamente o tamanho da matriz, pode-se dizer, de uma ma-
neira geral que, há ganho em termos de espaço, quando um número inferior a 1/5 dos elementos
da matriz não forem nulos.
A função seguinte apresenta um código para somar uma constante (K) aos elementos da
coluna J de uma determinada matriz, representada pela variável LC:

void SomaConstante (ListasCruzadas& LC, int K, int J)

{
No * P = [Link][J];
int Aux;
for (int i=0; i < NL; i++) {
if (P == NULL)
InsereListasCruzadas (LC, i, J, K);
else {
if (P->Lin != i)
InsereListasCruzadas (LC, i, J, K);
else {
P->Valor += K;
if (P->Valor == 0) {
P = P->PC;
RetiraListasCruzadas (LC, i, J, Aux);
} else
P = P->PC;
}
}
}
}

10 Exercı́cios
1. Implemente as primitivas de consulta e alteração de um nó em uma lista estática sequencial.

2. Desenvolver uma função para retornar a quantidade de elementos de uma lista estática
encadeada.

3. Desenvolva uma função para percorrer uma lista estática encadeada apresentando os seus
elementos.

4. Faça uma função para retornar o último elemento de uma lista estática encadeada.

5. Refaça os exercı́cios anteriores considerando uma lista dinâmica.

6. Escreva um procedimento para concatenar duas listas dinâmicas.

 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 25

(a) simplesmente encadeadas;

(b) duplamente encadeadas.

7. Polinômios podem ser representados por meio de listas, cujos nós são registros com 3
campos: coeficiente, expoente e referência ao seguinte. Usando esta representação, descreva
procedimentos para

(a) somar polinômios;

(b) multiplicar polinômios.

8. Considere um polinômio de coeficientes inteiros da forma P (x) = a0 xn + a1 xn−1 + · · · + an ,

representado na forma de lista simplesmente encadeada. Pede-se desenvolver uma função
que, recebendo o ponteiro de inı́cio da lista e o valor de x, retorna o valor de P (x).

9. Escreva uma função para inverter as referências de uma lista simplesmente encadeada.

10. Escreva uma função para verificar se duas listas encadeadas possuem o mesmo conteúdo.

11. Faça uma função para anexar uma lista simplesmente encadaeada ao final de outra lista
do mesmo tipo.

12. Seja L uma lista simplesmente encadeada, composta dos números l1 , l2 , · · · , ln , respectiva-
mente, segundo a ordem de armazenamento. Escreva uma função que, percorrendo L uma
única vez, constrói uma outra lista L0 , formada dos elementos seguintes:

(a) l2 , l3 , · · · , ln , l1 .
(b) ln , ln−1 , · · · , l1 .
(c) l1 + ln , l2 + ln−1 , · · · , ln/2 + ln/2+1 , onde n é par.

13. As frações de Farey de nı́vel um (1) são definidas como a sequência ( 10 , 11 ). Essa sequência
é estendida no nı́vel dois para formar a sequência ( 10 , 12 , 11 ), a sequência ( 01 , 31 , 12 , 23 , 11 ) no
nı́vel três e a sequência ( 01 , 41 , 13 , 21 , 23 , 43 , 11 ) no nı́vel quatro, de modo que a cada nı́vel n
(a+b) a b
uma nova fração (c+d) é inserida entre duas frações vizinhas c e d somente se c + d ≤ n.
Pede-se:

(a) A declaração do nó para uma lista que represente as frações de Farey.
(b) Uma função que recebe um ponteiro para a lista descrita e um número n, e crie a
lista estendendo-a constantemente até se alcançar a lista de frações no nı́vel n.

14. Implemente as primitiva InsereEsquerda, InsereDireita, RetiraEsquerda, RetiraDireita

para uma lista duplamente encadeada com descritor.

15. Seja a função Esvazie() tal que, recebendo uma lista como entrada, esvazie a lista descar-
tando todos os seus elementos. Escreva a função Esvazie() para as seguintes estruturas:

(a) lista estática sequencial;

 Algoritmos e Estruturas de Dados - Notas de Aula - Capı́tulo 02 - 26

(b) lista encadeada estática;

(c) lista encadeada dinâmica;
(d) lista duplamente encadeada;
(e) lista circular.

16. Reescreva os algoritmos do exercı́cio anterior considerando que as estruturas possuem um

elemento sentinela.

17. Faça uma função para apresentar a representação literal de uma lista generalizada.

18. Dê um exemplo de lista generalizada a qual contém, no total, pelo menos 25 átomos e 10
cabeças em, pelo menos, quatro nı́veis. Escreva sua lista em notação de parênteses (LISP).

19. Desenvolva uma função para apresentar todos os elementos de uma lista de salto.

20. Implemente a primitiva de remoção de um nó em uma lista de salto.

21. Implemente as primitivas InsereListasCruzadas e RemoveListasCruzadas

22. Considerando a estrutura listas cruzadas, implemente funções para:

(a) ler e imprimir uma matriz esparsa;

(b) somar os elementos de uma linha i a uma constante K;
(c) somar duas matrizes esparsas;
(d) verificar se uma matriz esparsa é uma matriz identidade.

Referências
DROZDEK, A. Estrutura de Dados e Algoritmos em C++. São Paulo: Pioneira Thomson
Learning, 2002.

PIMENTEL, M. da G. C.; OLIVEIRA, M. C. F. de. Algoritmos e estrutura de dados 1.

Http://[Link]/ sce182/. 2006.

SZWARCFITER, J. L.; MARKENZON, L. Estruturas de Dados e Seus Algoritmos. Rio de

Janeiro: LTC Editora, 1994.

VELOSO, P. et al. Estrutura de Dados. 2a. ed. Rio de Janeiro: Editora Campus, 1986.