# Learn Linked Lists in 13 minutes 🔗 https://www.youtube.com/watch?v=N6dOwBde7-M Translation: pt-BR [00:00] hey what's going on everybody it's you Ei, o que está acontecendo todo mundo, é você [00:02] hey what's going on everybody it's you bro hope you're doing well Ei, o que está acontecendo todo mundo, é você, mano, espero que você esteja bem [00:03] bro hope you're doing well in this video we're going to discuss Mano, espero que você esteja bem, neste vídeo vamos discutir [00:05] in this video we're going to discuss linked lists and computer science Neste vídeo, vamos discutir listas ligadas e ciência da computação [00:06] linked lists and computer science so sit back relax and enjoy the show Listas ligadas e ciência da computação, então sente-se, relaxe e aproveite o show [00:11] now before we dive straight into linked Agora, antes de mergulharmos direto em linked [00:13] now before we dive straight into linked lists we're going to take a closer Agora, antes de mergulharmos direto em listas ligadas, vamos dar uma olhada mais de perto [00:14] lists we're going to take a closer examination of arrays and array lists we Listas, vamos fazer um exame mais detalhado de arrays e listas de arrays, nós [00:16] examination of arrays and array lists we will see what disadvantages that these Exame de arrays e listas de arrays, veremos quais desvantagens essas [00:19] will see what disadvantages that these data structures have Veremos quais desvantagens essas estruturas de dados têm [00:20] data structures have where linked lists excel at so we'll Estruturas de dados têm onde as listas ligadas se destacam, então nós vamos [00:22] where linked lists excel at so we'll compare and contrast the differences Onde listas ligadas se destacam, então vamos comparar e contrastar as diferenças [00:24] compare and contrast the differences between the two Comparar e contrastar as diferenças entre os dois [00:25] between the two with what we understand with arrays and Entre os dois com o que entendemos com arrays e [00:26] with what we understand with arrays and array lists these data structures store Com o que entendemos com arrays e listas de arrays, essas estruturas de dados armazenam [00:29] array lists these data structures store elements in contiguous memory locations Listas de arrays, essas estruturas de dados armazenam elementos em locais de memória contíguos [00:31] elements in contiguous memory locations in this demonstration i'm storing Elementos em locais de memória contíguos, nesta demonstração estou armazenando [00:33] in this demonstration i'm storing letters of the alphabet suppose that the Nesta demonstração, estou armazenando letras do alfabeto, suponha que o [00:35] letters of the alphabet suppose that the first element of my array has a memory Letras do alfabeto, suponha que o primeiro elemento do meu array tenha uma memória [00:37] first element of my array has a memory address of Primeiro elemento do meu array tem um endereço de memória de [00:38] address of one two three fake street obviously Endereço de uma duas três fake street, obviamente [00:40] one two three fake street obviously these are not real memory addresses but Uma duas três fake street, obviamente, estes não são endereços de memória reais, mas [00:41] these are not real memory addresses but this is how i like to think about things Estes não são endereços de memória reais, mas é assim que eu gosto de pensar nas coisas [00:43] this is how i like to think about things if this was a memory address then the É assim que eu gosto de pensar nas coisas, se este fosse um endereço de memória, então o [00:45] if this was a memory address then the next element in my array may have an Se este fosse um endereço de memória, então o próximo elemento no meu array pode ter um [00:47] next element in my array may have an address of Próximo elemento no meu array pode ter um endereço de [00:48] address of one two five fake street then one two Endereço de uma duas cinco fake street, então uma duas [00:51] one two five fake street then one two seven fake street Uma duas cinco fake street, então uma duas sete fake street [00:52] seven fake street one two nine fake street and then you Sete fake street, uma duas nove fake street e então você [00:53] one two nine fake street and then you just continue on in that pattern Uma duas nove fake street e então você continua nesse padrão [00:55] just continue on in that pattern now arrays are fantastic at randomly Continua nesse padrão, agora arrays são fantásticos em aleatoriamente [00:57] now arrays are fantastic at randomly accessing elements because they have an Agora arrays são fantásticos em acessar elementos aleatoriamente porque eles têm um [00:58] accessing elements because they have an index Acessar elementos porque eles têm um índice [00:59] index but they're not so great at inserting or Índice, mas eles não são tão bons em inserir ou [01:01] but they're not so great at inserting or deleting elements especially when those elements are closer to the beginning of the array. mas eles não são tão bons em inserir ou excluir elementos, especialmente quando esses elementos estão mais próximos do início do array. [01:04] Here's an example. Aqui está um exemplo. [01:05] Suppose I need to insert a new element at index 3. Suponha que eu precise inserir um novo elemento no índice 3. [01:09] Since this element is already occupied with a value, I would need to shift my elements to the right in order to accommodate room for this new element. Como este elemento já está ocupado com um valor, eu precisaria deslocar meus elementos para a direita para acomodar espaço para este novo elemento. [01:15] So the process of shifting is cumbersome. Portanto, o processo de deslocamento é complicado. [01:19] But once this element is empty, then I can insert a new value. Mas, uma vez que este elemento esteja vazio, então eu posso inserir um novo valor. [01:21] So it's not that big of a deal if I have a small data set. Portanto, não é um grande problema se eu tiver um pequeno conjunto de dados. [01:24] But imagine if I had 1 million elements, I will need to shift my data up to that many times depending on the location of the insertion. Mas imagine se eu tivesse 1 milhão de elementos, eu precisaria deslocar meus dados até tantas vezes, dependendo da localização da inserção. [01:33] And the same concept applies with deletion as well. E o mesmo conceito se aplica à exclusão também. [01:34] We would shift our elements to the left to close the gap. Deslocaríamos nossos elementos para a esquerda para fechar a lacuna. [01:39] You're probably thinking, dude, why are you talking about arrays in a video about linked lists? Você provavelmente está pensando, cara, por que você está falando sobre arrays em um vídeo sobre linked lists? [01:44] Well, where arrays have difficulty inserting and deleting, linked lists actually have the advantage. Bem, onde arrays têm dificuldade em inserir e excluir, linked lists realmente têm a vantagem. [01:49] Here's a representation of a linked list. Aqui está uma representação de uma linked list. [01:51] A linked list is made up of a long chain of nodes. Uma linked list é composta por uma longa cadeia de nós. [01:53] Each node contains two parts: some data that we need to store and an address to the next node in line, also referred to as a pointer. Cada nó contém duas partes: alguns dados que precisamos armazenar e um endereço para o próximo nó na linha, também referido como um ponteiro. [02:02] also referred to as a pointer linked lists do not have an index the same way também referidos como ponteiros, listas ligadas não têm um índice da mesma forma [02:03] lists do not have an index the same way that arrays do listas não têm um índice da mesma forma que os arrays [02:04] that arrays do but each node contains an address to os arrays têm, mas cada nó contém um endereço para [02:06] but each node contains an address to where the next node is located mas cada nó contém um endereço para onde o próximo nó está localizado [02:08] where the next node is located so these nodes are non-contiguous they onde o próximo nó está localizado, então esses nós são não contíguos, eles [02:10] so these nodes are non-contiguous they can really be anywhere within your então esses nós são não contíguos, eles podem realmente estar em qualquer lugar dentro do seu [02:12] can really be anywhere within your computer's memory podem realmente estar em qualquer lugar dentro da memória do seu computador [02:13] computer's memory if our initial node has a memory address memória do computador, se o nosso nó inicial tiver um endereço de memória [02:15] if our initial node has a memory address of one two three fake street se o nosso nó inicial tiver um endereço de memória de um dois três rua falsa [02:17] of one two three fake street like our array example then the next de um dois três rua falsa, como nosso exemplo de array, então o próximo [02:19] like our array example then the next node in our linked list could have a como nosso exemplo de array, então o próximo nó em nossa lista ligada poderia ter um [02:21] node in our linked list could have a memory address of maybe nó em nossa lista ligada poderia ter um endereço de memória de talvez [02:23] memory address of maybe 101 help boulevard and another could be endereço de memória de talvez 101 Help Boulevard e outro poderia ser [02:26] 101 help boulevard and another could be 404 101 Help Boulevard e outro poderia ser 404 [02:26] 404 nowhere lane then 666 crime circle 404 Nowhere Lane, então 666 Crime Circle [02:30] nowhere lane then 666 crime circle each node knows where the next node Nowhere Lane, então 666 Crime Circle, cada nó sabe onde o próximo nó [02:31] each node knows where the next node resides i imagine this as if we're cada nó sabe onde o próximo nó reside, eu imagino isso como se estivéssemos [02:33] resides i imagine this as if we're following a scavenger hunt or reside, eu imagino isso como se estivéssemos seguindo uma caça ao tesouro ou [02:35] following a scavenger hunt or a series of clues to find the end of the seguindo uma caça ao tesouro ou uma série de pistas para encontrar o fim da [02:37] a series of clues to find the end of the linked list uma série de pistas para encontrar o fim da lista ligada [02:38] linked list the tale each node has an address a clue lista ligada, a cauda, cada nó tem um endereço, uma pista [02:41] the tale each node has an address a clue as to where the next note is we begin at a cauda, cada nó tem um endereço, uma pista de onde a próxima nota está, começamos em [02:43] as to where the next note is we begin at the head and work our way de onde a próxima nota está, começamos na cabeça e seguimos nosso caminho [02:45] the head and work our way towards the tail following each clue a cabeça e seguimos nosso caminho em direção à cauda, seguindo cada pista [02:47] towards the tail following each clue each memory address found in each node em direção à cauda, seguindo cada pista, cada endereço de memória encontrado em cada nó [02:49] each memory address found in each node then we know when we reach the end of cada endereço de memória encontrado em cada nó, então sabemos quando chegamos ao fim da [02:51] then we know when we reach the end of our linked list when we check that então sabemos quando chegamos ao fim da nossa lista ligada quando verificamos que [02:53] our linked list when we check that address nossa lista ligada quando verificamos esse endereço [02:53] address our pointer and it has a value of null endereço, nosso ponteiro, e ele tem um valor nulo [02:56] our pointer and it has a value of null that means we're at the tail we're at nosso ponteiro e ele tem um valor nulo, isso significa que estamos na cauda, estamos em [02:57] that means we're at the tail we're at the end of our linked list isso significa que estamos na cauda, estamos no fim da nossa lista ligada [02:58] the end of our linked list inserting a node is easy in a linked o fim da nossa lista ligada, inserir um nó é fácil em uma ligação [03:00] inserting a node is easy in a linked list there's no shifting of elements inserir um nó é fácil em uma lista ligada, não há deslocamento de elementos [03:01] list there's no shifting of elements involved wherever we need to place a new lista, não há deslocamento de elementos envolvido, onde quer que precisemos colocar um novo [03:04] involved wherever we need to place a new node we take the address stored in the node. envolvido onde quer que precisemos colocar um novo nó, pegamos o endereço armazenado no nó. [03:06] we take the address stored in the previous node. pegamos o endereço armazenado no nó anterior. [03:07] previous node and assign the address of our new node. nó anterior e atribuímos o endereço do nosso novo nó. [03:09] and assign the address of our new node with the address from the previous node. e atribuímos o endereço do nosso novo nó com o endereço do nó anterior. [03:12] with the address from the previous node so that our new node is pointing to the next node in line. com o endereço do nó anterior para que nosso novo nó aponte para o próximo nó na linha. [03:14] so that our new node is pointing to the next node in line. para que nosso novo nó aponte para o próximo nó na linha. [03:15] next node in line then we can take and replace the address. próximo nó na linha, então podemos pegar e substituir o endereço. [03:17] then we can take and replace the address in the previous node. então podemos pegar e substituir o endereço no nó anterior. [03:19] in the previous node with an address that points to our new node. no nó anterior com um endereço que aponte para o nosso novo nó. [03:20] with an address that points to our new node it's as simple as that and we're completing our chain. com um endereço que aponte para o nosso novo nó, é tão simples quanto isso e estamos completando nossa cadeia. [03:22] node it's as simple as that and we're completing our chain. nó, é tão simples quanto isso e estamos completando nossa cadeia. [03:23] completing our chain simply by inserting a node at a given location. completando nossa cadeia simplesmente inserindo um nó em um determinado local. [03:25] simply by inserting a node at a given location there's only a few steps involved. simplesmente inserindo um nó em um determinado local, há apenas alguns passos envolvidos. [03:27] location there's only a few steps involved no shifting of elements required. local, há apenas alguns passos envolvidos, nenhuma movimentação de elementos necessária. [03:29] involved no shifting of elements required deleting nodes are easy too. envolvida, nenhuma movimentação de elementos necessária, excluir nós também é fácil. [03:31] required deleting nodes are easy too wherever we need to delete a node we have the previous node. necessária, excluir nós também é fácil, onde quer que precisemos excluir um nó, temos o nó anterior. [03:32] wherever we need to delete a node we have the previous node point instead to the next node in line. onde quer que precisemos excluir um nó, fazemos o nó anterior apontar em vez disso para o próximo nó na linha. [03:34] have the previous node point instead to the next node in line. o nó anterior apontar em vez disso para o próximo nó na linha. [03:36] point instead to the next node in line again no shifting of elements is necessary. apontar em vez disso para o próximo nó na linha novamente, nenhuma movimentação de elementos é necessária. [03:37] again no shifting of elements is necessary. novamente nenhuma movimentação de elementos é necessária. [03:38] necessary now this is where linked lists tend to be inferior to arrays. necessário, agora é aqui que as listas ligadas tendem a ser inferiores aos arrays. [03:40] now this is where linked lists tend to be inferior to arrays. agora é aqui que as listas ligadas tendem a ser inferiores aos arrays. [03:41] be inferior to arrays they are bad at searching we can randomly access an element of an array. ser inferiores aos arrays, elas são ruins em busca, podemos acessar aleatoriamente um elemento de um array. [03:43] they are bad at searching we can randomly access an element of an array. elas são ruins em busca, podemos acessar aleatoriamente um elemento de um array. [03:45] randomly access an element of an array because we have an index with a linked list that is not the case. acessar aleatoriamente um elemento de um array porque temos um índice com uma lista ligada que não é o caso. [03:46] because we have an index with a linked list that is not the case. porque temos um índice com uma lista ligada que não é o caso. [03:48] index with a linked list that is not the case to locate an element we need to begin at the head. índice com uma lista ligada que não é o caso, para localizar um elemento precisamos começar pela cabeça. [03:50] case to locate an element we need to begin at the head. caso, para localizar um elemento precisamos começar pela cabeça. [03:51] begin at the head and work our way towards the tail until we find the element that we are looking for. começar pela cabeça e trabalhar em direção à cauda até encontrarmos o elemento que estamos procurando. [03:53] and work our way towards the tail until we find the element that we are looking for. e trabalhar em direção à cauda até encontrarmos o elemento que estamos procurando. [03:55] we find the element that we are looking for. encontrarmos o elemento que estamos procurando. [03:55] for this itself takes time in fact it would take linear time but making the insertion or deletion of a node is constant. para isso em si leva tempo, de fato, levaria tempo linear, mas tornar a inserção ou exclusão de um nó é constante. [03:57] this itself takes time in fact it would take linear time but making the insertion or deletion of a node is constant. isso em si leva tempo, de fato, levaria tempo linear, mas tornar a inserção ou exclusão de um nó é constante. [03:59] take linear time but making the insertion or deletion of a node is constant. levar tempo linear, mas tornar a inserção ou exclusão de um nó é constante. [04:00] insertion or deletion of a node is constant this variation of a linked list is a singly linked list. inserção ou exclusão de um nó é constante, esta variação de uma lista ligada é uma lista ligada simplesmente. [04:02] or deletion of a node is constant this variation of a linked list is a singly linked list. ou exclusão de um nó é constante, esta variação de uma lista ligada é uma lista ligada simplesmente. [04:03] variation of a linked list is a singly linked list there are single. variação de uma lista ligada é uma lista ligada simplesmente, existem single. [04:06] is a singly linked list there are single links to each node. é uma lista ligada simples, existem links únicos para cada nó. [04:08] links to each node however there's another variation called. links para cada nó, no entanto, existe outra variação chamada. [04:10] however there's another variation called a doubly linked list. no entanto, existe outra variação chamada lista duplamente ligada. [04:11] a doubly linked list a doubly linked list requires even more. uma lista duplamente ligada, uma lista duplamente ligada requer ainda mais. [04:13] a doubly linked list requires even more memory to store two addresses in each. uma lista duplamente ligada requer ainda mais memória para armazenar dois endereços em cada. [04:16] memory to store two addresses in each node not just one which is the case with. memória para armazenar dois endereços em cada nó, não apenas um, que é o caso de. [04:18] node not just one which is the case with a. nó, não apenas um, que é o caso de uma. [04:18] a singly linked list one address for the. uma lista ligada simples, um endereço para o. [04:20] singly linked list one address for the next node and another for the previous. lista ligada simples, um endereço para o próximo nó e outro para o anterior. [04:22] next node and another for the previous node in our chain. próximo nó e outro para o nó anterior em nossa cadeia. [04:23] node in our chain the benefit of a doubly linked list is. nó em nossa cadeia, o benefício de uma lista duplamente ligada é. [04:25] the benefit of a doubly linked list is that we can traverse our doubly linked. o benefício de uma lista duplamente ligada é que podemos percorrer nossa lista duplamente ligada. [04:27] that we can traverse our doubly linked list. que podemos percorrer nossa lista duplamente ligada. [04:28] list from head to tail or from tail to head. lista da cabeça para a cauda ou da cauda para a cabeça. [04:30] from head to tail or from tail to head in reverse. da cabeça para a cauda ou da cauda para a cabeça, ao contrário. [04:31] in reverse each node knows where the next and. ao contrário, cada nó sabe onde o próximo e. [04:33] each node knows where the next and previous note is. cada nó sabe onde está o próximo e o nó anterior. [04:34] previous note is but the downside is that a doubly linked. nó anterior está, mas a desvantagem é que uma duplamente ligada. [04:37] but the downside is that a doubly linked list uses even more memory than a singly. mas a desvantagem é que uma lista duplamente ligada usa ainda mais memória do que uma simplesmente. [04:39] list uses even more memory than a singly linked list. lista usa ainda mais memória do que uma lista ligada simples. [04:40] linked list so how about we create a linked list in. lista ligada, então que tal criarmos uma lista ligada em. [04:42] so how about we create a linked list in real life now let's do it. então que tal criarmos uma lista ligada na vida real agora, vamos fazer isso. [04:43] real life now let's do it all right ladies and gentlemen with all. vida real agora, vamos fazer isso. Tudo bem, senhoras e senhores, com tudo. [04:45] all right ladies and gentlemen with all that out of the way let's create a. tudo bem, senhoras e senhores, com tudo isso fora do caminho, vamos criar uma. [04:46] that out of the way let's create a linked list. isso fora do caminho, vamos criar uma lista ligada. [04:47] linked list linked list list the data type of the. lista ligada, lista ligada, lista, o tipo de dado do. [04:50] linked list list the data type of the objects we'll be storing within this. lista ligada, lista, o tipo de dado dos objetos que armazenaremos nesta. [04:51] objects we'll be storing within this linked list. objetos que armazenaremos nesta lista ligada. [04:52] linked list just strings because they're easy and i. lista ligada, apenas strings porque são fáceis e eu. [04:54] just strings because they're easy and i will name this linked list. apenas strings porque são fáceis e eu nomearei esta lista ligada. [04:55] will name this linked list linked list linked list equals new. nomearei esta lista ligada, lista ligada, lista ligada igual a novo. [04:58] linked list linked list equals new linked. lista ligada, lista ligada igual a nova ligada. [04:59] linked list and list the data type again we are. lista ligada e lista o tipo de dado novamente estamos. [05:01] list and list the data type again we are storing strings at a constructor boom. lista e lista o tipo de dado novamente estamos armazenando strings em um construtor, boom. [05:03] storing strings at a constructor boom you got yourself a linked list. armazenando strings em um construtor, boom, você tem uma lista ligada. [05:04] you got yourself a linked list now if i was to take my cursor and hover. você tem uma lista ligada, agora se eu pegasse meu cursor e passasse o mouse. [05:06] Now if I was to take my cursor and hover over my linked list declaration. Agora, se eu fosse pegar meu cursor e passar sobre a declaração da minha lista ligada. [05:08] Over my linked list declaration, there's a note here that says this is a doubly linked list. Sobre a declaração da minha lista ligada, há uma nota aqui que diz que esta é uma lista duplamente ligada. [05:11] There's a note here that says this is a doubly linked list. Há uma nota aqui que diz que esta é uma lista duplamente ligada. [05:12] Each node knows where the previous and next nodes are. Cada nó sabe onde os nós anterior e próximo estão. [05:14] List, each node knows where the previous and next nodes are. Lista, cada nó sabe onde os nós anterior e próximo estão. [05:15] And next nodes are. E os nós próximos estão. [05:17] Now if we head to the linked list class itself, there's a few things I need to mention here. Agora, se formos para a própria classe de lista ligada, há algumas coisas que preciso mencionar aqui. [05:19] List class itself, there's a few things I need to mention here. Classe da lista em si, há algumas coisas que preciso mencionar aqui. [05:20] Need to mention here. Preciso mencionar aqui. [05:22] Our linked list stores the memory location of our first and last nodes. Nossa lista ligada armazena a localização na memória de nossos primeiro e último nós. [05:25] Location of our first and last nodes. Localização de nossos primeiro e último nós. [05:27] These are effectively the head and the tail of our linked list. Estes são efetivamente a cabeça e a cauda de nossa lista ligada. [05:28] Tail of our linked list. Cauda de nossa lista ligada. [05:30] And there's also an inner class named node. E também há uma classe interna chamada nó. [05:31] Node. Nó. [05:34] Each node knows the memory address of the next and previous nodes within this linked list. Cada nó conhece o endereço de memória dos nós próximo e anterior dentro desta lista ligada. [05:36] Previous nodes within this linked list. Nós anteriores dentro desta lista ligada. [05:38] Now taking a look at our linked list class definition. Agora, dando uma olhada na definição da nossa classe de lista ligada. [05:40] Class definition. Definição da classe. [05:43] Our linked list class implements the deck interface, and a deck is more or less a double ended queue. Nossa classe de lista ligada implementa a interface deck, e um deck é mais ou menos uma fila de duas pontas. [05:45] Is more or less a double ended queue. É mais ou menos uma fila de duas pontas. [05:48] So with the deck interface, we implement 12 additional methods. Portanto, com a interface deck, implementamos 12 métodos adicionais. [05:50] 12 additional methods. 12 métodos adicionais. [05:52] So here's just a few of them. Então, aqui estão apenas alguns deles. [05:53] So we can add to the head, add to the tail, remove the head, remove the tail. Então podemos adicionar à cabeça, adicionar à cauda, remover a cabeça, remover a cauda. [05:55] Add to the tail, remove the head, remove the tail. Adicionar à cauda, remover a cabeça, remover a cauda. [05:56] The tail, peek at the head, peek at the tail. A cauda, espiar a cabeça, espiar a cauda. [05:58] Peek at the head, peek at the tail. Espiar a cabeça, espiar a cauda. [06:00] Some will throw exceptions, some will return a special value. Alguns lançarão exceções, alguns retornarão um valor especial. [06:01] Special value. Valor especial. [06:03] So you can use any combination of these really. Então você pode usar qualquer combinação destes, realmente. [06:05] Really. Realmente. [06:05] And not only do we have these 12 methods, but we can treat our linked list. E não só temos estes 12 métodos, mas podemos tratar nossa lista ligada. [06:07] methods but we can treat our linked list as either a stack or a queue we can push métodos, mas podemos tratar nossa lista ligada como uma pilha ou uma fila, podemos adicionar [06:09] as either a stack or a queue we can push we can pop we can pull then we can offer como uma pilha ou uma fila, podemos adicionar, podemos remover, podemos puxar, então podemos oferecer [06:11] we can pop we can pull then we can offer so just to demonstrate let's first treat podemos remover, podemos puxar, então podemos oferecer, então, apenas para demonstrar, vamos primeiro tratar [06:13] so just to demonstrate let's first treat our linked list as a stack então, apenas para demonstrar, vamos primeiro tratar nossa lista ligada como uma pilha [06:15] our linked list as a stack so linked lists do have a push method as nossa lista ligada como uma pilha, então listas ligadas têm um método push também [06:18] so linked lists do have a push method as well if we need to então listas ligadas têm um método push também se precisarmos [06:19] well if we need to push an element onto our linked list as if it were a stack bem, se precisarmos adicionar um elemento à nossa lista ligada como se fosse uma pilha [06:21] push an element onto our linked list as if it were a stack adicionar um elemento à nossa lista ligada como se fosse uma pilha [06:23] if it were a stack so let's push the letter a and then i will display my linked list se fosse uma pilha, então vamos adicionar a letra a e então exibirei minha lista ligada [06:26] will display my linked list with a print line statement exibirei minha lista ligada com uma instrução de impressão [06:28] with a print line statement system.out.printline linked list com uma instrução de impressão system.out.printline linked list [06:30] system.out.printline linked list and of course we have the letter a so system.out.printline linked list e, claro, temos a letra a, então [06:32] and of course we have the letter a so let's push another letter onto our stack e, claro, temos a letra a, então vamos adicionar outra letra à nossa pilha [06:34] let's push another letter onto our stack what about b vamos adicionar outra letra à nossa pilha, que tal b [06:35] what about b so at the bottom of our linked list we have a and then on top we have b que tal b, então na parte inferior da nossa lista ligada temos a e então no topo temos b [06:39] have a and then on top we have b let's add a couple more letters let's represent a typical grading scale we temos a e então no topo temos b, vamos adicionar mais algumas letras, vamos representar uma escala de notas típica, nós [06:43] represent a typical grading scale we have c d and f a b c representamos uma escala de notas típica, temos c, d e f, a, b, c [06:47] c d and f a b c d f notice that i'm intentionally leaving out e we're going to insert that later c, d e f, a, b, c, d, f, note que estou intencionalmente deixando e de fora, vamos inseri-lo mais tarde [06:52] later so within our linked list that's behaving as a stack mais tarde, então dentro da nossa lista ligada que está se comportando como uma pilha [06:55] behaving as a stack we have f on top then d c b and a comportando-se como uma pilha, temos f no topo, depois d, c, b e a [06:59] we have f on top then d c b and a so we also have access to a pop method as well temos f no topo, depois d, c, b e a, então também temos acesso a um método pop [07:02] as well linked list dot pop and this will pop the top of my linked list so f should no também linked list ponto pop e isso removerá o topo da minha lista ligada, então f deveria não [07:08] top of my linked list so f should no longer be here it's longer be here it's d c b and a so we can treat a linked list as a stack topo da minha lista encadeada, então f não deveria mais estar aqui, está mais aqui, está d c b e a, então podemos tratar uma lista encadeada como uma pilha [07:13] list as a stack we can also treat it as a queue as well lista como uma pilha, também podemos tratá-la como uma fila [07:16] we can also treat it as a queue as well and just to save some time i'm going to copy these lines of code também podemos tratá-la como uma fila e, para economizar tempo, vou copiar estas linhas de código [07:19] copy these lines of code to add an element to a queue we do not use push we use offer so linkedlist.offer copiar estas linhas de código para adicionar um elemento a uma fila, não usamos push, usamos offer, então linkedlist.offer [07:26] offer so linkedlist.offer and we will keep the order so i'm not going to pop it quite yet offer, então linkedlist.offer e manteremos a ordem, então não vou removê-lo ainda [07:29] and we will keep the order so i'm not going to pop it quite yet so we have a b c d f a is at the head f is at the tail and to remove the head of our q we do not use pop we use pull e manteremos a ordem, então não vou removê-lo ainda, então temos a b c d f, a está na cabeça, f está na cauda e para remover a cabeça da nossa fila, não usamos pop, usamos pull [07:40] of our q we do not use pop we use pull and a is no longer in here we have b c f da nossa fila, não usamos pop, usamos pull e a não está mais aqui, temos b c f [07:43] so you can use a linked list to mimic a stack or a queue então você pode usar uma lista encadeada para imitar uma pilha ou uma fila [07:47] stack or a queue before we move on to the next section i'm going to get rid of this pull method pilha ou uma fila, antes de passarmos para a próxima seção, vou me livrar deste método pull [07:49] i'm going to get rid of this pull method so we have a typical grading scale a b c d f where linked lists are really good vou me livrar deste método pull, então temos uma escala de notas típica a b c d f, onde listas encadeadas são muito boas [07:57] is the insertion and deletion of nodes let's say for this example i need to add a node between d and f that contains the letter e é a inserção e exclusão de nós, digamos que para este exemplo eu precise adicionar um nó entre d e f que contenha a letra e [08:02] so that's really easy to do with the linked list então isso é muito fácil de fazer com a lista encadeada [08:06] list we would type the name of our linked list dot add lista, digitaríamos o nome da nossa lista encadeada ponto add [08:09] list dot add list and index like for and our object lista ponto adicionar lista e índice como para e nosso objeto [08:13] list and index like for and our object e and then to remove a node we would type the name of our linked list lista e índice como para e nosso objeto e e então para remover um nó digitaríamos o nome da nossa lista ligada [08:17] dot remove then list the object e ponto remover então listar o objeto e [08:20] so e should no longer be within my linked list então e não deve mais estar dentro da minha lista ligada [08:22] so where linked lists tend to have an advantage over arrays and array lists is the insertion and deletion of nodes então onde as listas ligadas tendem a ter uma vantagem sobre arrays e listas de arrays é a inserção e exclusão de nós [08:30] however there's one catch to this no entanto há uma pegadinha nisso [08:32] with a linked list we still need to traverse the entire linked list to find where we need to go com uma lista ligada ainda precisamos percorrer toda a lista ligada para encontrar onde precisamos ir [08:37] unlike with arrays and array lists there's no random access to a linked list ao contrário de arrays e listas de arrays não há acesso aleatório a uma lista ligada [08:41] searching for an element is fairly straightforward too buscar um elemento também é bastante simples [08:43] so within a print line statement i'm going to use the index of method of a linked list então dentro de uma instrução de impressão vou usar o método index of de uma lista ligada [08:50] linkedlist.index of let's look for f so that would be at index four linkedlist.index of vamos procurar por f então isso seria no índice quatro [08:55] and before we wrap things up here here's a few methods related to linked lists that you might be interested in e antes de encerrarmos por aqui aqui estão alguns métodos relacionados a listas ligadas que você pode achar interessantes [09:00] we can peek at the head or the tail node of our linked list podemos espiar o nó da cabeça ou da cauda da nossa lista ligada [09:06] so within a print line statement i'm going to print linked list então dentro de uma instrução de impressão vou imprimir a lista ligada [09:09] going to print linked list dot and then use the peak first method. vou imprimir a lista ligada ponto e então usar o método peak first. [09:13] dot and then use the peak first method so the first node within my linked list. ponto e então usar o método peak first, então o primeiro nó dentro da minha lista ligada. [09:16] so the first node within my linked list contains the letter. então o primeiro nó dentro da minha lista ligada contém a letra. [09:17] contains the letter a so we can peek last as well linked. contém a letra a, então podemos dar uma olhada no último também, ligado. [09:20] a so we can peek last as well linked list. a, então podemos dar uma olhada no último também, lista ligada. [09:20] list dot peak last and the last node of my. lista ponto peak last e o último nó da minha. [09:24] dot peak last and the last node of my linked list contains the letter f. ponto peak last e o último nó da minha lista ligada contém a letra f. [09:26] linked list contains the letter f we can add new nodes at the head or the. lista ligada contém a letra f, podemos adicionar novos nós na cabeça ou na. [09:28] we can add new nodes at the head or the tail of our linked list by using the. podemos adicionar novos nós na cabeça ou na cauda da nossa lista ligada usando o. [09:30] tail of our linked list by using the add first method for the head so maybe i. cauda da nossa lista ligada usando o método add first para a cabeça, então talvez eu. [09:34] add first method for the head so maybe i need to add. método add first para a cabeça, então talvez eu precise adicionar. [09:35] need to add maybe zero because i don't really know. preciso adicionar talvez zero porque eu realmente não sei. [09:37] maybe zero because i don't really know what comes before a in the alphabet so. talvez zero porque eu realmente não sei o que vem antes de a no alfabeto, então. [09:39] what comes before a in the alphabet so zero would be a good bet i guess or we. o que vem antes de a no alfabeto, então zero seria uma boa aposta, eu acho, ou nós. [09:41] zero would be a good bet i guess or we could add to the tail by using. zero seria uma boa aposta, eu acho, ou nós poderíamos adicionar à cauda usando. [09:43] could add to the tail by using add last and after. poderíamos adicionar à cauda usando add last e depois. [09:46] add last and after f comes g and we now have. add last e depois de f vem g e agora temos. [09:50] f comes g and we now have g at the tail of our linked list we can. f vem g e agora temos g na cauda da nossa lista ligada, podemos. [09:53] g at the tail of our linked list we can remove first and remove last. g na cauda da nossa lista ligada, podemos remover o primeiro e remover o último. [09:55] remove first and remove last you can also store them within a. remover o primeiro e remover o último, você também pode armazená-los em uma. [09:56] you can also store them within a variable two let's say string. você também pode armazená-los em uma variável dois, digamos string. [09:58] variable two let's say string first equals linked list dot. variável dois, digamos string first equals linked list dot. [10:01] first equals linked list dot remove first then to remove the last. first equals linked list dot remove first, então para remover o último. [10:04] remove first then to remove the last node. remove first, então para remover o último nó. [10:06] node we could just use remove last then. nó, poderíamos apenas usar remove last, então. [10:10] we could just use remove last then and let's store this within a different podemos simplesmente usar remover último e então vamos armazenar isso em um diferente [10:12] and let's store this within a different variable remove e vamos armazenar isso em uma variável diferente remover [10:13] variable remove last so yeah those are a few useful variável remover último então sim esses são alguns úteis [10:17] last so yeah those are a few useful methods related to linked lists último então sim esses são alguns métodos úteis relacionados a listas ligadas [10:18] methods related to linked lists in conclusion everybody a linked list is métodos relacionados a listas ligadas em conclusão todos uma lista ligada é [10:21] in conclusion everybody a linked list is a data structure that stores a series of em conclusão todos uma lista ligada é uma estrutura de dados que armazena uma série de [10:23] a data structure that stores a series of nodes uma estrutura de dados que armazena uma série de nós [10:24] nodes each node contains two parts some data nós cada nó contém duas partes alguns dados [10:26] each node contains two parts some data and an address cada nó contém duas partes alguns dados e um endereço [10:27] and an address nodes are stored in non-consecutive e um endereço nós são armazenados em não consecutivos [10:30] nodes are stored in non-consecutive memory locations nós são armazenados em locais de memória não consecutivos [10:31] memory locations each node can be really anywhere within locais de memória cada nó pode estar realmente em qualquer lugar dentro [10:33] each node can be really anywhere within your computer's memory cada nó pode estar realmente em qualquer lugar dentro da memória do seu computador [10:34] your computer's memory and elements are linked via these a memória do seu computador e elementos são ligados através destes [10:36] and elements are linked via these pointers they contain an address for e elementos são ligados através destes ponteiros eles contêm um endereço para [10:38] pointers they contain an address for where the next ponteiros eles contêm um endereço para onde o próximo [10:39] where the next node is we've discussed two varieties of onde o próximo nó está discutimos duas variedades de [10:42] node is we've discussed two varieties of linked lists a singly linked list nó está discutimos duas variedades de listas ligadas uma lista ligada simplesmente [10:44] linked lists a singly linked list as well as a doubly linked list with a listas ligadas uma lista ligada simplesmente assim como uma lista ligada duplamente com uma [10:46] as well as a doubly linked list with a singly linked list assim como uma lista ligada duplamente com uma lista ligada simplesmente [10:47] singly linked list each node is made up of two parts some lista ligada simplesmente cada nó é composto por duas partes alguns [10:50] each node is made up of two parts some data and an address cada nó é composto por duas partes alguns dados e um endereço [10:51] data and an address to traverse a singly linked list we dados e um endereço para percorrer uma lista ligada simplesmente nós [10:53] to traverse a singly linked list we would begin at the head node para percorrer uma lista ligada simplesmente nós começaríamos no nó cabeça [10:55] would begin at the head node and use the address as a sort of clue to começaríamos no nó cabeça e usaríamos o endereço como uma espécie de pista para [10:57] and use the address as a sort of clue to find where the next e usaríamos o endereço como uma espécie de pista para encontrar onde o próximo [10:58] find where the next node is located within our computer's encontrar onde o próximo nó está localizado dentro do nosso computador [11:00] node is located within our computer's memory with a doubly linked list nó está localizado dentro da memória do nosso computador com uma lista ligada duplamente [11:03] memory with a doubly linked list each node is made up of three parts some memória com uma lista ligada duplamente cada nó é composto por três partes alguns [11:05] each node is made up of three parts some data and two addresses cada nó é composto por três partes alguns dados e dois endereços [11:07] data and two addresses one address for the next node and dados e dois endereços um endereço para o próximo nó e [11:09] one address for the next node and another address for the previous node um endereço para o próximo nó e outro endereço para o nó anterior [11:10] another address for the previous node and it behaves the same way and to outro endereço para o nó anterior e ele se comporta da mesma forma e para [11:12] and it behaves the same way and to traverse a doubly linked list e ele se comporta da mesma forma e para percorrer uma lista duplamente encadeada [11:14] traverse a doubly linked list we could begin at the head and work our percorrer uma lista duplamente encadeada podemos começar pela cabeça e trabalhar nosso [11:15] we could begin at the head and work our way towards the tail or podemos começar pela cabeça e trabalhar nosso caminho em direção à cauda ou [11:17] way towards the tail or we could begin at the tail and work our caminho em direção à cauda ou podemos começar pela cauda e trabalhar nosso [11:18] we could begin at the tail and work our way towards the head depending on which podemos começar pela cauda e trabalhar nosso caminho em direção à cabeça dependendo de qual [11:20] way towards the head depending on which way is closer to where we need to be caminho em direção à cabeça dependendo de qual caminho está mais próximo de onde precisamos estar [11:22] way is closer to where we need to be within our linked list caminho está mais próximo de onde precisamos estar dentro da nossa lista encadeada [11:23] within our linked list what are some of the advantages of a dentro da nossa lista encadeada quais são algumas das vantagens de uma [11:25] what are some of the advantages of a linked list one they're a dynamic data quais são algumas das vantagens de uma lista encadeada um elas são uma estrutura de dados dinâmica [11:27] linked list one they're a dynamic data structure lista encadeada um elas são uma estrutura de dados dinâmica [11:28] structure they can allocate needed memory while estrutura elas podem alocar memória necessária enquanto [11:29] they can allocate needed memory while their program is currently running elas podem alocar memória necessária enquanto seu programa está em execução [11:31] their program is currently running two insertion and deletion of nodes is seu programa está em execução dois inserção e exclusão de nós é [11:33] two insertion and deletion of nodes is really easy dois inserção e exclusão de nós é realmente fácil [11:34] really easy if you're familiar with big-o notation realmente fácil se você estiver familiarizado com a notação big-o [11:36] if you're familiar with big-o notation this would be in constant time se você estiver familiarizado com a notação big-o isso seria em tempo constante [11:38] this would be in constant time there's only a few steps regardless of isso seria em tempo constante há apenas algumas etapas independentemente de [11:39] there's only a few steps regardless of the size of our data set há apenas algumas etapas independentemente do tamanho do nosso conjunto de dados [11:41] the size of our data set and three there is no to low memory o tamanho do nosso conjunto de dados e três não há desperdício de memória muito baixo [11:43] and three there is no to low memory waste what are some disadvantages e três não há desperdício de memória muito baixo quais são algumas desvantagens [11:46] waste what are some disadvantages one there is greater memory usage desvantagens quais são algumas desvantagens um há um maior uso de memória [11:48] one there is greater memory usage because we have to store an additional um há um maior uso de memória porque temos que armazenar um adicional [11:50] because we have to store an additional pointer porque temos que armazenar um ponteiro adicional [11:50] pointer each node also stores the address for ponteiro cada nó também armazena o endereço para [11:53] each node also stores the address for where the next node is located cada nó também armazena o endereço de onde o próximo nó está localizado [11:55] where the next node is located and even more so with a doubly linked onde o próximo nó está localizado e ainda mais com uma duplamente encadeada [11:56] and even more so with a doubly linked list this will use a lot more memory e ainda mais com uma lista duplamente encadeada isso usará muito mais memória [11:58] list this will use a lot more memory because we need lista isso usará muito mais memória porque precisamos [11:59] because we need two addresses for each node now two porque precisamos de dois endereços para cada nó agora dois [12:02] two addresses for each node now two there's no random axis of elements dois endereços para cada nó agora dois não há acesso aleatório a elementos [12:04] there's no random axis of elements within a linked list não há acesso aleatório a elementos dentro de uma lista encadeada [12:06] within a linked list to find an element we need to begin at dentro de uma lista encadeada para encontrar um elemento precisamos começar em [12:08] to find an element we need to begin at one end and work our way para encontrar um elemento precisamos começar em uma extremidade e trabalhar nosso caminho [12:09] one end and work our way towards the other end and three uma extremidade e trabalhar nosso caminho em direção à outra extremidade e três [12:12] towards the other end and three accessing and searching of elements is em direção à outra extremidade e três o acesso e a busca de elementos é [12:14] accessing and searching of elements is more time consuming o acesso e a busca de elementos consomem mais tempo [12:15] more time consuming this is done in linear time this is mais demorado isso é feito em tempo linear isso é [12:17] this is done in linear time this is where arrays and array lists have an isso é feito em tempo linear é onde arrays e listas de arrays têm uma [12:19] where arrays and array lists have an advantage onde arrays e listas de arrays têm uma vantagem [12:20] advantage since they use indexing they can vantagem pois usam indexação eles podem [12:22] since they use indexing they can randomly access an element of an array pois usam indexação eles podem acessar aleatoriamente um elemento de um array [12:24] randomly access an element of an array or an array list acessar aleatoriamente um elemento de um array ou de uma lista de arrays [12:25] or an array list with a linked list we have to manually ou uma lista de arrays com uma lista ligada temos que manualmente [12:27] with a linked list we have to manually traverse the entire linked list com uma lista ligada temos que percorrer manualmente toda a lista ligada [12:29] traverse the entire linked list to get to a particular index since we percorrer toda a lista ligada para chegar a um índice específico pois nós [12:32] to get to a particular index since we don't have random access para chegar a um índice específico pois não temos acesso aleatório [12:33] don't have random access now what are some uses of linked lists não temos acesso aleatório agora quais são alguns usos de listas ligadas [12:35] now what are some uses of linked lists one they could implement stacks or agora quais são alguns usos de listas ligadas um eles poderiam implementar pilhas ou [12:37] one they could implement stacks or queues if you need a stack or queue for um eles poderiam implementar pilhas ou filas se você precisar de uma pilha ou fila para [12:39] queues if you need a stack or queue for anything you could also use a linked filas para qualquer coisa você também poderia usar uma lista ligada [12:40] anything you could also use a linked list qualquer coisa você também poderia usar uma lista ligada [12:41] list two maybe gps navigation so let's say lista dois talvez navegação GPS então digamos [12:44] two maybe gps navigation so let's say you have a starting position and a final dois talvez navegação GPS então digamos que você tem uma posição inicial e uma final [12:46] you have a starting position and a final destination você tem uma posição inicial e um destino final [12:47] destination each step or stop along the way is kind destino cada passo ou parada ao longo do caminho é tipo [12:49] each step or stop along the way is kind of like a node and if you need to take a cada passo ou parada ao longo do caminho é como um nó e se você precisar fazer um [12:50] of like a node and if you need to take a detour tipo de nó e se você precisar fazer um desvio [12:51] detour you can easily change insert or delete a desvio você pode facilmente mudar inserir ou deletar um [12:53] you can easily change insert or delete a node and recalculate how to get to your você pode facilmente mudar inserir ou deletar um nó e recalcular como chegar ao seu [12:55] node and recalculate how to get to your final destination nó e recalcular como chegar ao seu destino final [12:57] final destination three what about a music playlist so destino final três e quanto a uma playlist de música então [12:59] three what about a music playlist so each song within a playlist might not três e quanto a uma playlist de música então cada música dentro de uma playlist pode não [13:01] each song within a playlist might not necessarily be next to each other within cada música dentro de uma playlist pode não estar necessariamente próxima uma da outra dentro [13:02] necessarily be next to each other within your computer's memory necessariamente próxima uma da outra dentro da memória do seu computador [13:03] your computer's memory you want your playlist to follow a memória do seu computador você quer que sua playlist siga uma [13:05] you want your playlist to follow a certain order of songs você quer que sua playlist siga uma certa ordem de músicas [13:07] certain order of songs so that could be another use of a linked certa ordem de músicas então esse poderia ser outro uso de uma lista [13:08] so that could be another use of a linked list so those are linked lists if you então esse poderia ser outro uso de uma lista ligada então essas são listas ligadas se você [13:11] list so those are linked lists if you would like lista então essas são listas ligadas se você gostaria [13:11] would like a copy of all my notes here and my code gostaria de uma cópia de todas as minhas anotações aqui e do meu código [13:13] a copy of all my notes here and my code i will post this to the comment section. uma cópia de todas as minhas anotações aqui e meu código, postarei isso na seção de comentários. [13:15] i will post this to the comment section down below. postarei isso na seção de comentários abaixo. [13:16] down below if you can give this video a thumbs up. abaixo se você puder dar um joinha neste vídeo. [13:18] if you can give this video a thumbs up drop a random comment down below. se você puder dar um joinha neste vídeo, deixe um comentário aleatório abaixo. [13:19] drop a random comment down below and well yeah those are linked lists in. deixe um comentário aleatório abaixo e bem, sim, essas são listas ligadas em. [13:22] and well yeah those are linked lists in computer science. e bem, sim, essas são listas ligadas em ciência da computação.