Inserção e Remoção em Listas Encadeadas em Python | Estruturas de Dados #6

Uma lista encadeada é uma estrutura de dados linear, porém com alocação em memória não sequencial. Isto quer dizer que, diferentemente do que acontece em uma lista comum, elementos em posições consecutivas na lista não necessariamente estarão armazenados em espaços de memória contíguo. Por conta disso, não é possível fazer acesso aleatório a uma posição de memória diretamente a partir de um índice como lista[3], por exemplo.
▶️Se você não tem experiência com Python, mas gostaria de aprender a programar e desenvolver uma base sólida de programação usando esta linguagem, confira o nosso curso Python do Jeito Certo: vai.pgdinamica...
Para construir uma lista encadeada, utilizamos uma estrutura auxiliar chamada "nó", que serve para encapsular o dado que queremos armazenar e também uma referência para outro nó. Assim, conseguimos criar uma lista encadeada unindo nós tal como elos de uma corrente, em que um nós aponta para o nó seguinte. Com esta ideia, podemos alcançar qualquer elemento da lista apenas guardando uma referência para o primeiro nó e seguindo para o próximo nó quantas vezes forem necessárias.
Neste vídeo, prosseguimos a implementação da nossa lista encadeada escrevendo os métodos de inserção e remoção de elementos na lista.
*Código do vídeo: github.com/pyt...
▶️ Acompanhe o curso de estrutura de dados nesta playlist: • Estrutura de Dados
▶️ Confira também a playlist sobre Análise e Projeto de Algoritmos: • Análise e Projeto de A...
📚 Livros de Algoritmos e Estruturas de Dados: amzn.to/3d5wK4m
📚 Livros recomendados de Data Science: amzn.to/2XZyxUr
🎥 SetUp - Equipamentos: amzn.to/37Cg3N2
🟣 Canal na Twitch para lives: / pgdinamica
🟦 Canal do Telegram para receber os vídeos: t.me/joinchat/...
✉️ E-mails:
- Propostas comerciais: [e-mail]
- Demais assuntos: [e-mail]
👩🏾‍💻👨🏾‍💻 Confira mais conteúdo em nosso blog: blog.programac...
🔥 Faça parte da comunidade gratuita Programação Mais Dinâmica: bit.ly/pgsparkle (baixe o app e entre na comunidade)
📸 Nos siga no Instagram: / pgdinamica
📸 @kizzy_terra @hallpaz
🐦 Nos siga no Twitter: / pgdinamica
🐦 @kizzy_terra @hallpaz
⚠️ Python Café agora é Programação Dinâmica! :D
* Curta a Programação Dinâmica no facebook: pgdinamica
* Nosso repositório no Github: github.com/programacaodinamica
* Confira o nosso Medium: medium.com/programacaodinamica
* Confira os artigos no Python Café: pythoncafe.com.br
🥰 Se você gosta do nosso trabalho e acha relevante a nossa atuação no KZbin, considere nos apoiar se tornando membro do canal: www.youtube.co...

[@dianacodes]

gente, como vim parar aqui??? MUITO OBRIGADA KZbin, me recomendou um deus do Python pra me explicar estrutura de dados !!!

[@pgdinamica]

hahaha, vou retomar essa série. Vai vir a parte mais legal...

[@dionneysaraiva2489]

Cara, vou maratonar nos seus vídeos. Esse tipo de conteúdo é muito difícil achar com qualidade e é super necessário entender o que acontece debaixo dos panos no processamento. Parabéns, continue fazendo mais conteúdo desse tipo.

[@pgdinamica]

Bom ver gente disposta a aprender como você, Dionney! Bons estudos 🙌🏾

[@user-om1dr2re7l]

fiz a função "remove" de um jeito diferente, invertendo o processo da função "insirt": def remove(self, index): if self._size == 1: self.head = None self._size = 0 elif self._size == 0: raise IndexError("Lista vazia") else: pointer = self._getnode(index-1) node = pointer.next pointer.next = node.next self._size -= 1

[@caiokx1337]

Obrigado irmao, me ajudou muito! A aula foi excelente!

[@pgdinamica]

Obrigado, @Hastingo!

[@paulastefany7048]

Professor, no bloco else do insert não é necessário um If pointer após pointer= self._getnode(Index - 1) ?

[@thepurplemug]

Thank you! You saved my life!!

[@pgdinamica]

You're welcome!

[@VivianneLopes-es5kc]

Um dúvida na função getnode. O ponteiro fica em cima do último elemento caso que queira modificar ou exibir um elemento específico em uma posição fora do index?

[@VivianneLopes-es5kc]

Acabei de descobrir pelo python tutor que não, ele fica no None

[@Linkk2011]

sensacional, parabéns pela didática, sensei

[@pgdinamica]

Obrigado! Bons estudos!

[@alextrevis3608]

ótimo conteúdo!!!

[@pgdinamica]

Obrigado!

[@thiagofelippi5969]

Muito bom o conteúdo! Como auto ditada acabei passando batido por algoritmos e estrutura de dados, agora que estou sentindo que estou evoluindo senti que precisava me aprofundar

[@pgdinamica]

Show! É sempre bom ver pessoas como você, que estão constantemente buscando evoluir. Sucesso!

[@ruinascimento501]

Aula muito boa! válido ressaltar que um curso de POO em python seria muito bem vindo assim como implementação das estruturas: Lista duplamente encadeada e grafos. Sucesso e abs. obs: Muito bom seus conteúdos. Parabéns.

[@pgdinamica]

POO tem aqui: kzbin.info/aero/PL5TJqBvpXQv60f8_yh-fg1uJptnA8ZDNV :) e grafos está sendo providenciado \o/

[@paulastefany7048]

Que aulaaa😆💛💛💛

[@anadotie6618]

Tentei fazer a def de remoção de elemento sem assistir ao vídeo e reparei que a minha ficou diferente(no meu caso quis deletar por uma posição da lista e não por valor), poderia me dizer se está certo?(OBS: como ainda não sei nada sobre lançar e tratar erros usei print para dizer que há um erro) def delete(self, index): #usado para deletar um elemento especifico da lista if self.head: pointer = self.head if index == 0: node = pointer.next self.head = node else: for i in range(index - 1): if pointer: pointer = pointer.next else: print("List index out of range!") node = pointer.next pointer.next = node.next else: print("List index out of range")

[@theo_riveroooo]

Fiz essa funçãozinha e funcionou, quer quiser usar: def drop_by_index(self, index): if index == 0: self.head = self.head.next else: pointer = self._getnode(index-1) pointer.next = pointer.next.next self._size -= 1

[@VivianneLopes-es5kc]

Eu vi esse vídeo há uns meses atrás e não entendi tão bem, hj eu entendo bem mais mas ainda sinto que n tenho uma compreenção 100% de tudo. Vou seguir tentando kkkk

[@chinfoplaya]

eu tbm kkkkk é assim mesmo, tem que ir praticando até assimilar 100%

[@kauanphbbb]

Estava meio perdido sobre como fazer um fifo na prova da facul, teu vídeo me ajudou bastante, valeu

[@pgdinamica]

Bons estudos! 🚀

[@kauerichardy2394]

vapo

[@brunogorini4838]

Onde está o link com os códigos vistos na aula? rs

[@pgdinamica]

Fala, Bruno! Atualizei a descrição do vídeo com os códigos. Acabei esquecendo na hora de postar, peço desculpas e agradeço pelo comentário! Abraço!

[@raniel0511]

Assistido✔️ No começo assusta, mas depois que entende um pouco os conceitos dá pra ler e interpretar tudinho.

[@pgdinamica]

Que ótimo!

[@arturcorreia6615]

Oi, to com um problema, quando fui tentar rodar o programa, ele diz que "from" não tem suporte na versão do programa :(

[@moisessouza6665]

pode se o interpretador verifica qual é a versão ou se estiver no vscode tem que configurar bem o ambiente

[@fabioleonam]

No minuto 14:32 a linha "node.next = pointer.next". Isso significa que o novo nó que estamos inserindo na lista está apontando para o mesmo lugar que o pointer?

[@pgdinamica]

Não...significa que o novo nó aponta para o sucessor do pointer. Queremos inserir o node na posição "index"; daí, encontramos quem ocupa a posição index-1, representado pela variável pointer, e vamos inserir o **node** ENTRE o pointer e seu sucessor.

[@Trash611]

Professor boa tarde, qual a diferença entre o self.head.data para self.head no if self.head.data == elem: cheguei a pensar que o .data referencia o valor que esta na posição do nó, já o .head só é a posição da cabeça da lista, seria isso ?

[@pgdinamica]

É isso mesmo. self.head é o "nó" que representa a cabeça da lista, enquanto self.head.data é o valor do nó que representa a cabeça da lista. Precisamos envolver o dado, o valor, que queremos armazenar em uma estrutura chamada "nó" (node), para conseguirmos ligá-los.

[@Trash611]

@@pgdinamica muito obrigado por tirar a dúvida, me ajudou muito

[@danilodasilvarocha3792]

Caso em uma lista tenha elementos repetidos, seria possível selecionar um index específico e remover esse elemento?

[@pgdinamica]

Você não pode fazer acesso aleatório (ir direto a um índice) em listas encadeadas. Para remover elementos duplicados, você teria que percorrer a lista de um nó a outro como no algoritmo de remoção do vídeo.

[@jubilanda98]

Boa noite professor, tudo bem? Provavelmente fiz algo errado mas quando fiz o teste pra remover um item da lista que não existia ele continuava retornando "True". Você sabe me dizer qual seria o erro? Se alguma pessoa nos comentarios também souber, sua ajuda sera bem vinda :) def remove(self, elem): if self.head == None: raise ValueError(f'{elem} is not in list') elif self.head.data == elem: self.head = self.head.next self._size = self._size - 1 else: ancestor = self.head pointer = self.head.next while(pointer): if pointer.data == elem: ancestor.next = pointer.next pointer.next = None ancestor = pointer pointer = pointer.next self._size = self._size - 1 return True raise ValueError(f'{elem} is not in list')

[@pgdinamica]

O seu "return True" é executado depois do "while", independentemente de ter encontrado o elemento. Para que ele seja executado *apenas* quando o elemento for encontrado na lista, ele deve ser a última instrução do escopo do "if": if pointer.data == elem: # SE ENCONTROU ancestor.next = pointer.next pointer.next = None self._size = self._size - 1 #(só reduz o tamanho se encontro) return True # retorna True SE ENCONTROU A implementação completa fica neste repositório: github.com/python-cafe/data_structures/blob/master/listas_encadeadas/linkedlist.py

[@jubilanda98]

@@pgdinamica Muito obrigada!

[@sdmastergames4905]

Me Salvo Muito Nos Trabalhos da Faculdade, mas notei algo no código... Quando vc remove um elemento que n ta na lista o cod retorna true cm se tivesse removido, então eu olhei o código e fiquei pensando pq ele ta fzn isso sendo que era pra retorna false? ai que percebi o segundo Return True tava no fim do Else: então toda vez que ele saia do while ele retornava True, Resolvi colocando dentro do If mas n sei se é o jeito certo de resolver esse problema '-'

[@pgdinamica]

Oi @SD MasterGames, você está certo, obrigado pelo toque! Vou corrigir lá o código, o correto seria: "else: ancestor = self.head pointer = self.head.next while(pointer): if pointer.data == elem: ancestor.next = pointer.next pointer.next = None self._size = self._size - 1 return True ancestor = pointer pointer = pointer.next" Corrigido: github.com/python-cafe/data_structures/blob/master/listas_encadeadas/linkedlist.py Repara que essa solução não retorna "False", ela lança uma exceção (um erro), mas isso é uma decisão de projeto, você pode optar por retornar False nos casos em que não encontrar o elemento para remover. A questão é que quem for utilizar a lista vai ter que se lembrar sempre de verificar o valor de retorno da função, porque ela "falhará silenciosamente". Abraço!

[@fernandobandeirademellomat7711]

para o código de remover, não valeria a pena utilizar as funções _getnode() e index(), que já foram criadas? o meu código ficou assim (funciona perfeitamente): def remove(self, elem): if self.head.data == elem: self.head = self.head.next self._size -= 1 return current = self._getnode(self.index(elem)) prev = self._getnode(self.index(elem) - 1) prev.next = current.next self._size -= 1

[@pgdinamica]

Boa pergunta! O problema desta solução é que _getnode precisa internar até a posição desejada. Embora não mude a complexidade da solução, na prática, você está pagando um custo dobrado, que depende do tamanho da lista, pra encontrar esta posição

[@zaqueudovale852]

Muito bom! Fiz uma versão em JavaScript + P5.js: editor.p5js.org/ZaqueuCavalcante/sketches/Gnt3zd_1S Dá pra visualizar a lista a cada operação feita.

[@pgdinamica]

Show demais!

[@zaqueudovale852]

@@pgdinamica Valew! Pretendo implementar as principais Estruturas de Dados e Algoritmos (Busca e Ordenação pelo menos) nesse repo: github.com/ZaqueuCavalcante/Data-Structures Já ouviu falar da linguagem Processing? Ela têm versões baseadas em Java e em Python, dá pra fazer muita coisa visual com poucas linhas de código. Eu mesmo tô fazendo o clássico Snake Game nela, nesse repo: github.com/ZaqueuCavalcante/Snake-AI Seria show VER uma busca binária em árvore acontecendo passo a passo, fica a ideia... Sua didática é sensacional, muito obrigado por compartilhar seu conhecimento!

[@C3L3ST1C]

mano oq significa esse if __name__ == '__main__' ?

[@pgdinamica]

Fala, Bruno, excelente pergunta! Redigimos um pequeno artigo para contextualiza-la e respondê-la: medium.com/programacaodinamica/o-que-significa-if-name-main-4c167df45f58

[@C3L3ST1C]

@@pgdinamica Poo mano valeu, esclareceu minhas dúvidas, fiquei lisonjeado com a citação hahaha.., mano só uma perguntinha, tu tem alguma dica de como eu posso iniciar os estudos em machine learning, pois preciso apresentar um trabalho a respeito..

[@pgdinamica]

​@@C3L3ST1C Este curso: (pt.coursera.org/learn/machine-learning) tem uma abordagem didática e ampla da área, mas sem muito foco na matemática da coisa. Como introdução aos conceitos, é muito bom. Este aqui (developers.google.com/machine-learning/crash-course/ml-intro) é um material da Google para uma introdução rápida a partir do Tensorflow, o framework que eles desenvolveram para machine learning/deep learning.

[@C3L3ST1C]

@@pgdinamica Valeu mano, ta me ajudando bastante!!

[@TheElkabong]

Olá. Estou estudando python e me deparei com o problema: como elaborar um programa para listar e contar a quantidade de elementos repetidos numa lista. Se puder ajudar, agradeço bastante se mandar para [e-mail]. Valeu.