Estruturas de Dados - Listas Encadeadas

tu estavas alunos sejam bem-vindos a aula de hoje na aula de hoje nós falaremos sobre listas encadeadas o roteiro que nós vamos seguir na aula de hoje vai ser o seguinte primeiramente nós falaremos O que que é uma vista de Neve São listas lineares nós temos utilizado esse termo mas ainda não demos uma definição para ele depois nós falaremos sobre estás encadeadas e depois nós falaremos sobre implementação de pilhas ou listas encadeadas em implementação de filas com listas encadeadas noiva já deve surgir a primeira dúvida para você porque nós vamos implementar pilhas e filas agora

com listas encadeadas se Nossa implementação anterior que foi feita com vetores a gente já tinha conseguido fazer com que as inserções e as remoções tá sem tempo constantes daí você se pergunta é Qual perfeccionismo é esse que vai fazer com que a gente implemente aquelas estruturas utilizando uma nova maneira a organizar os dados da memória então a resposta é que essa nova maneira de organizar dados na memória ela confere algumas vantagens traz algumas desvantagens também mas ela Confere aí algumas vantagens então é como se fosse uma nova opção de implementação para pessoa que quiser utilizar

pilhas e filas e vamos começar com uma definição de listas lineares o que que são listas lineares são estruturas de dados na qual cada elemento é precedido por um elemento e sucedido por outro elemento com exceção do primeiro que não tem predecessor e do último que não tem sucessor Então nesse caso nós podemos imaginar que é uma lista O que que é uma lista é uma sequência em que cada elemento tem no máximo um predecessor e no máximo um sucessor e isso gera uma ordem nos elementos que podem até que pode até mesmo ser a

ordem de inclusão porque eu coloquei que pode ser a ordem de inclusão porque vai ser a ordem da aula de hoje então a ordem de inclusão vai ser a ordem que os elementos entre a gente vai definir quem é o predecessor e quem é o sucessor de um dado elemento dentro dessa sequência as estruturas filha e Fila Então são listas lineares por quê Porque a gente pode imaginar elas por exemplo a ordem que a gente sincera na pilha a gente pode a gente pode imaginar como o topo da pilha ele tem um sucessor ou predecessor

depende da maneira como você imaginar e assim por diante ele não pode ter nenhum elemento dentro de uma pilha ele pode ter dois predecessores ou dois sucessores não ele tem apenas um para de sensor e um sucessor pelo menos ele pode ser mais nada dessa forma e continuando aqui nós implementamos a pilha EA fila comunistas delineares sequenciais então nós já sabemos que o que nós fizemos nas aulas anteriores era uma lista de Near e Nós também vamos dizer que era uma lista de né sequencial então um vetor é uma lista de né a sequencial o

que que é lista de né sequencial indígenas lineares sequenciais a ordem lógica dos elementos ou seja aquela ordem vista pelo usuário aquela ordem que a gente imagina os elementos é a mesma da ordem física ou seja é a mesma da ordem em que os elementos Estão realmente da memória o ou seja se nós estamos imaginando que dois elementos eles estão lado a lado na nossa ordem lógica então eles estão bem estão lado a lado na memória por quê Porque eles têm que estar contigo ou na memória dentro dessa característica de listas lineares sequenciados e essa

toda a caracterização de um vetor um vetor Então seria uma lista de Neal sequencial e essa organização ela que confere acesso em tempo constantes a qualquer elemento da do índice do elemento por quê porque se a gente tem um vetor é como se a gente tivesse o endereço base aqui do vetor se eu quero por exemplo o índice 4 é apenas uma operação matemática que eu tenho que fazer eu sei o tipo dos elementos por exemplo inteiros e tem eu sei quanto eu tenho que deslocar para obter o elemento de índice quatro aqui dentro desse

vetor dado que eu sei que tipo Então posso obter o elemento quatro elementos 01 do Sacramento três Me desculpe então eu posso obter o quarto elemento que seria o elemento três em tempo constante e o poder ter acesso aos elementos em tempo constante Confere aí algumas vantagens na hora de implementar códigos eficientes por exemplo supondo que eu tenho um vetor ordenar tá esse vetor ordenado aqui 16 22 23 33 35 37 4.553 é um vetor que está na ordem do menor para o maior o acesso em tempo constantes é o que permite que eu faça

um algoritmo por exemplo de busca binária por quê Porque eu posso acessar o elemento que está no meio seria as elemento 33 em tempo constante então eu posso acessar ele verificar eu tô buscando o elemento 23 nessa minha busca binária eu quero 23 eu posso comparar o 23 direto com quarto elemento aqui já que eu tenho que pensar que meus elementos são de 0 a 8 de dentro desse vetor Então eu posso ir lá no 33 de verificar Olha você é o 23 aí aqui ele vai dizer para mim não só o 33 Você tá

buscando 23 como você tá buscando 23 e eu sou um Array ordenado eu faço parte de uma reordenado Ignore todo mundo que vem depois de mim então eu posso avisar vou ignorar todo mundo que estava depois do 33 aqui é ignorava e agora eu vou fazer a busca nesses elementos daqui e o que é que eu faço na busca binária eu sigo a mesma estratégia eu procuro elemento do meio eu consigo acessar ele tempo constante tem colar no 22 é pergunto Olha você é o 23 ele vai dizer não eu não sou 23 as ou

22 entre a tanto como eu estou em uma Rei ordenado Isso quer dizer que você não precisa mais procurar quem vem antes de mim porque eles são menores do que eu então Ignore todo mundo que vem antes de mim porque são menores do que eu e procure agora quem é depois de mim como eu já testei de norado boa eu sei que eu tenho que procurar nesses dois elementos e eventualmente eu acho 23 Essa é a ideia da busca binária porque a busca binária funciona em um vetor ordenado porque eu consigo acessar qualquer elemento e

tempo constante e vamos pensar agora em vantagens e desvantagens tá Quais são as vantagens as vantagens são as que eu falei basicamente o o acesso em tempo constante e as desvantagens as desvantagens é que nós precisamos alocar espaço suficiente para todos os elementos de uma só vez se fossem uma rei em vetor estático a gente teria que local antes da compilação tipo será que eles eram o tamanho receber ator antes de compilar vai ser tamanho sempre E se a gente usasse dinâmico como a gente tem feito até agora a gente pode dizer qual vai ser

o tamanho do vetor em tempo de execução entre a tanta gente pode dizer apenas uma vez você diz você é louco o espaço e daí você não pode mais aumentar e diminuir se você quisesse aumentar você ter o que terá que pegar todo aquele vetor copiar com uma outra região de memória tamanho maior e e daí você poderia continuar utilizando bom então caso falte algum espaço seria então oneroso mover todos os elementos para uma nova posição de memória com mais espaços fazer todas essa transferência da memória onerosa computacional Mix é só temos essa primeira desvantagem

às vezes é difícil estimar as vezes a gente erra demais se for acabei usando só teste quanto você alocou 10 milhões só você desperdiçou memória ou outro caso que se pode eu achava que eu penso que 10 milhões eram suficientes quando você precisou Presidente uso então saiu perdendo por conta de ter feito uma estimativa diferente daquilo que você realmente eu te disso é bom e o outro problema das listas lineares sequência nós vamos voltar por exemplo do Array ordenado do vetor ordenado tá bom e no arranjo ordenado manter a ordem é um pouco onerosa por

quê Porque talvez sejam necessários muitos deslocamentos em memória tá só para manter um vetor ordenado o quê que isso quer dizer o quê que isso quer dizer o seguinte supondo que eu quero manter essa sequência ordenada já tinha 16 22 23 25 e 27 33 e assim por diante eu quero misterioso 27 para exterior 27 eu preciso colocar ele depois do 25 e antes do 33 o quê que isso quer dizer que todos esses elementos que estão aqui eles terão que ser deslocados uma posição para direito se eu quisesse também por outro lado no mesmo

vetor original remover o 22 para manter esse vetor ordenado ao remover o 22 eu vou ter que pegar todos esses elementos aqui e deslocar uma pose a esquerda então manter esta estrutura aqui ordenada ela talvez seja um pouco onerosa tá aí você começa a pensar se você não for fazer muitas músicas supondo que você faz muita infecção e muita remoção e quase nada de busca que que você teria que fazer então você teria que o criar uma maneira melhor de utilizar a sua memória uma maneira de organizar os seus dados que não forçasse você vai

fazer tanto de deslocamentos na hora que você quiser esperei remoto e eu no final das contas a gente tem maneiras diferentes de fazer a mesma coisa você como desenvolvedor é que vai ter que medir os prós e contras de cada uma delas vantagens desvantagens e decidir e para sua aplicação uma delas é melhor do que a outra bom então vamos dar uma nova opção Eu já falei sobre as vantagens e desvantagens das listas lineares sequenciais que era o nosso Beto Vamos falar das listas encadeadas que que é uma lista encadeada é uma lista de Near

ou seja tem essa questão do sucessor e o predecessor só que a ordem lógica dos elementos não é a mesma da ordem física ou seja você pensa de uma forma mas na memória está de uma forma completamente diferentes por quê Porque nessa lista encadeada os elementos estão espalhados na memória em várias posições de memória não estão contidos o elemento 2 o segundo elemento na sua ordem lógica não está do lado do elemento pode estar antes pode estar depois pode estar em outro módulo de memória tanto faz um a cada elemento nesse caso precisa indicar em

que endereço de memória está o seu sucessor o melhor com que endereço e demora o seu sucessor pode ser encontrado de modo a manter a ordem lógica ótimo nossas elementos estão espalhadas e agora todo mundo aponta para o seu sucessor algo parecido com isso daqui eu imaginei que isso daqui a memória e todos os meus elementos estão espalhados na memória percebam que isso aqui é uma vista ordenada esta de história de nada ela é logicamente né uma forma lógica é semelhante a esta dista sequencial aqui em cima entretanto imagina que os elementos estão em todos

os lugares da memória primeira coisa que nós precisamos entender mas precisamos entender aqui dado índice de um elemento para acessar quem é o valor que está nesse índice por exemplo eu quero o índice três Eu tenho 23 eu quero obter você não vai mais obter diretamente em tempo constante você vai ter que iniciar a sua busca no primeiro elemento depois você vai ter que segundo elemento para o terceiro elemento até chegar aqui no elemento de índice 3 que é o quarto elemento o que isso quer dizer o quê que isso quer dizer é que com

essa nova forma de organizar os dados da memória a gente já não pode mais acessar qualquer elemento em tempo constante isso já quer dizer o que que já retiro aí uma grande vantagem que tinha nas listas lineares sequencias 1 bom então por que usaria uma estrutura que tem uma certa desvantagem em relação à dista General sequenciais porque ela também tem vantagens não só para você entender o porquê eu te devo ter mencionado aquela desvantagem em relação à vista que ganhar sequencial perceba uma coisa como eu não posso mais acessar qualquer elemento em tempo constante a

busca binária ela deixa de fazer sentido Se você estiver implementando em uma lista encadeada por quê Porque para obter o elemento do Meio isso porque essa é a ordem lógica mas a implementação ela é feita mas a implementação dela é uma lista encadeada para obter esse elemento do meio aqui seja feita que acessar o primeiro já teve que acessar o segundo para depois das e sair então se você já teve que acessar então era melhor ter feito a busca sequencial já cê sabe já procurava a ser e você está querendo buscar então busca binária ela

deixa de fazer sentido se você está utilizando uma distinta Diana e entretanto essa nova estrutura vai possui vantagens o número de elementos ele pode aumentar ou diminuir durante a execução do programa que ela grande desvantagem da lista sequenciais a manutenção da ordem lógica lá não existirá deslocamento de elementos outra grande vantagem porque supondo que eu tenho essa lista que quero remover o elemento número 15 para remover o 15 basta desalocar a memória e fazer o 10 apontar por 19 ninguém vai precisar mudar de lugar e para remover por exemplo para inserir por exemplo elemento 21

você simplesmente Coloca ele qualquer lugar da sua memória depois pegam o elemento 19 Episódio você não vai mais apontar para o 22 você vai apontar por 21 e o 21 agora vai apontar por 22 Então ninguém mais precisa se deslocar na memória e Vamos repensar agora em como nós implementar íamos pilhas com listas encadeadas como pilhas são estruturas lineares nós podemos implementar Claro com listras em cadeado só temos que lembrar o que que é uma pilha uma estrutura que o primeiro elemento a entrar tem que ser o último a sair o último elemento a entrar

tem que ser o primeiro a sair as inserções e remoções elas ocorrem na cabeça já vimos isso em aulas anteriores e as inserções e remoções devem ocorrer em tempo constante é porque porque com vetores a gente já tinha conseguido e tempo constante então aqui a gente quer manter o tempo constante Vamos pensar então em como nós implementar esse exemplo aqui do meu lado esquerdo é o mesmo exemplo que nós vimos em aulas anteriores tá então nós colocamos o elemento 35 numa pilha vazia como seria Isso numa diz Tem cadeado seria simplesmente pegar um ponteiro e

apontar para uma região de memória Onde tem um elemento 35 na hora de inserir o elemento desce como nós fazemos uma lista sequencial no Beto nós simplesmente seríamos o teste e depois diríamos olha o 10 agora é a cabeça tá agora o 10 é o topo da pilha como nós vamos fazer numa desencadeada da mesma forma nós vamos ao locar o 10 numa região qualquer de memória tá coloca ele em qualquer lugar depois como nós dialogamos dele nós temos o ponteiro para ele nós fazemos nós estamos olha 10 agora você vai ter que guardar a

posição de demora do elemento 35 porque porque se eu desempilhar você eu vou querer que eu 35 fique no topo da pilha então nós colocamos ele numa região qualquer de memória e nem é de nós colocamos um endereço de memória dizendo onde está o 35 e daí nós não precisamos mais apontar para o 35 então Quebra esse link bem aqui então o que que é a minha filha a minha filha é um ponteiro para o elemento dessa em algum lugar da memória só que é um ponteiro mesmo ele aponta para uma região de memória e

o alimento 10 tem um ponteiro para o elemento 35 uma forma melhor de se pensar e dessa forma que eu só mudei ele de lado só para ficar próximo da minha ordem lógica a e na hora de inserir mais elementos por exemplo 94 12:45 no vetor eu só garantia que eu sabia quem era esse alimento aqui que basicamente era lente de aulas anteriores então se eu quero dar um peixe eu coloco depois desse se eu quero dar um copo eu sei que o pop é nele que eu daria um Pop Então pode significaria olha remove

ele e agora a cabeça da pilha era o que estava antes dele então a gente só precisava saber quem era o número de Quantos elementos eu tinha na minha filha como funciona aqui a inserção do 9412 45 Se eu quero receber um 94 ele vai ficar do lado do 10 então eu vou colocar ele em qualquer lugar de memória 94 e depois eu vou fazer um 94 a contato para o Dash e e se agora eu quisesse o 12 o 12 vai ficar do lado 94 eu vou colocar ele qualquer lugar de memória e ele

vai apontar para 94 e no final 4545 a mesma coisa coloca de qualquer lugar de memória e faça ele apontar para doce então esse daqui são a ordem dos apontamentos bom e o que é que eu guardo realmente eu só guardo o ponteiro por 45 é tudo que eu preciso o resto são eles que se encadeiam por quê Porque se eu quiser remover um elemento Onde está o elemento que eu quero remover ele já tá na cabeça aqui da minha filha já tá no topo é o 45 eu consigo achar esse elemento em tempo constante

para inserir significa o que coloca em qualquer lugar de memória EA ponte para cá tempo constante para remover e já tá aqui no tô é move então tempo constante bom então conta do IBOPE o que que simplesmente eu faço eu removo ele ele já tinha um ponteiro para o próximo e tenho só atualiza esse ponteiro para também apontar pros Se eu der um top de novo eu já tem um ponteiro para cá por remover ele e eu já tinha um ponteiro dele para outro canto que eu só faço apontar para esse outro canto e assim

por diante bom e com filas como é que eu faço com filas ele tem o primeiro lembrar o que que eram as filas era uma estrutura que o primeiro elemento a entrar será o primeiro a sair ou seja se Pedro enviou um documento antes de Paulo para impressora então documento de Pedro tem que ser empréstimo antes do documento pipoca inserções emoções novamente tem que ser feita sem tempo constantes por quê Porque ela que eu já conseguia com vetor bom então vamos lá ver se lado esquerdo aqui eu tenho que a gente viu em aulas anteriores

nesse lado direito é a nossa estrutura de agora anteriormente nós tínhamos duas variáveis inteiras que apontavam para o índice da frente e para o índice de trás aqui nós vamos substituir essas duas variáveis por dois ponteiros que vão apontar para região de memória Onde está o elemento da frente e para região de memória Onde está o elemento de trás ou seja no início elas vão estar apontando para o mesmo lugar porque porque só tem um elemento aqui o chão e seria o elemento 10 o ponteiro que estava apontando para frente vai continuar apontando para frente

só que a gente vai pegar esse elemento esse ponteiro e vai dizer olha agora você vai apontar para outro elemento e esse outro elemento vai ser o elemento de trás e nós vamos precisar de um ponteiro para o elemento de trás porque porque se a gente não tiver um ponteiro para o elemento de trás nós não vamos conseguir fazer com que a infecção seja em tempo constante bom então nós precisamos um ponteiro por de trás para poder fazer a inserção e nós vamos precisar de um ponteiro para o da frente para poder fazer a remoção

do elemento eu tô na hora de inserir o que é que eu faço para se eu quero inserir por exemplo 94 eu ensino usando o ponteiro que tá apontando para elemento de trás tá contando por laranjinha então eu vou pegar colocaram 94 de uma região qualquer de memória como eu já estou apontando para cá eu digo olha agora você não está apontando para ninguém vai apontar para 94 tá E esse ponteiro que antes estava contando por 10 ele vai apontar agora para cá porque porque eventualmente eu vou precisar saber quem é que tá no final

da fila para exterior outros elementos que é o que ocorreu por exemplo quando aqui seria o dobro coloquei um doce uma região qualquer de memória como eu já tenho um ponteiro para 94 acesso em tempo constante de Glória ponte para o doso e daí eu digo agora o 94 não é mais o fim da fila tem esse ponteiro vai deixar de apontar para cá e vai apontar agora para o doce e na hora de remover na hora de remover eu uso ela o ponteiro Estava contando para frente que era o ponteiro que estava apontando por

exemplo por 35 e eu digo Olha eu não quero mais você 35 Então vou apagar o 35 e volto a dizer Esse ponteiro aqui para onde para onde eu 35 apontado eu consigo obter esse tempo constante Então na hora de remover Eu uso esse ponteiro aqui por exemplo remover o teste significa simplesmente a apontar por 94 que eu já tinha o tempo constante para remover então eu uso da frente para inserir Eu uso o de trás e é isso basicamente que a gente tem que ter em mente nas próximas aulas que nós vamos fazer estas

implementações em Sistemas mas só que antes de fazer as implementações você precisa entender exatamente como como elas funcionam antes Claro de inserir a sua primeira linha de pode tá e tenha ficado claro esses conceitos aqui de listas encadeadas caso não tenha ficado claro como eu sempre digo assistir essa aula de novo antes de prosseguir para a próxima então nós vemos na próxima aula um forte abraço e até mais é E aí [Música]