Inserção e Remoção em Listas Encadeadas em Python | Estruturas de Dados #6

Подписаться 203 тыс.

Просмотров 14 тыс.

50% 1

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: pgdinamica@brunch.ag
- Demais assuntos: contato@programacaodinamica.com.br
👩🏾‍💻👨🏾‍💻 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 RU-vid, considere nos apoiar se tornando membro do canal: www.youtube.co...

Опубликовано:

1 окт 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 57

@dianacodes 5 лет назад

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

@pgdinamica 5 лет назад

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

@paulastefany7048 10 месяцев назад

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

@dionneysaraiva2489 2 года назад

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 2 года назад

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

@pedrohenrique-f8v4z 3 месяца назад

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

@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")

@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

@theo_riveroooo 3 года назад

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

@arturcorreia6615 4 года назад

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 3 года назад

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

@ruinascimento501 4 года назад

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 4 года назад

POO tem aqui: ru-vid.com/group/PL5TJqBvpXQv60f8_yh-fg1uJptnA8ZDNV :) e grafos está sendo providenciado \o/

@brunogorini4838 6 лет назад

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

@pgdinamica 6 лет назад

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!

@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 4 месяца назад

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

@caiokx1337 5 лет назад

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

@pgdinamica 5 лет назад

Obrigado, @Hastingo!

@kauerichardy2394 Год назад

vapo

@jubilanda98 4 года назад

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 4 года назад

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 4 года назад

@@pgdinamica Muito obrigada!

@fernandobandeirademellomat7711 3 года назад

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 3 года назад

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

@thiagofelippi5969 4 года назад

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 4 года назад

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

@sdmastergames4905 4 года назад

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 4 года назад

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!

@fabioleonam 4 года назад

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 4 года назад

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.

@alextrevis3608 4 года назад

ótimo conteúdo!!!

@pgdinamica 3 года назад

Obrigado!

@Trash611 2 года назад

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 2 года назад

É 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 2 года назад

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

@danilodasilvarocha3792 3 года назад

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

@pgdinamica 3 года назад

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.

@raniel0511 3 года назад

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

@pgdinamica 3 года назад

Que ótimo!

@zaqueudovale852 4 года назад

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 4 года назад

Show demais!

@zaqueudovale852 4 года назад

@@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!

@kauanphbbb 3 года назад

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

@pgdinamica 3 года назад

Bons estudos! 🚀

@paulastefany7048 10 месяцев назад

Que aulaaa😆💛💛💛

@thepurplemug 3 года назад

Thank you! You saved my life!!

@pgdinamica 3 года назад

You're welcome!

@TheElkabong 5 лет назад

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 zarodasilva@gmail.com. Valeu.

@Linkk2011 Год назад

sensacional, parabéns pela didática, sensei

@pgdinamica Год назад

Obrigado! Bons estudos!

@C3L3ST1C 5 лет назад

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

@pgdinamica 5 лет назад

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 5 лет назад

@@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 5 лет назад

@@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 5 лет назад

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