Aluno: Cristiano Macedo Melo

Matrícula: 182813

Relatório — TAD Lista Linear com Ocupação Circular do Arranjo

1. Introdução

O objetivo deste trabalho é implementar um TAD Lista Linear com Ocupação

Circular do Arranjo, utilizando a linguagem Python.

A estrutura foi desenvolvida com um vetor de tamanho fixo (9), no qual os

elementos são armazenados de forma lógica em sequência. Porém, por utilizar
ocupação circular, a ordem física dos elementos no vetor pode ficar dividida
entre o final e o início do arranjo.

Essa estratégia permite reaproveitar espaços livres no início do vetor após

remoções, evitando desperdício de posições e melhorando o uso da estrutura.

Foram implementadas as seguintes operações:

 Inserir elemento;
 Remover elemento;

 Acessar elemento por posição;

 Buscar informação;

 Exibir a lista em ordem lógica;

 Exibir a estrutura interna do arranjo.

2. Fundamentação Teórica

Uma lista linear é uma sequência de nodos organizados de forma ordenada.

Segundo o conteúdo apresentado em aula, uma lista linear pode ser vista como
uma coleção de zero ou mais nodos do mesmo tipo, em que o primeiro
elemento não possui antecessor, o último não possui sucessor, e os elementos
intermediários possuem um antecessor e um sucessor.

As listas lineares podem ser aplicadas em vários contextos, como cadastros de

alunos, funcionários, clientes, produtos, controle de estoque, carrinho de
compras, agenda e histórico de valores. Os slides também destacam
operações comuns em listas, como inserir, excluir, acessar, alterar, localizar e
determinar a cardinalidade da lista.
Na implementação por contiguidade física, a lista é armazenada em um
arranjo, ou seja, um vetor. Cada posição do vetor representa um nodo da lista.
O exemplo fornecido pelo professor utiliza uma classe Lista com os campos
max, vetor, ini e fim, sendo ini e fim usados para indicar o início e o final da lista
dentro do arranjo.
3. Lista Linear com Ocupação Circular

Na lista linear comum com arranjo, pode acontecer de o final da lista chegar à
última posição do vetor, mesmo ainda existindo espaço livre no início. Isso
ocorre principalmente após remoções dos primeiros elementos.

Os slides de listas circulares explicam que, quando uma lista linear é

implementada sobre um arranjo, sucessivas inclusões e remoções podem fazer
com que o final da lista esteja na última posição do arranjo, restando espaço
livre no início. Uma nova inclusão no final não seria possível sem
deslocamentos, por isso é usada a ocupação circular do arranjo.
Na ocupação circular, o vetor físico continua sendo um arranjo comum, mas a
lógica de acesso muda. Quando o índice chega ao final do vetor, ele retorna
para o índice 0.

Na implementação desenvolvida, foram usados os seguintes atributos:

A conversão de posição lógica para posição física é feita com a fórmula:

O uso do operador % permite que a posição “dê a volta” para o início do vetor
quando ultrapassa a última posição física.
4. Implementação

A implementação foi feita em dois arquivos:

[Link]
[Link]

O arquivo [Link] contém a classe responsável pela estrutura do TAD.

O arquivo [Link] contém os testes realizados sobre a lista.

Essa organização segue o estilo usado no material do professor, em que a

classe da lista fica em um arquivo separado e o programa principal importa
essa classe para realizar os testes.

5. Operações Implementadas

5.1 Inicialização

A lista é inicializada com um vetor de tamanho fixo preenchido com None.

Inicialmente, ini e fim recebem -1, indicando que a lista está vazia. A variável
qtd começa com valor 0.

5.2 Verificar se a lista está vazia

A função Vazia() verifica se a quantidade de elementos é igual a zero.

5.3 Verificar se a lista está cheia

A função Cheia() verifica se a quantidade de elementos chegou ao tamanho

máximo do vetor.

Essa verificação é importante porque, em uma lista circular, não basta analisar
se ini está no começo e fim está no final do vetor. A lista pode estar quebrada
fisicamente e ainda assim estar cheia.

5.4 Tamanho da lista

A função Tamanho() retorna a quantidade atual de elementos armazenados.

5.5 Inserção

A função Inserir(posicao, dado) adiciona um elemento em uma posição lógica

da lista.
Primeiro, a função verifica se a lista está cheia ou se a posição é inválida. A
posição é considerada válida quando está entre 1 e qtd + 1.

Se a lista estiver vazia, o elemento é inserido na posição 0, e os indicadores ini

e fim passam a apontar para essa posição.

Se a inserção for no início, o índice ini é decrementado de forma circular. Se for

no final, o índice fim é incrementado de forma circular.

Quando a inserção ocorre no meio, é necessário deslocar elementos. A

implementação escolhe o lado com menor custo:

 Se a posição estiver mais próxima do início, desloca-se a parte inicial da

lista.

 Se a posição estiver mais próxima do final, desloca-se a parte final da

lista.

Esse deslocamento mantém a ordem lógica dos elementos mesmo quando a

lista está fisicamente dividida entre o fim e o início do vetor.
5.6 Remoção

A função Remover(posicao) remove o elemento de uma posição lógica da lista.

Primeiro, a função verifica se a lista está vazia ou se a posição é inválida.

Se a lista possuir apenas um elemento, esse elemento é removido e os

indicadores voltam para -1.
Se a remoção for no início, o elemento da posição ini é removido e ini avança
circularmente. Se for no final, o elemento da posição fim é removido e fim recua
circularmente.

Na remoção no meio, a função também escolhe o lado de menor custo para

deslocar os elementos e manter a ordem lógica da lista.

5.7 Acesso por posição

A função Acessar(posicao) retorna o valor armazenado em uma posição lógica

da lista.

Como a lista é circular, a posição lógica precisa ser convertida para índice
físico:

indice = ([Link] + posicao - 1) % [Link]

Depois disso, o valor armazenado naquela posição física é retornado.

5.8 Buscar informação

A função Buscar(dado) percorre a lista em ordem lógica e compara cada

elemento com o valor procurado.

Se encontrar o dado, retorna sua posição lógica. Caso contrário, retorna -1.

5.9 Exibição da lista

A função Exibir() mostra os elementos na ordem lógica da lista, começando em

ini e avançando circularmente pelo vetor.

Essa função é importante porque a ordem física do vetor pode não ser igual à
ordem lógica da lista.
5.10 Exibição da estrutura interna

A função ExibirEstrutura() mostra:

 O vetor físico completo;

 O valor de ini;

 O valor de fim;

 A quantidade de elementos;

 A ordem lógica da lista.

Essa função foi usada para demonstrar o funcionamento da ocupação circular

e verificar se os dados continuaram corretos após inserções e remoções.
6. Custo das Operações

Operação Custo

Verificar se a lista está vazia O(1)

Verificar se a lista está cheia O(1)

Consultar tamanho O(1)

Acessar por posição O(1)

Buscar informação O(n)

Exibir lista O(n)

Exibir estrutura O(n)

Inserir no início O(1)

Inserir no final O(1)

Inserir no meio O(n)

Remover do início O(1)

Remover do final O(1)

Remover do meio O(n)

O acesso por posição possui custo constante porque basta calcular o índice
físico usando módulo.

A busca possui custo linear porque, no pior caso, pode ser necessário percorrer
todos os elementos da lista.

A inserção e a remoção no meio podem ter custo linear porque exigem

deslocamento de elementos.
7. Vantagens

A lista linear com ocupação circular do arranjo apresenta as seguintes

vantagens:

 Aproveita melhor o espaço disponível no vetor;

 Permite reutilizar posições livres no início do arranjo;

 Evita deslocamentos desnecessários em algumas inserções no final;

 Mantém acesso direto por posição lógica;

 Não necessita de alocação dinâmica de memória;

 É eficiente para inserções e remoções nas extremidades.

8. Desvantagens

As principais desvantagens são:

 O tamanho máximo da lista precisa ser definido previamente;

 A implementação é mais complexa do que uma lista sequencial comum;

 Inserções e remoções no meio ainda podem exigir deslocamentos;

 É necessário cuidado com os cálculos circulares usando módulo;

 A ordem física dos elementos pode ser diferente da ordem lógica,

dificultando a visualização.
9. Aplicações

Essa estrutura pode ser utilizada em situações em que há um número máximo

conhecido de elementos e é importante reaproveitar espaços livres do arranjo.

Algumas aplicações possíveis são:

 Filas circulares;
 Buffers circulares;

 Sistemas de atendimento;

 Controle de estoque;

 Agenda;

 Histórico de valores;

 Armazenamento temporário de dados.

10. Cenário de Teste

O cenário de teste foi desenvolvido no arquivo [Link].

Foi criada uma lista circular com tamanho máximo igual a 9:

10.1 Povoamento inicial

Primeiramente, foram inseridos oito elementos na lista:

Essa etapa teve como objetivo ocupar o arranjo até a parte final, deixando a
lista em sequência física.

Estado lógico esperado:

10.2 Remoção dos primeiros elementos

Depois, foram removidos os três primeiros elementos da lista.

Com isso, os valores 10, 20 e 30 foram removidos, e o início lógico da lista foi
deslocado para frente.

Estado lógico esperado:

Contendo posições livres no início do vetor.

10.3 Teste de circularidade

Em seguida, foram inseridos três novos elementos no final lógico da lista:

Como o fim físico do vetor já estava próximo do final do arranjo, essas

inserções forçaram o indicador fim a retornar para o início do vetor.
Estado lógico esperado:

Nesse ponto, a lista está fisicamente “quebrada”: parte dos dados está no final
do vetor e parte está no início.

10.4 Teste crítico: inserção no meio

Com a lista quebrada, foi realizada uma inserção na posição lógica 4:

Antes da inserção, a ordem lógica era:

Após inserir o valor 150 na posição lógica 4, a ordem esperada é:

Esse teste demonstra que a inserção no meio da lista quebrada não corrompeu
a ordem dos dados.

10.5 Teste de acesso

Foi realizado o acesso à posição lógica 4.

Como o valor 150 foi inserido nessa posição, o retorno esperado é:

10.6 Teste de busca

Também foi realizada a busca pelo valor 150.

Como esse valor está presente na lista, o retorno esperado é:

11. Conclusão

A implementação do TAD Lista Linear com Ocupação Circular do Arranjo

permitiu observar como uma lista pode ser armazenada em um vetor de forma
mais eficiente.

A principal vantagem dessa estrutura é a possibilidade de reutilizar posições

livres no início do arranjo após remoções. Dessa forma, quando o final físico do
vetor é atingido, a lista pode continuar ocupando posições a partir do início do
vetor.

Durante a implementação, foi necessário utilizar os indicadores ini, fim e qtd

para controlar corretamente o início lógico, o fim lógico e a quantidade de
elementos da lista. Também foi necessário usar o operador módulo para
converter posições lógicas em posições físicas.
O teste crítico mostrou que, mesmo com a lista fisicamente quebrada, foi
possível inserir um elemento no meio sem corromper a ordem lógica dos
dados. Portanto, o TAD implementado cumpre as operações solicitadas e
demonstra corretamente o funcionamento da ocupação circular do arranjo.