Listas Encadeadas em Jogos Digitais

Prévia do material em texto

03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=uczP… 1/43
introdução
Introdução
PROGRAMAÇÃO E INTEGRAÇÃO DE JOGOSPROGRAMAÇÃO E INTEGRAÇÃO DE JOGOS
LISTAS ENCADEADASLISTAS ENCADEADAS
Autor: Me. Victor de Assis Rodrigues
Revisor : Emerson dos Santos Paduan
IN IC IAR
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=uczP… 2/43
Nesta unidade discorreremos sobre a estrutura de dados Listas, mais especi�camente sobre
Listas Encadeadas. Esse tipos de estrutura é mais versátil por permitir a inserção e remoção de
elementos em qualquer posição dentro da coleção. Além disso, existem muitas variações que
serão comentadas como, por exemplo, as listas de encadeamento simples e duplo e listas
circulares.
Iremos também explorar contextos de utilização dessas estruturas em jogos digitais. O objetivo
aqui é tentar separar a lógica de implementação dos mecanismos com a lógica de design dos
jogos, pois cada um possui formas de implementação e objetivos diferentes.
Por �m, vamos explorar mais um pouco os mecanismos clássicos de iteração, para que você
possa ter mais conhecimento e habilidade na implementação dos seus jogos digitais.
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=uczP… 3/43
Sabemos que um vetor possui diversas vantagens e é aplicável em uma série de problemas
relacionados à computação. Uma dessas vantagens, por exemplo, é a facilidade de acesso a um
determinado valor, uma vez que é possível utilizar seu índice para acesso direto ao elemento e,
por conta da alocação estática, a quantidade de memória necessária já é de�nida em tempo de
compilação (LAUREANO, 2008).
Entretanto, seu uso também apresenta algumas desvantagens. Se quisermos inserir um novo
elemento na primeira posição do vetor, por exemplo, será necessário deslocar todos os outros
elementos que já estavam no vetor para uma posição à frente, como ilustrado na Figura 3.1.
Na Figura 3.1, temos um vetor de cinco posições com quatro valores, localizados nas primeiras
posições do vetor. Para adicionar um novo elemento no início desse vetor precisaríamos deslocar
todos os valores para uma posição posterior e, apenas nesse momento, inserir o novo valor no
vetor.
Listas EncadeadasListas Encadeadas
Figura 3.1 - Inserção de um novo elemento em um vetor
Fonte: Elaborado pelo autor, 2019
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=uczP… 4/43
Assim, precisamos de um mecanismo computacionalmente e�caz para adicionar e remover itens
de uma sequência, em qualquer posição. Conseguiremos suprir essa necessidade através da
implementação de uma Lista Encadeada e suas variações (CELES, CERQUEIRA e RANGEL, 2016).
Representação e Manipulação
Para representarmos uma estrutura que seja �exível ao manuseio das informações devemos
aplicar algo que não seja �xo. A ideia principal da lista encadeada é que cada elemento possua
uma referência para o próximo elemento da lista, e que, caso haja alguma alteração, basta
apenas atualizarmos essa referência (GOODRICH e TAMASSIA, 2013).
Caso precisarmos inserir um novo número entre dois elementos da lista, basta atualizarmos as
referências do elemento anterior e também do novo elemento. A Figura 3.3 ilustra esse
mecanismo.
Na Figura 3.3 (a) queremos inserir um novo número na lista que �cará entre os números 7 e 45.
Como estamos trabalhando com uma lista encadeada, é possível atualizar a referência do
Figura 3.2 - Representação de uma lista encadeada
Fonte: Elaborado pelo autor (2019)
Figura 3.3 - Inserindo um novo elemento na lista encadeada
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=uczP… 5/43
elemento 7 para o novo elemento 16. Depois, atualizamos a referência do elemento 16 para o 45.
Dessa forma conseguimos   manter a integridade da lista sem precisar alterar a posição dos
demais elementos.
Nas próximas seções iremos representar essa funcionalidade na linguagem de programação
Javascript.
Representação
Uma lista é um conjunto ou agrupamento de itens. Assim, iremos precisar de duas classes: o
item, que representará cada elemento individualmente: e a lista, que �cará responsável pelo
gerenciamento de todos os itens. Os itens, por sua vez, são divididos em duas partes: a primeira
parte é destinada aos valores que deverão ser armazenados. A outra parte é a referência para o
próximo elemento da lista. As duas partes estão ilustradas na Figura 3.4.
Vamos de�nir a estrutura item, que será uma classe escrita na em linguagem Javascript. Iremos
declarar dois atributos: valor e próximo. Para facilitar a instanciação, iremos declarar um
construtor no qual receberá como parâmetro um valor.
Com a classe item representada, começaremos a de�nir a Estrutura de Dados Lista. Entretanto,
uma lista se diferencia das outras estruturas de dados devido sua versatilidade, a�nal, podemos
inserir e remover itens de qualquer posição da coleção. Assim, nesse momento, vamos criar
apenas os atributos principais e, nas próximas seções, iremos estudar cada método
separadamente:
Nas próximas seções vamos analisar as operações que deverão ser implementadas na lista.
Como foi dito, a lista é uma estrutura de dados mais adaptável que a pilha ou �la, uma vez que
permite inserir e remover um elemento independente da posição que está na coleção. Além
disso, por possuir essa �exibilidade, é possível representar uma pilha ou �la usando uma lista,
Figura 3.4 - Representação do item de uma lista encadeada
Fonte: Elaborado pelo autor, 2019
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=uczP… 6/43
bastando apenas respeitar os  princípios da estratégia FILO ( First In, Last Out ) ou FIFO ( First In,
First Out ).
Operações em Listas
Como observamos na anteriormente, uma Lista é representada por dois nós: início e �m.
Entretanto, precisamos criar uma funcionalidade que permita inserir e retirar elementos no meio
da coleção, em qualquer posição. Isso abre uma grande quantidade de possibilidades: podemos
inserir um item quando a lista está vazia, ou inserir um item no começo, meio ou �nal da lista.
Para retirar um item, também temos várias situações. Assim, vamos criar funções que nos
ajudem a resolver cada caso dessa estrutura.
Em termos gerais, temos os seguintes métodos:
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=uczP… 7/43
Tabela 3.1 - Métodos básicos de listas
Fonte: Elaborado pelo autor (2019)
Métodos Descrição
Inserir(L, posicao, item,
sucesso)
O método Inserir() é responsável por inserir o elemento
na lista. O parâmetro L é a lista que irá ser utilizada,
posicao é a posição que será inserido o elemento, item é
o elemento a ser inserido e a variável sucesso terá a
informação se o processo deu certo ou não, sendo esse
último um parâmetro opcional.
Remover (L, posicao,
sucesso)
Esse método retira o elemento da lista. O elemento a ser
retirado pode estar em qualquer posição na coleção. O
parâmetro L é a lista que irá ser utilizada, o parâmetro
posicao é a posição que está o item a ser removido e a
variável sucesso terá a informação se o processo deu
certo ou não, sendo esse último um parâmetro opcional.
PegarItem(L, posicao)
Método que retorna qual o elemento que está na posicao
da lista. Caso a lista estiver vazia, um erro será lançado.
O parâmetro L é a lista que irá ser utilizada e o
parâmetro posicao é a posição do item que deseja-se serrecuperado.
ContarElementos(L)
Esse método adicional conta a quantidade de elementos
inseridos na lista. É necessário informar qual lista que
será utilizada no parâmetro L .
EstaVazia(L)
Método adicional que veri�ca se existe algum elemento
na lista. O parâmetro L é a lista a ser utilizada.
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=uczP… 8/43
saiba mais
Saiba mais
Devido à importância da disciplina de estrutura de dados,
estudantes e professores têm interesse em desenvolver
soluções para facilitar a aprendizagem desses conceitos.
No link é possível ter acesso a um artigo descrevendo um
jogo para facilitar o entendimento do conceito de
algoritmos de ordenação em estruturas de dados.
Fonte: Elaborado pelo autor.
ACESSAR
Nas próxima seção vamos explorar detalhes dessas operações e descobrir como aplicá-las em
uma linguagem de programação. Vamos conferir!
Inserção de um Item no Começo da Lista
A inserção no começo da lista possui duas situações. A primeira situação é quando a lista está
vazia, ou seja, não possui nenhum elemento. Nesse caso, precisamos atualizar tanto a referência
das propriedades inicio como �m da lista, como ilustra a Figura 3.5.
Figura 3.5 - (a) Lista vazia e em (b) a representação de ligação dos atributos com o item
Fonte: Elaborado pelo autor (2019)
A segunda situação ocorre quando já temos elementos na lista. Nessa situação precisamos
mudar a referência do atributo inicio . Além disso, a referência proximo do novo elemento deve
conter o primeiro elemento da coleção.
https://www.br-ie.org/pub/index.php/sbie/article/view/1772/1533
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=uczP… 9/43
Segue a implementação:
No código acima estamos declarando uma nova função com a instrução function . Podemos
descobrir se a lista está vazia veri�cando se o atributo totalElementos é igual a 0 (zero). Quando
a lista está vazia, alteramos os valores de referência dos atributos início e �m, setando item
adicionado. Caso a lista já tiver elementos, alteramos apenas o atributo próximo do objeto item,
setando o elemento atual que está no início.
Vale lembrar que é uma boa prática colocar método como privado da classe, ou seja, que só pode
ser acessado em rotinas pertencentes a classe que está sendo implementada. Isso porque
estamos tratando apenas da situação de inserção no início da coleção e, para a utilização externa,
convém disponibilizar apenas um método público que possamos contemplar todas as situações,
onde essas rotinas especí�cas serão chamadas dentro deste.
Inserção no Fim da Lista
Como na lista o usuário passa a posição que gostaria de inserir o elemento, podemos tratar a
inserção no �m também possuindo duas situações. A primeira situação é quando a lista está
vazia, ou seja, não possui nenhum elemento. Nesse caso, é a mesma situação de incluir o
elemento no início, e podemos chamar o método que recém criamos, como foi observado na
Figura 3.5.
A segunda situação é quando a lista já possui algum elemento. Nesse caso, precisamos atualizar o
atributo próximo do último elemento da lista, como ilustra a Figura 3.7, e também a referência do
�m da lista, também para o novo elemento.
Figura 3.6 - (a) Lista com elementos e em (b) a representação de ligação dos atributos
Fonte: Elaborado pelo autor, 2019
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 10/43
Segue a implementação:
Conforme já conversamos, no temos duas situações. Para veri�car se a lista está vazia podemos
veri�car se o atributo totalElementos da estrutura é igual a 0 (zero). Nesse caso, temos a mesma
situação se fossemos inserir um elemento no início da lista.
Na segunda situação, precisamos atualizar tanto a referência do atributo proximo do último
elemento da lista, como também o �m da lista propriamente dito. É bom notar que precisamos
ter muito cuidado na ordem que efetuamos essas operações pois, se �zermos em outra ordem,
em alguns casos, perdemos a referência dos elementos e não será mais possível recuperá-las. Ao
�nal, incrementamos o valor do  atributo totalElementos em uma unidade.
Inserção em uma Determinada Posição da Lista
Agora que já tratamos a inserção tanto no início como no �nal da lista, vamos tratar a última
situação que é a inclusão do elemento no meio da lista. Nesse caso, é impossível que a lista esteja
vazia, então só temos uma situação, conforme podemos observar na Figura 3.8.
Figura 3.7 - (a) Lista com elementos e em (b) a inserção do novo item no �m da lista
Fonte: Elaborado pelo autor, 2019
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 11/43
Como podemos observar na ilustração, para a inserção do elemento precisamos obter a
referência do elemento anterior que queremos inserir, para atualizar a referência do próximo
item. Mas como faremos isso? Como a lista é encadeada, a única maneira que temos é, a partir do
início, navegarmos de item em item até chegarmos na posição de referência. Para isso, vamos
criar um método chamado pegarItem , conforme segue:
Esse método receberá como parâmetro uma posição e retornará o elemento contido naquela
posição dentro da coleção. Para isso, é necessário veri�car se a posição é válida, ou seja, se
realmente existe um elemento na posição solicitada. Considere, por exemplo, que sua lista possui
apenas três elementos. É possível recuperar o elemento que está na nona posição? Não, pois não
existe essa quantidade de elementos na lista. Assim, podemos criar um método chamado
posicaoValida() , que, como o nome sugere, será responsável por veri�car se a posição é válida
dentro da coleção. O código será apresentado posteriormente.
Se a posição for inválida, vamos lançar um erro, informando essa condição. Quando a posição é
válida, varremos a lista, até encontrar o elemento procurado. Para auxiliar nesse processo, existe
uma variável denominada itemAtual , que primeiramente receberá o elemento que estiver no
inicio . Em seguida, com um laço de repetição, vamos navegando entre os elementos até
encontrar aquele que está na posição do parâmetro. Para realizar essa navegação, basta
atualizarmos o valor da variável itemAtual para receber o próximo elemento
Para descobrirmos se uma posição é válida ou não, devemos considerar a quantidade de
elementos existentes na lista. Vamos considerar também que a primeira posição é o valor 0
(zero). Segue o código:
Assim, se a posição for maior ou igual a 0 (zero) e menor que totalElementos, essa posição será
considerada válida para poder inserir o novo elemento.
Figura 3.8 - (a) Lista com elementos e em (b) a inserção do novo item no meio da lista
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 12/43
Uma consideração importante é que esse método não será utilizado quando deseja-se inserir o
elemento no �nal da lista. Veremos que a rotina principal chamará o método inserirNoFim
diretamente. Por exemplo, considere que uma lista possui os valores 1, 2, 3 e 4. Se o usuário
quiser inserir no �nal da lista o elemento 5, ele deverá passar a posição 4, uma vez que o índice
começa sempre do zero (0). Se veri�carmos se a posição é válida, ela retornará falso mas, como
dissemos, a função não será usada para essa situação.
Agora que já explicamos as duas funções auxiliares, segue o código principal da inserção:
Apesar do código �car um pouco grande, essa função é bastante simples. Como parâmetro temos
a posicao que queremos realizar a inserção e o item propriamente dito.
Se o valor contido no parâmetro posicao for igual a zero,quer dizer que devemos inserir o
elemento no início da lista. Se o valor for igual a quantidade de elementos atuais, devemos inserir
no �nal.
Se a posição for no meio, como já foi discutido, precisamos recuperar os itens do elemento
anterior e acertar a posição dos ponteiros. A referência do elemento anterior será armazenada na
variável itemAnterior . Além disso, o atributo proximo do novo item receberá o elemento que
naquele momento está na posição, cuja referência é itemAnterior.proximo. Ao �nal desse
processo, adicionamos uma unidade no valor do atributo totalElementos .
Remoção no Início da Lista
A remoção de um item no início da lista possui três situações: a primeira, mais simples, é quando
a lista estiver vazia. Nesse caso, podemos lançar um erro com a mensagem que não é possível
realizar a operação, devido a falta de itens.
Na segunda situação, e conforme podemos observar na Figura 3.9, temos a presença de apenas
um item na lista. Quando removemos esse item, as referências tanto do atributo início como
também do atributo �m precisa ser setado para nulo.
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 13/43
Figura 3.9 - (a) Lista com apenas um elemento e em (b) a remoção do item
Fonte: Elaborado pelo autor (2019)
Na terceira situação, temos uma lista com alguns itens. Precisamos apenas posicionar o ponteiro
do início para o segundo item da lista.
Segue o código da remoção no início da lista:
Conforme foi explicado, descobrimos se a estrutura está vazia veri�cando se o atributo inicio é
nulo. Em caso positivo, lançamos um erro com a informação. Em caso negativo, direcionamos o
inicio para o próximo elemento da lista, e decrementamos a contagem dos elementos em 1
unidade. Se essa quantidade, após a operação, for igual a zero, quer dizer que a coleção está
vazia e, dessa forma, precisamos setar o atributo �m para nulo.
Remoção no Final da Lista
A remoção no �nal da lista possui apenas uma situação. Isso porque, caso a estrutura de dados
possuir apenas um item ou estiver vazia, iremos tratar a operação da mesma como sendo
aplicada no início da lista.
Figura 3.10 - (a) Lista com vários elementos e em (b) a remoção do item inicial
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 14/43
Na Figura 3.11 é possível observar a única situação especí�ca: quando a lista possui vários itens.
Nesse caso, precisamos setar a referência para o penúltimo elemento da lista como nulo e
modi�car também a referência do ponteiro �m.
Segue o código:
No código, veri�camos primeiro se a lista está vazia, na qual iremos lançar um erro caso essa
condição for verdadeira. Caso a lista possuir apenas um elemento, iremos tratar como uma
remoção no começo da lista. No �m, caso entrar dentro do bloco else , iremos recuperar o
penúltimo item da lista. Para isso, podemos chamar o método pegarItem e passar como
parâmetro o valor contido no atributo totalElementos , subtraído de 2.  Após recuperar o item,
vamos atualizar a referência do atributo proximo pertencente a ele com o valor nulo. Em
seguida, vamos alterar o valor do atributo �m, passando a referência deste item. No �nal do
método, subtraímos o totalElementos em 1 unidade.
Remoção em uma Determinada Posição da Lista
Para remover um item no meio da lista, precisamos recuperar a referência do item anterior do
item que queremos excluir. Após esse processo, basta atualizarmos o valor do atributo proximo
desse item para o proximo do item a ser excluído . Na Figura 3.12 é possível observar esse
procedimento:
Figura 3.11 - (a) Lista com vários elementos e em (b) a remoção do item �nal
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 15/43
Segue o código:
O código acima representa o método principal de remoção. Após receber a posição por
parâmetro, veri�camos se a posição passada é válida. Além disso, veri�camos também se
estamos removendo o elemento no início ou no �nal da lista. Sabemos que é no início quando a
posição informada é zero, e no �nal, quando a posição é o número de itens subtraído de 1 (um).
Caso não satisfazer nenhuma dessas condições, vamos remover um item do meio da lista. Vamos
pegar a referência do item anterior e atualizarmos às referências destacadas. Ao �nal do
processo, subtraímos a quantidade de elementos em 1 unidade.
Código Completo
Segue o código completo:
Nas próximas seções veremos outros tipos de listas encadeadas como, por exemplo, as listas
duplamente encadeadas e listas circulares. Cada estrutura possui características singulares.
Também veremos exemplos de aplicação desses conceitos em jogos digitais.
praticar
Vamos Praticar
Leia o trecho a seguir:
Figura 3.12 - (a) Lista com vários elementos e em (b) a remoção do item central
Fonte: Elaborado pelo autor (2019).
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 16/43
“As listas ligadas consistem em uma série de elementos que não estão necessariamente armazenados
em posições contíguas da memória, os quais são denominados nós.”
RAMOS, José M. B.; LACERDA, Liluyoud C. de; DUARTE, Sara L. O. Estrutura de dados . Org. Instituto
Federal de Educação, Ciência e Tecnologia; Universidade Federal do Mato Grosso - Cuiabá: UFMT; Porto
Velho: IFRO, 2013. p. 40.
Assinale a alternativa que corresponda às características  de uma lista linear encadeada:
a) Possibilidade de inserção de um elemento apenas no início da lista.
b) Remoção de um elemento apenas no �nal da lista.
c) Contar elemento na lista apenas quando é inserido um novo item.
d) Transformar uma lista linear em uma árvore, sem perdas.
e) Permitir a utilização da estratégia FIFO em uma lista.
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 17/43
Uma lista encadeada pode ter dois tipos de ligações: simples ou duplas. As listas com
encadeamento simples possuem apenas uma única ligação entre os itens da lista, cuja referência
é o próximo elemento. Já nas listas com encadeamento duplo, também chamadas duplamente
encadeadas, os itens possuem ligação tanto com o elemento anterior como posterior a ele
(LAUREANO, 2008, p. 103).
Segundo Laureano (2008, p.104), existem vantagens que podem ser destacadas na utilização de
uma lista duplamente encadeada:
a lista pode ser lida em ambas às direções, o que simpli�ca o gerenciamento da lista.
E, no caso de alguma falha de equipamento, onde uma das extremidades seja
perdida, a lista pode ser reconstruída a partir da outra extremidade. (LAUREANO,
2008, p. 104).
Listas Duplamente EncadeadasListas Duplamente Encadeadas
Figura 3.13 - Lista duplamente encadeada
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 18/43
Vamos analisar os aspectos de implementação.
Representação e Operações
As operações de uma lista duplamente encadeada são as mesmas de uma lista encadeada
simples. A única diferença é que no elemento também iremos armazenar, além da referência
para o próximo elemento, uma referência para o elemento anterior.
Segue o código da classe item:
Nas próximas seções vamos explorar os aspectos técnicos e especí�cos desse tipos de lista.
Inserção de um Item no Começo da Lista
Quando comparamos com a lista de encadeamento simples, a inserção no início da lista não
houve alterações. Isso porque, como não existe um elemento anterior ao primeiro da lista, não é
necessário armazenar uma referência. O novo elementoterá seu atributo anterior com o valor
nulo, até o momento deste não ser mais o primeiro da lista.
Inserção no Fim da Lista
A inserção no �nal da lista possui alterações. Quando inserimos o item no �nal precisamos alterar
agora o atributo anterior do novo item. Na Figura 3.15 torna-se possível observar as alterações
que ocorrem nessa operação:
Figura 3.14 - Lista duplamente encadeada
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 19/43
Segue o código:
Você irá perceber que os códigos da lista duplamente encadeada são muito parecidos com os
outros códigos. Nessa  operação, tivemos a inclusão de apenas uma linha de programação, que é
a atribuição de valor para o atributo item.anterior, recebendo a referência do último elemento
atual da lista.
Inserção em uma Determinada Posição da Lista
Para inserir um elemento no meio de dois outros elementos, precisamos alterar os atributos
tanto do elemento anterior ao índice da inserção, como também do novo elemento. Na Figura
3.16, queremos incluir o elemento 20 entre outros dois elementos. Perceba que é necessário
modi�car o atributo próximo do elemento 16 e também a referência anterior do elemento 26,
este último é o elemento atual da posição.
Segue o código da implementação:
Figura 3.15 - Em (a) uma lista com elementos e em (b) a inserção no �nal da lista
Fonte: Elaborado pelo autor (2019).
Figura 3.16 - Em (a) uma lista com elementos e em (b) a inserção no meio da lista
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 20/43
No código temos as validações de lista vazia, além da inserção no início e �m da lista, igual ao da
lista encadeada simples. A alteração do código está dentro do bloco else : por ser uma lista
duplamente encadeada, a partir do elemento atual conseguimos recuperar o elemento anterior.
Dessa forma, o elemento anterior é dado pelo atributo itemAtual.anterior. Para acessarmos o
atributo proximo do elemento anterior, podemos usar a instrução itemAtual.anterior.proximo.
Esse atributo receberá o novo item.
Feito o ajuste dessa primeira referência, podemos ajustar também as referências anterior e
próximo do  novo item, que receberão o item anterior - representado por itemAtual.anterior ,
conforme já mencionado – e o item atual. Após ajustar todas as referências necessárias,
somamos 1 ao atributo totalElementos , responsável por contabilizar a quantidade de itens na
lista.
Remoção no Início da Lista
O método de remoção de um elemento no início da lista não houve alterações signi�cativas. A
única situação nova, porém, é o ajuste da referência anterior para o segundo elemento da lista –
o elemento que, após a exclusão, virará o primeiro elemento.
Figura 3.17 - Em (a) uma lista com elementos e em (b) a remoção no início da lista
Fonte: Elaborado pelo autor (2019)
Segue o código:
No código, temos as mesmas situações já discutidas anteriormente. A única diferença é a inclusão
do bloco else . Se mesmo após a exclusão do item a lista ainda possuir elementos, é necessário
alterar a referência anterior do elemento que está no início para nulo.
Remoção no Final da Lista
A remoção do �nal da lista para uma lista duplamente encadeada é igual ao de uma lista
simplesmente encadeada. Iremos realizar apenas uma alteração para melhorar o código, uma vez
que não precisamos mais recuperar o penúltimo item da lista utilizando o método pegarItem .
Agora podemos recuperá-lo utilizando o atributo �m.proximo , e é isso que iremos fazer. Essa
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 21/43
alteração aumenta a performance do código, pois não é mais necessário varrer a lista de item em
item até encontrarmos esse elemento.
Segue o código:
No código acima, a alteração se encontra no bloco else . Podemos perceber que o novo �m da
lista será o penúltimo elemento, ou seja, this.�m.anterior. Após realizarmos esse ajuste,
precisamos também limpar a referência do �m.proximo , por não existir mais nenhum elemento
na sequência desse item.
Remoção em uma Determinada Posição da Lista
Na remoção de um elemento qualquer de uma lista duplamente encadeada, precisamos receber
uma posição que representa o índice do elemento. Se o elemento estiver no início ou no �m da
lista, tratamos essa situação de acordo com as características explicadas nas seções anteriores.
Outra situação é quando o elemento está no meio da lista, ou seja, entre dois outros elementos.
Diferentemente da lista simplesmente encadeada, podemos agora recuperar tanto o item
anterior como o sucessor utilizando a mesma referência, por causa dos atributos anterior e
proximo desse item. Na Figura 3.19 é possível observar essa situação.
Figura 3.18 - Em (a) uma lista com elementos e em (b) a remoção no �nal da lista
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 22/43
Podemos observar na Figura 3.19 que precisamos alterar valores do item anterior como também
do item posterior ao elemento alterado. Segue o código da implementação dessa funcionalidade:
No código acima, todas as situações são iguais ao da lista simplesmente encadeada exceto o
código presente no bloco else , singular para a lista duplamente encadeada. Como foi dito no
parágrafo anterior, precisamos recuperar a referência do elemento anterior a partir do elemento
que queremos excluir. O elemento que queremos excluir iremos chamar de elemento atual. Para
recuperarmos a referência do elemento atual utilizamos a função pegarItem , passando a
posição correspondente por parâmetro.
Agora que já recuperamos elemento atual, cuja referência está armazenada na variável
itemAtual , podemos recuperar o elemento anterior a ele, acessando o atributo
itemAtual.anterior. Podemos recuperar também o item sucessor ao elemento atual, acessando
a propriedade itemAtual.proximo . No �nal, realizamos as operações que estabelecem o
relacionamento do elemento anterior do item posterior.
Código Completo
Segue o código completo:
Na próxima seção veremos um outro tipo de lista bastante utilizado: a lista circular simplesmente
encadeada. A diferença dessa lista para as demais está no seu formato: o último elemento é
ligado com o primeiro, ou seja, o próximo elemento do item �nal da lista é o início da lista. Essa
estrutura permite facilitar a representação de alguns contextos encontrados no mundo real.
Figura 3.19 - Em (a) uma lista com elementos e em (b) a remoção no meio da lista
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 23/43
praticar
Vamos Praticar
Leia o trecho a seguir:
“[...] enquanto em uma lista simples ligada, cada nó (elemento) conhece (aponta) apenas o próximo nó,
nas listas duplamente ligadas, os nós conhecem dois outros nós, seu antecessor e seu sucessor, com
exceção da cabeça e da cauda em que o primeiro aponta apenas para o seu sucessor e o segundo aponta
apenas para o seu antecessor. ”
RAMOS, José M. B.; LACERDA, Liluyoud C. de; DUARTE, Sara L. O. Estrutura de dados . Org. Instituto
Federal de Educação, Ciência e Tecnologia; Universidade Federal do Mato Grosso - Cuiabá: UFMT; Porto
Velho: IFRO, 2013. p. 53.
Sobre os conceitos de listas simplesmente encadeadas e duplamente encadeadas, assinale a alternativa
que corresponda a uma aplicação desse conceito:
a) Representação de Mapas Rodoviários
b) Representação de uma árvore genealógica.
c) Cálculo da melhor jogada em um jogo de xadrez.
d) Hierarquia e agrupamento deobjetos
e) Livros desejados em um site de compras.
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 24/43
Dizemos que uma estrutura de dados é circular quando o item de primeira posição sucede o da
última posição (RICARTE, 2008, p. 48).   Assim como na lista encadeada temos as formas de
implementação com ligação simples ou dupla, na circular também temos essas variações: lista
circular simplesmente encadeada e lista circular duplamente encadeada .
Iremos tratar nesta seção apenas da implementação da lista circular simplesmente encadeada
. Esse tipo de lista é bem parecido com a lista simplesmente encadeada: sua representação e
operações são as mesmas. A única diferença é que precisa nos preocupar em manter a conexão
do último elemento da lista com o primeiro.
Representação
Existem dois tipos de implementação de uma lista circular: podemos utilizar dois ponteiros inicio
e �m , de forma semelhante à lista encadeada, ou apenas um ponteiro, denominado lista
circular com nó cabeça (HONDA e Paraboni, 2011).  Nessa última representação, existe apenas
um ponteiro que aponta para o primeiro elemento da lista e, a partir dele, é possível acessar a
referência dos demais.
Diante das duas opções iremos explorar apenas a implementação com utilização de dois
atributos: início e �m. Essa implementação é bem semelhante as outras, e essa escolha tem
objetivo de facilitar o entendimento do leitor. Os códigos demonstrados sempre serão
comparados com a implementação da lista simplesmente encadeada.
Inserção de um Item no Começo da Lista
Para inserir no começo da lista, temos duas situações. A primeira é quando a lista não possui
nenhum item, e por se tratar de uma lista circular, o próximo elemento do item seria ele mesmo,
Lista CircularLista Circular
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 25/43
conforme é possível veri�car na Figura 3.20.
A segunda situação é quando inserimos um novo item em uma lista que já possui elementos.
Nesse caso, é necessário alterar tanto a referência inicio e do elemento, como também a
referência proximo do último elemento da lista, conforme podemos observar na Figura 3.21.
Figura 3.21 - Em (a) uma lista circular e em (b) a inserção no início da lista
Fonte: Elaborado pelo autor (2019)
Segue o código:
No código acima, podemos observar que inserimos um novo bloco else . O comando contido
nesse bloco só será executado quando a lista possuir mais de um elemento. Nesse caso, a
referência proximo do último item irá receber o inicio da lista, sempre atualizando esse valor
para essa operação.
Inserção de um Item no Final da Lista
Nesse caso, a inserção é realizada de forma muito semelhante ao de uma lista simples
encadeada, porém o atributo próximo do novo item receberá o início da lista, conforme é possível
Figura 3.20 - Em (a) uma lista circular sem elementos e em (b) a inserção do primeiro elemento
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 26/43
observar na Figura 3.22.
Segue o código:
Perceba que, na terceira linha dentro do bloco else , o atributo proximo receberá o início da lista.
Na implementação da lista encadeada simples, essa referência era mantida como nula. Esse
comando permite que a lista mantenha sua característica circular.
Inserção no Meio da Lista
A inserção do meio da lista permanece com as mesmas características de implementação, uma
vez que não as características circulares da lista se concentram nos elementos de inicio e �m .
Assim, o código permanece intacto, sem considerações.
Remoção no Início da Lista
A remoção no início da lista possui duas situações: quando a lista possui apenas um elemento ou
quando possui mais elementos. Na primeira situação, conforme podemos observar na Figura
3.23, precisamos atribuir os valores inicio e �m da lista para nulo.
Figura 3.22 - Em (a) uma lista circular e em (b) a inserção no �nal da lista
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 27/43
Na segunda situação, após a exclusão do elemento, precisamos alterar a referência proximo do
último elemento  – que antes da exclusão era o penúltimo – para se conectar com o início da lista,
conforme podemos observar na Figura 3.24.
Segue o código:
Para a solução dessa nova situação, foi inserido no código um bloco else . Se mesmo após a
exclusão a lista ainda possuir elementos, o último elemento atual da lista terá como elemento
sucessor o início da lista. Assim conseguimos manter a característica circular da estrutura de
dados.
Remoção no Fim da Lista
A remoção no �m da lista é mais simples. Basta apenas após a exclusão do elemento, ao invés de
atribuirmos ao atributo próximo do último elemento da lista o valor de nulo, a referência do
elemento inicial da lista., conforme podemos observar na Figura 3.25:
Figura 3.23 - Em (a) uma lista circular com um único elemento e em (b) a remoção do elemento
Fonte: Elaborado pelo autor (2019)
Figura 3.24 - Em (a) uma lista circular com um único elemento e em (b) a remoção do elemento
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 28/43
Segue o código:
A alteração do código foi realizada dentro do bloco else. Agora, após recuperarmos a referência
itemAnterior, atribuímos ao atributo próximo o valor correspondente ao elemento inicial da lista.
Todas as outras características do código permaneceram de acordo com a implementação da lista
simplesmente encadeada.
Remoção no Meio da Lista
A remoção no meio da lista permanece com as mesmas características de implementação, uma
vez que as características circulares da lista se concentram nos elementos de inicio e �m . Assim,
o código permanece intacto, sem considerações.
Código Completo
Segue o código completo:
praticar
Vamos Praticar
Leia o trecho a seguir:
Figura 3.25 - Em (a) uma lista circular e em (b) a remoção do elemento
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 29/43
“Mesmo que uma lista circular não tenha início ou �m, sempre será necessário que algum nodo seja
marcado de forma especial, sendo chamado de cursor. O nodo cursor serve como ponto de partida
sempre que for necessário percorrer a lista circular. E se for possível lembrar do ponto de partida, então
é possível saber quando se completou a volta [...]”.
GOODRICH , Michael T.,  TAMASSIA, Roberto. Estruturas de Dados e Algoritmos em Java . 5 ed. Editora
Bookman. ISBN-10: 8582600186. 2013. p. 128.
Sobre as listas circulares encadeadas, assinale a alternativa correta:
a) Quando implementamos uma lista circular encadeada, precisamos sempre utilizar duas
referências (início e �m) para gerenciar essa estrutura, não havendo outras alternativas.
b) Quando inserimos um item no início de uma lista circular, podemos alterar apenas a referência
do início para esse item. Outras validações não são necessárias.
c) Quando inserimos um elemento no meio de uma lista circular, devemos alterar os valores de
referência dos atributos início e �m, além de veri�car se o elemento já existe na lista.
d) Quando inserimos um elemento no meio da lista circular, o procedimento que devemos
executar é o mesmo de uma lista linear. Podemos aproveitar o código, sem modi�cações.
e) É impossível concatenarmos duas listas circulares em uma, uma vez que não é possível de�nir
qual o elemento inicial e �nal de cada umadessas listas.
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 30/43
É fácil de compreender que as listas encadeadas sejam aplicáveis em diversas situações no
mundo dos games. Elas são versáteis, possuem diversos tipos e permitem a inclusão e exclusão
em qualquer posição da coleção.
Alguns jogos, por exemplo, permitem que o jogador carregue diversos tipos de armamento, e é
necessário criar um mecanismo para que ele possa trocar e escolher qual armamento queira
utilizar. Esses armamentos podem ser armazenados em listas e, de acordo com o progresso do
usuário durante as fases e os novos equipamentos que ele conquista, esses itens podem ser
adicionados em uma posição especí�ca da lista. A Figura 3.26 ilustra um exemplo de um
personagem e opções de equipamentos que ele pode utilizar.
Outra aplicação possível é um sistema de inventário de itens (PENTON e LAMOTHE, 2002, p. 176).
Nesse tipo de mecanismo, temos uma quantidade máxima de itens que podem ser adicionados e,
além disso, algumas variações permitem o usuário alterar a ordem dos itens contidos.
Listas Encadeadas Aplicadas emListas Encadeadas Aplicadas em
Jogos DigitaisJogos Digitais
Figura 3.26 - Soldado de combate robótico com armas
Fonte: Freepik/ Vectorpocket.
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 31/43
Criando um Score
No contexto de um jogo digital, temos a questão da tela de score (GOODRICH e TAMASSIA, 2013).
A tela de score é uma tela que existem em alguns jogos indicando a pontuação máxima obtida
pelos jogadores. Caso houver um novo jogador que atingiu uma elevada pontuação e mereça
entrar no score, esse jogador deve ser inserido em uma determinada posição dessa sequência,
alterando a ordem dos demais.
Vamos realizar a implementação da tela de score ilustrada na Figura 3.27. Primeiro precisamos
de�nir quais as principais características que serão apresentadas: no caso, nome do jogador e a
pontuação obtida. Essas características serão representadas por meio de atributos .
Precisamos entender que o score é uma lista de itens e que, para cada item, devemos armazenar
os valores relacionados aos nomes do jogador e pontuação. Além disso, precisamos também criar
um atributo que será a referência para o próximo item da lista encadeada. Vamos ver então como
�caria o código em Javascript:
Dentro do escopo de classe, delimitado pelas chaves, temos a declaração de três atributos:
nomeJogador , pontuação e proximo . Os dois primeiros atributos são as características que
queremos armazenar do nosso problema. O atributo proximo representa o encadeamento para o
próximo elemento da lista.
Implementação da Estrutura de Dados Lista
A lista que vamos utilizar possuirá o mesmo código que foi apresentado anteriormente.
Poderíamos limitar a quantidade de itens, uma vez que o score apresenta apenas a pontuação
dos cinco primeiros - top 5 .
Outra característica que poderíamos implementar na lista é a ordenação já no momento da
inclusão dos itens, de modo que respeite uma ordem decrescente de valores. Entretanto, não
abordaremos esse assunto por possuir bastante profundidade e ser necessário dedicar um
tópico para isso. O código completo dessa estrutura será apresentado logo adiante.
Figura 3.27 - Tela de score
Fonte: Elaborado pelo autor (2019)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 32/43
Inicialização da Lista e Criação dos Elementos Qrá�icos
Vamos criar um método iniciarJogo , que será chamado no início do programa. No método,
iremos realizar alguns procedimentos:
Instanciar um novo objeto lista ;
Criar as instâncias de cinco itens e adicioná-los à lista;
Imprimir título e cabeçalhos da listagem;
Imprimir itens da lista, com destaque para o jogador com maior pontuação.
Segue o código:
A primeira parte do método, criamos a instância de um novo objeto para a lista e também
inserimos nela 5 (cinco) novos elementos. Perceba que propositalmente estamos inserindo os
elementos em ordem decrescente de pontuação, uma vez que o contexto desta aplicação exige
essa característica.
Após criarmos nossa lista, vamos imprimir primeiro o título no objeto canvas . Para isso,
recuperamos as referências dos objetos canvas e context 2D (do próprio canvas ). Depois,
de�nimos o estilo da fonte como Algerian e tamanho 42px, e a cor do preenchimento como
branco ( white ). Em seguida, usamos o método �llText para imprimir um texto no canvas ,
informando como parâmetro um texto e as coordenadas x e y que esse texto será apresentado
no canvas .
Com a mesma lógica vamos imprimir também os cabeçalhos da tabela: primeiro iremos de�nir as
características da fonte: Consolas tamanho 30px. Em seguida, imprimimos cada um dos dois
cabeçalhos utilizando o método �llText , onde informamos os textos e as coordenadas
correspondentes.
Para imprimir os cinco primeiro elementos da lista, vamos criar um laço de repetição cuja variável
de controle irá de 0 (zero) à 5 (cinco). Para cada um desses valores, vamos recuperar o item na
lista com o mesmo índice, utilizando a função pegarItem e, após esse procedimento, imprimir os
valores do nome do jogador e pontuação. A coordenada y do canvas que será utilizado esses
valores deve respeitar a fórmula:
onde os valores 230 é a coordenada de altura inicial e 45 é o incremento de altura que será
adicionado para cada linha da lista. Esses valores foram estabelecidos de forma empírica.
Para de�nir as cores dos itens, se o índice i for igual a 0 a cor será de�nida como amarelo. Isso foi
criado para destacar o item que contém a maior pontuação da lista. Caso contrário, ou seja, para
todos os demais itens da lista, a cor impressa será o ciano.
Código Completo
y = 230 + (i ∗ 45)
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 33/43
Por �m, segue o código completo da solução. Tanto as partes HTML como o código em Javascript
estão descritas.
Com essa implementação, �nalizamos o conceito de listas encadeadas. Para rodar o código, basta
apenas copiar o código e colar, salvando o arquivo com a extensão .html. Em seguida, abra o
arquivo em um navegador com suporte à linguagem HTML5.
praticar
Vamos Praticar
Uma animação envolve exibir uma sequência de imagens estática de forma rápida, su�ciente para seja
possível interpretá-las como um movimento. Um tipo de animação é a animação computadorizada, que
consiste em recalcular a posição de um objeto e exibí-lo novamente ao usuário.
MEYER, Jeanine. The Essential Guide to HTML5 : Using Games to Learn HTML5 and JavaScript. 2nd ed.
Editora Apress. ASIN B07KFQ33RL. 2018. p. 81-82.
Assinale a alternativa que corresponda a correta implementação de uma animação utilizando a estrutura
de dados lista:
a) Se implementarmos uma animação utilizando uma lista circular, onde cada quadro representa
um item da lista, não é possível descobrir o começo da animação.
b) Se implementarmos uma animação com uma lista duplamente encadeada, onde cada quadro
representa um item da lista, a animação não poderá ser executada.
c) A aplicação de uma lista duplamente encadeada para a animação inibe que a mesma seja
executada de trás para frente, caso tenha essa necessidade.
d) Podemos utilizar qualquer tipo de lista (simples, duplo encadeamento ou circular) para
implementar a animação, cada qual com suas vantagens e desvantagens.
e) A utilização de uma lista circular para implementação da animação di�culta, caso houver essa
necessidade, em executar a animação diversas vezes seguidas.
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 34/43
indicaçõesMaterial Complementar
FILME
O Triunfo dos Nerds - ALTAIR
Ano : 1996
Comentário : Baseado no livro “The Rise of Accidental Empires”, esse
�lme é destinado aqueles que gostam ou atuam na área de TI, e
também para empreendedores. É um documentário que conta sobre
o primeiro computador pessoal - o ALTAIR 8080 - e também sobre o
início de grandes empresas, como Microsoft, Apple e IBM.
TRA ILER
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 35/43
LIVRO
CSS3: o Manual que Faltava
Editora : Alta Books; Edição: 3 (2015)
Autor :  David Sawyer Mcfarland
ISBN : 8576088630
Comentário : Esse livro aborda os conceitos de CSS3 e HTML5,
envolvendo formatação de páginas e uso de recursos que enriquecem
a experiência do usuário, fornecendo detalhes sobre a utilização de
imagens grá�cas, criação de formulários e tabelas, entre outros.
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 36/43
conclusão
Conclusão
Nessa unidade tivemos a oportunidade de conhecer conceitos sobre Tipos Abstrato de Dados
Lista. Nesse contexto, aprendemos um pouco sobre as formas de implementação em um
linguagem de programação.
Discorremos também sobre aplicações desse tipos de estrutura em mecanismos de jogos e
também no mundo real. Por ser bastante versátil e possuir diversas formas e adaptações,
podemos implementar as listas até mesmo em situações que seriam possíveis a implementação
de pilhas ou �las.
Por �m, você pôde compreender, também, uma forma de aplicar os conceitos vistos na unidade
de forma prática, com a criação de uma tela de score , onde pode ser criado um ranking com os
jogadores que conquistaram a maior pontuação em um game.
referências
Referências Bibliográ�cas
CELES, Waldemar; CERQUEIRA, Renato, RANGEL, José Lucas. Introdução a Estrutura de Dados :
Com técnicas de programação em C. 2 ed. Editora Campus. Elsevier. 2016 .
GOODRICH , Michael T.,  TAMASSIA, Roberto. Estruturas de Dados e Algoritmos em Java . 5 ed.
Editora Bookman. ISBN-10: 8582600186. 2013.
HONDA, Willian Yukio; PARABONI; Ivandré. ALGORITMOS E ESTRUTURAS DE DADOS . Disponível
em: <
https://edisciplinas.usp.br/plugin�le.php/4379241/mod_resource/content/0/apostila_AED1_completo.pd
>. Acesso em: 16 dez. 2019. 2008.
LAUREANO, Marcos. Estrutura de dados com Algoritmos e C .  Editora Brasport. 2008.
PENTON, Ron; LAMOTHE, André. Data Structures for Game Programmers . 1 ed. Muska &
Lipman/Premier-Trade. 2002. ISBN-10: 1931841942.
https://edisciplinas.usp.br/pluginfile.php/4379241/mod_resource/content/0/apostila_AED1_completo.pdf
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 37/43
RICARTE, Ivan Luiz Marques. Estrutura de Dados . Disponível em: <
http://calhau.dca.fee.unicamp.br/wiki/images/0/01/EstruturasDados.pdf >. Acesso em:
16/12/2019. 2008.
http://calhau.dca.fee.unicamp.br/wiki/images/0/01/EstruturasDados.pdf
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 38/43
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 39/43
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 40/43
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 41/43
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 42/43
03/04/2023, 21:13 Ead.br
https://student.ulife.com.br/ContentPlayer/Index?lc=S7S6ENZny18%2blDVzjSI6gg%3d%3d&l=VPic%2fFbeAnDPgloJidbuAg%3d%3d&cd=ucz… 43/43