Listas Lineares em Estrutura de Dados

Prévia do material em texto

Universidade Federal de Itajubá – UNIFEI
Campus Itabira
Capítulo 4
Listas Lineares
Sandro Carvalho Izidoro
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 realidade, são inúmeros os tipos de dados que podem ser descritos por listas 
lineares [1]. 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 
seqüê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 freqüentes 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 são consideradas como primitivas. Outras operações, também importantes, 
podem ser mencionadas: 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 [1]. 
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 seqüencial 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. 
Estrutura de Dados – Capítulo 4 – 2
2 Lista Estática Sequencial 
 Uma lista estática seqüencial, também conhecida como lista por contigüidade, é 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 [2]. Desta forma, 
o sucessor de um elemento ocupa posição física subseqüente. 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 seqüencial 
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 seqüencial: 
#define TAM 10; 
struct No { 
  char Chave; 
  int Valor; 
}; 
struct ListaSequencial { 
  No Dados[TAM]; 
  int Fim; 
}; 
Estrutura de Dados – Capítulo 4 – 3
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 ultimo elemento válido na lista dentro do vetor. 
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 seqüê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 (L.Fim == TAM ­ 1) 
      return false; 
   else { 
      int i = 0, p; 
      while ((i <= L.Fim) && (L.Dados[i].Chave < Novo.Chave)) 
         i++; 
      p = i; 
      i = L.Fim; 
      while (i > p­1) { 
         L.Dados[i+1] = L.Dados[i]; 
         i­­; 
      } 
      L.Dados[p] = Novo; 
      L.Fim++; 
      return true; 
   } 
}
E 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 subseqüente (K + 2) e 
Estrutura de Dados – Capítulo 4 – 4
assim sucessivamente. A função seguinte implementa o procedimento descrito: 
bool RetiraListaSeq (ListaSequencial& L, No& N){ 
   int i = 0; 
   while ((i <= L.Fim) && (L.Dados[i].Chave != N.Chave)) 
      i++; 
   if (i > L.Fim) 
      return false; 
   N = L.Dados[i]; 
   while (i < L.Fim) { 
      L.Dados[i] = L.Dados[i+1]; 
      i++; 
   } 
   L.Fim­­; 
   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 continuidade 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 contigüidade 
comprometem 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 
encadeamento 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: 
Estrutura de Dados – Capítulo 4 – 5
#define TAM 10; 
struct No { 
   char Info; 
   int Lig; 
}; 
struct ListaEstaticaEncadeada { 
   int Com; 
   int Dispo; 
   No Dados[TAM]; 
}; 
Figura 2: Exemplo de uma lista estática encadeada 
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 processosde 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 
Estrutura de Dados – Capítulo 4 – 6
Figura 4: Exemplo de remoção em uma lista encadeada 
3.1 Primitiva de inserção
Como foi dito, o processo de inserçao 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 unico nó e a lista começará 
neste nó. 
• 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 (L.Dispo == ­1) 
    return false; 
  else { 
    if (L.Com == ­1) { 
       L.Com = L.Dispo; 
       L.Dispo = L.Dados[L.Dispo].Lig; 
       L.Dados[L.Com].Info = Novo; 
       L.Dados[L.Com].Lig = ­1; 
    } else { 
       int Ant = ­1; 
       int Aux = L.Com; 
       while ((Aux != ­1) && (L.Dados[Aux].Info < Novo)) { 
         Ant = Aux; 
         Aux = L.Dados[Aux].Lig; 
       } 
       Aux = L.Dispo; 
       L.Dispo = L.Dados[L.Dispo].Lig; 
Estrutura de Dados – Capítulo 4 – 7
       L.Dados[Aux].Info = Novo; 
       if (Ant == ­1) { 
         L.Dados[Aux].Lig = L.Com; 
         L.Com = Aux; 
         } else { 
            L.Dados[Aux].Lig = L.Dados[Ant].Lig; 
            L.Dados[Ant].Lig = Aux; 
         } 
      } 
      return true; 
   } 
} 
3.2 Inicialização da lista estática encadeada 
Na lista estática sequencial a unica 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ível, 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++) 
      L.Dados[i].Lig = i+1; 
   L.Dados[TAM­1].Lig = ­1; 
   L.Dispo = 0; 
   L.Com = ­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; 
Estrutura de Dados – Capítulo 4 – 8
É 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 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 = L.Com; 
   while ((Aux != ­1) && (L.Dados[Aux].Info != Novo)) { 
     Ant = Aux; 
     Aux = L.Dados[Aux].Lig; 
   } 
   if (Aux == ­1) 
     return false; 
   if (Aux == L.Com) 
     L.Com = L.Dados[L.Com].Lig; 
   else 
     L.Dados[Ant].Lig = L.Dados[Aux].Lig; 
   L.Dados[Aux].Lig = L.Dispo; 
   L.Dispo = Aux; 
   return true; 
} 
4 Lista Dinâmica
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 Nó. Este tipo de estrutura 
deve ser auto-referente, isto é, deve conter um membro ponteiro que armazena o 
endereço de outra estrutura do mesmo tipo. 
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: 
• o ponteiro para o início da lista; e 
• o dado a ser inserido. 
Estrutura de Dados – Capítulo 4 – 9
void InsereLista (NoPtr& L, char Novo) { 
  if (L == NULL) {  // INSERÇÃO DO PRIMEIRO NÓ
      L = new No; 
      L­>Info = Novo; 
      L­>Lig = NULL; 
  } else {                // AJUSTA PONTEIROS ANT E AUX
      NoPtr Ant = NULL; 
      NoPtr Aux = L; 
      while((Aux != NULL)&&(Aux­>Info < Novo)) {//ENCONTRA POSIÇÃO
           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 Novo) { 
  NoPtr Ant = NULL; 
  NoPtr Aux = L; 
  while ((Aux != NULL) && (Aux­>Info != Novo)) { 
          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; 
} 
Estrutura de Dados – Capítulo 4 – 10
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 util. 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 [1]. 
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 duplamente 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; 
}; 
typedef No * NoPtr; 
voidInsereLista (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; 
      
Estrutura de Dados – Capítulo 4 – 11
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 inseçã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 ultimo 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: 
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 ultimo 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 [3]. 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 de Dados – Capítulo 4 – 12
estrutura, 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; 
} 
A seguir, são apresentados outras funções para manipulação de listas encadeadas 
com descritor. 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 { 
Estrutura de Dados – Capítulo 4 – 13
        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 { 
       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. 
Estrutura de Dados – Capítulo 4 – 14
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 [2]. 
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) { 
   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; 
} 
Estrutura de Dados – Capítulo 4 – 15
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 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 consequencia, 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 [4]. 
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. 
9 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. 
Estrutura de Dados – Capítulo 4 – 16
10 Referências
[1] Jayme Luiz Szwarcfiter and Lilian Markenzon. Estruturas de Dados e Seus Algoritmos. 
LTC Editora, Rio de Janeiro, 1994. 
[2] Maria da Graça Campos Pimentel and Maria Cristina Ferreira de Oliveira. Algoritmos e 
estrutura de dados 1. http://www.icmc.usp.br/ sce182/, 2006. 
[3] Paulo Veloso, Clesio dos Santos, Paulo Azeredo, and Antonio Furtado. Estrutura de 
Dados. Editora Campus, Rio de Janeiro, 2a edition, 1986. 
[4] Adam Drozdek. Estrutura de Dados e Algoritmos em C++. Pioneira Thomson Learning, 
São Paulo, 2002. 
Observação
Material elaborado a partir das notas de aula do professor Edmilson Marmo Moreira 
(UNIFEI) 
	1 Considerações Iniciais
	2 Lista Estática Sequencial
	2.1 Inserção de um nó em uma lista sequencial
	2.2 Remoção de um nó da lista sequencial
	3 Lista Estática Encadeada
	3.1 Primitiva de inserção
	3.2 Inicialização da lista estática encadeada
	3.3 Primitiva de remoção
	4 Lista Dinâmica
	4.1 Primitiva de inserção em listas dinâmicas
	4.2 Primitiva de remoção em listas dinâmicas
	5 Listas Duplamente Encadeadas
	6 Lista com Descritores
	7 Listas com Sentinelas
	8 Listas Circulares
	9 Exercícios
	10 Referências