Learn Linked Lists in 13 minutes 🔗

Full Transcript

https://www.youtube.com/watch?v=N6dOwBde7-M

[00:00] hey what's going on everybody it's you
[00:02] hey what's going on everybody it's you bro hope you're doing well
[00:03] bro hope you're doing well in this video we're going to discuss
[00:05] in this video we're going to discuss linked lists and computer science
[00:06] linked lists and computer science so sit back relax and enjoy the show
[00:11] now before we dive straight into linked
[00:13] now before we dive straight into linked lists we're going to take a closer
[00:14] lists we're going to take a closer examination of arrays and array lists we
[00:16] examination of arrays and array lists we will see what disadvantages that these
[00:19] will see what disadvantages that these data structures have
[00:20] data structures have where linked lists excel at so we'll
[00:22] where linked lists excel at so we'll compare and contrast the differences
[00:24] compare and contrast the differences between the two
[00:25] between the two with what we understand with arrays and
[00:26] with what we understand with arrays and array lists these data structures store
[00:29] array lists these data structures store elements in contiguous memory locations
[00:31] elements in contiguous memory locations in this demonstration i'm storing
[00:33] in this demonstration i'm storing letters of the alphabet suppose that the
[00:35] letters of the alphabet suppose that the first element of my array has a memory
[00:37] first element of my array has a memory address of
[00:38] address of one two three fake street obviously
[00:40] one two three fake street obviously these are not real memory addresses but
[00:41] these are not real memory addresses but this is how i like to think about things
[00:43] this is how i like to think about things if this was a memory address then the
[00:45] if this was a memory address then the next element in my array may have an
[00:47] next element in my array may have an address of
[00:48] address of one two five fake street then one two
[00:51] one two five fake street then one two seven fake street
[00:52] seven fake street one two nine fake street and then you
[00:53] one two nine fake street and then you just continue on in that pattern
[00:55] just continue on in that pattern now arrays are fantastic at randomly
[00:57] now arrays are fantastic at randomly accessing elements because they have an
[00:58] accessing elements because they have an index
[00:59] index but they're not so great at inserting or
[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.
[01:04] Here's an example.
[01:05] Suppose I need to insert a new element at index 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.
[01:15] So the process of shifting is cumbersome.
[01:19] But once this element is empty, then I can insert a new value.
[01:21] So it's not that big of a deal if I have a small data set.
[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.
[01:33] And the same concept applies with deletion as well.
[01:34] We would shift our elements to the left to close the gap.
[01:39] You're probably thinking, dude, why are you talking about arrays in a video about linked lists?
[01:44] Well, where arrays have difficulty inserting and deleting, linked lists actually have the advantage.
[01:49] Here's a representation of a linked list.
[01:51] A linked list is made up of a long chain of nodes.
[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.
[02:02] also referred to as a pointer linked lists do not have an index the same way
[02:03] lists do not have an index the same way that arrays do
[02:04] that arrays do but each node contains an address to
[02:06] but each node contains an address to where the next node is located
[02:08] where the next node is located so these nodes are non-contiguous they
[02:10] so these nodes are non-contiguous they can really be anywhere within your
[02:12] can really be anywhere within your computer's memory
[02:13] computer's memory if our initial node has a memory address
[02:15] if our initial node has a memory address of one two three fake street
[02:17] of one two three fake street like our array example then the next
[02:19] like our array example then the next node in our linked list could have a
[02:21] node in our linked list could have a memory address of maybe
[02:23] memory address of maybe 101 help boulevard and another could be
[02:26] 101 help boulevard and another could be 404
[02:26] 404 nowhere lane then 666 crime circle
[02:30] nowhere lane then 666 crime circle each node knows where the next node
[02:31] each node knows where the next node resides i imagine this as if we're
[02:33] resides i imagine this as if we're following a scavenger hunt or
[02:35] following a scavenger hunt or a series of clues to find the end of the
[02:37] a series of clues to find the end of the linked list
[02:38] linked list the tale each node has an address a clue
[02:41] the tale each node has an address a clue as to where the next note is we begin at
[02:43] as to where the next note is we begin at the head and work our way
[02:45] the head and work our way towards the tail following each clue
[02:47] towards the tail following each clue each memory address found in each node
[02:49] each memory address found in each node then we know when we reach the end of
[02:51] then we know when we reach the end of our linked list when we check that
[02:53] our linked list when we check that address
[02:53] address our pointer and it has a value of null
[02:56] our pointer and it has a value of null that means we're at the tail we're at
[02:57] that means we're at the tail we're at the end of our linked list
[02:58] the end of our linked list inserting a node is easy in a linked
[03:00] inserting a node is easy in a linked list there's no shifting of elements
[03:01] list there's no shifting of elements involved wherever we need to place a new
[03:04] involved wherever we need to place a new node we take the address stored in the node.
[03:06] we take the address stored in the previous node.
[03:07] previous node and assign the address of our new node.
[03:09] and assign the address of our new node with the address from the previous node.
[03:12] with the address from the previous node so that our new node is pointing to the next node in line.
[03:14] so that our new node is pointing to the next node in line.
[03:15] next node in line then we can take and replace the address.
[03:17] then we can take and replace the address in the previous node.
[03:19] in the previous node with an address that points to our new node.
[03:20] with an address that points to our new node it's as simple as that and we're completing our chain.
[03:22] node it's as simple as that and we're completing our chain.
[03:23] completing our chain simply by inserting a node at a given location.
[03:25] simply by inserting a node at a given location there's only a few steps involved.
[03:27] location there's only a few steps involved no shifting of elements required.
[03:29] involved no shifting of elements required deleting nodes are easy too.
[03:31] required deleting nodes are easy too wherever we need to delete a node we have the previous node.
[03:32] wherever we need to delete a node we have the previous node point instead to the next node in line.
[03:34] have the previous node point instead to the next node in line.
[03:36] point instead to the next node in line again no shifting of elements is necessary.
[03:37] again no shifting of elements is necessary.
[03:38] necessary now this is where linked lists tend to be inferior to arrays.
[03:40] now this is where linked lists tend to be inferior to arrays.
[03:41] be inferior to arrays they are bad at searching we can randomly access an element of an array.
[03:43] they are bad at searching we can randomly access an element of an array.
[03:45] randomly access an element of an array because we have an index with a linked list that is not the case.
[03:46] because we have an index with a linked list that is not the case.
[03:48] index with a linked list that is not the case to locate an element we need to begin at the head.
[03:50] case to locate an element we need to begin at the head.
[03:51] begin at the head and work our way towards the tail until we find the element that we are looking for.
[03:53] and work our way towards the tail until we find the element that we are looking for.
[03:55] we find the element that we are looking for.
[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.
[03:57] this itself takes time in fact it would take linear time but making the insertion or deletion of a node is constant.
[03:59] take linear time but making the insertion or deletion of a node is constant.
[04:00] insertion or deletion of a node is constant this variation of a linked list is a singly linked list.
[04:02] or deletion of a node is constant this variation of a linked list is a singly linked list.
[04:03] variation of a linked list is a singly linked list there are single.
[04:06] is a singly linked list there are single links to each node.
[04:08] links to each node however there's another variation called.
[04:10] however there's another variation called a doubly linked list.
[04:11] a doubly linked list a doubly linked list requires even more.
[04:13] a doubly linked list requires even more memory to store two addresses in each.
[04:16] memory to store two addresses in each node not just one which is the case with.
[04:18] node not just one which is the case with a.
[04:18] a singly linked list one address for the.
[04:20] singly linked list one address for the next node and another for the previous.
[04:22] next node and another for the previous node in our chain.
[04:23] node in our chain the benefit of a doubly linked list is.
[04:25] the benefit of a doubly linked list is that we can traverse our doubly linked.
[04:27] that we can traverse our doubly linked list.
[04:28] list from head to tail or from tail to head.
[04:30] from head to tail or from tail to head in reverse.
[04:31] in reverse each node knows where the next and.
[04:33] each node knows where the next and previous note is.
[04:34] previous note is but the downside is that a doubly linked.
[04:37] but the downside is that a doubly linked list uses even more memory than a singly.
[04:39] list uses even more memory than a singly linked list.
[04:40] linked list so how about we create a linked list in.
[04:42] so how about we create a linked list in real life now let's do it.
[04:43] real life now let's do it all right ladies and gentlemen with all.
[04:45] all right ladies and gentlemen with all that out of the way let's create a.
[04:46] that out of the way let's create a linked list.
[04:47] linked list linked list list the data type of the.
[04:50] linked list list the data type of the objects we'll be storing within this.
[04:51] objects we'll be storing within this linked list.
[04:52] linked list just strings because they're easy and i.
[04:54] just strings because they're easy and i will name this linked list.
[04:55] will name this linked list linked list linked list equals new.
[04:58] linked list linked list equals new linked.
[04:59] linked list and list the data type again we are.
[05:01] list and list the data type again we are storing strings at a constructor boom.
[05:03] storing strings at a constructor boom you got yourself a linked list.
[05:04] you got yourself a linked list now if i was to take my cursor and hover.
[05:06] Now if I was to take my cursor and hover over my linked list declaration.
[05:08] Over my linked list declaration, there's a note here that says this is a doubly linked list.
[05:11] There's a note here that says this is a doubly linked list.
[05:12] Each node knows where the previous and next nodes are.
[05:14] List, each node knows where the previous and next nodes are.
[05:15] And next nodes are.
[05:17] Now if we head to the linked list class itself, there's a few things I need to mention here.
[05:19] List class itself, there's a few things I need to mention here.
[05:20] Need to mention here.
[05:22] Our linked list stores the memory location of our first and last nodes.
[05:25] Location of our first and last nodes.
[05:27] These are effectively the head and the tail of our linked list.
[05:28] Tail of our linked list.
[05:30] And there's also an inner class named node.
[05:31] Node.
[05:34] Each node knows the memory address of the next and previous nodes within this linked list.
[05:36] Previous nodes within this linked list.
[05:38] Now taking a look at our linked list class definition.
[05:40] Class definition.
[05:43] Our linked list class implements the deck interface, and a deck is more or less a double ended queue.
[05:45] Is more or less a double ended queue.
[05:48] So with the deck interface, we implement 12 additional methods.
[05:50] 12 additional methods.
[05:52] So here's just a few of them.
[05:53] So we can add to the head, add to the tail, remove the head, remove the tail.
[05:55] Add to the tail, remove the head, remove the tail.
[05:56] The tail, peek at the head, peek at the tail.
[05:58] Peek at the head, peek at the tail.
[06:00] Some will throw exceptions, some will return a special value.
[06:01] Special value.
[06:03] So you can use any combination of these really.
[06:05] Really.
[06:05] And not only do we have these 12 methods, but we can treat our linked list.
[06:07] methods but we can treat our linked list as either a stack or a queue we can push
[06:09] as either a stack or a queue we can push we can pop we can pull then we can offer
[06:11] we can pop we can pull then we can offer so just to demonstrate let's first treat
[06:13] so just to demonstrate let's first treat our linked list as a stack
[06:15] our linked list as a stack so linked lists do have a push method as
[06:18] so linked lists do have a push method as well if we need to
[06:19] well if we need to push an element onto our linked list as if it were a stack
[06:21] push an element onto our linked list as if it were a stack
[06:23] if it were a stack so let's push the letter a and then i will display my linked list
[06:26] will display my linked list with a print line statement
[06:28] with a print line statement system.out.printline linked list
[06:30] system.out.printline linked list and of course we have the letter a so
[06:32] and of course we have the letter a so let's push another letter onto our stack
[06:34] let's push another letter onto our stack what about b
[06:35] what about b so at the bottom of our linked list we have a and then on top we have 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
[06:43] represent a typical grading scale we have c d and 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
[06:52] later so within our linked list that's behaving as a stack
[06:55] behaving as a stack we have f on top then d c b and 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
[07:02] as well linked list dot pop and this will pop the top of my linked list so f should no
[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
[07:13] list as a stack we can also treat it as a queue as well
[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
[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
[07:26] offer so linkedlist.offer and we will keep the order so i'm not going to pop it quite yet
[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
[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
[07:43] so you can use a linked list to mimic a stack or a queue
[07:47] stack or a queue before we move on to the next section i'm going to get rid of this pull method
[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
[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
[08:02] so that's really easy to do with the linked list
[08:06] list we would type the name of our linked list dot add
[08:09] list dot add list and index like for and our object
[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
[08:17] dot remove then list the object e
[08:20] so e should no longer be within my linked list
[08:22] so where linked lists tend to have an advantage over arrays and array lists is the insertion and deletion of nodes
[08:30] however there's one catch to this
[08:32] with a linked list we still need to traverse the entire linked list to find where we need to go
[08:37] unlike with arrays and array lists there's no random access to a linked list
[08:41] searching for an element is fairly straightforward too
[08:43] so within a print line statement i'm going to use the index of method of a linked list
[08:50] linkedlist.index of let's look for f so that would be at index four
[08:55] and before we wrap things up here here's a few methods related to linked lists that you might be interested in
[09:00] we can peek at the head or the tail node of our linked list
[09:06] so within a print line statement i'm going to print linked list
[09:09] going to print linked list dot and then use the peak first method.
[09:13] dot and then use the peak first method so the first node within my linked list.
[09:16] so the first node within my linked list contains the letter.
[09:17] contains the letter a so we can peek last as well linked.
[09:20] a so we can peek last as well linked list.
[09:20] list dot peak last and the last node of my.
[09:24] dot peak last and the last node of my linked list contains the letter f.
[09:26] linked list contains the letter f we can add new nodes at the head or the.
[09:28] we can add new nodes at the head or the tail of our linked list by using the.
[09:30] tail of our linked list by using the add first method for the head so maybe i.
[09:34] add first method for the head so maybe i need to add.
[09:35] need to add maybe zero because i don't really know.
[09:37] maybe zero because i don't really know what comes before a in the alphabet so.
[09:39] what comes before a in the alphabet so zero would be a good bet i guess or we.
[09:41] zero would be a good bet i guess or we could add to the tail by using.
[09:43] could add to the tail by using add last and after.
[09:46] add last and after f comes g and we now have.
[09:50] f comes g and we now have g at the tail of our linked list we can.
[09:53] g at the tail of our linked list we can remove first and remove last.
[09:55] remove first and remove last you can also store them within a.
[09:56] you can also store them within a variable two let's say string.
[09:58] variable two let's say string first equals linked list dot.
[10:01] first equals linked list dot remove first then to remove the last.
[10:04] remove first then to remove the last node.
[10:06] node we could just use remove last then.
[10:10] we could just use remove last then and let's store this within a different
[10:12] and let's store this within a different variable remove
[10:13] variable remove last so yeah those are a few useful
[10:17] last so yeah those are a few useful methods related to linked lists
[10:18] methods related to linked lists in conclusion everybody a linked list is
[10:21] in conclusion everybody a linked list is a data structure that stores a series of
[10:23] a data structure that stores a series of nodes
[10:24] nodes each node contains two parts some data
[10:26] each node contains two parts some data and an address
[10:27] and an address nodes are stored in non-consecutive
[10:30] nodes are stored in non-consecutive memory locations
[10:31] memory locations each node can be really anywhere within
[10:33] each node can be really anywhere within your computer's memory
[10:34] your computer's memory and elements are linked via these
[10:36] and elements are linked via these pointers they contain an address for
[10:38] pointers they contain an address for where the next
[10:39] where the next node is we've discussed two varieties of
[10:42] node is we've discussed two varieties of linked lists a singly linked list
[10:44] linked lists a singly linked list as well as a doubly linked list with a
[10:46] as well as a doubly linked list with a singly linked list
[10:47] singly linked list each node is made up of two parts some
[10:50] each node is made up of two parts some data and an address
[10:51] data and an address to traverse a singly linked list we
[10:53] to traverse a singly linked list we would begin at the head node
[10:55] would begin at the head node and use the address as a sort of clue to
[10:57] and use the address as a sort of clue to find where the next
[10:58] find where the next node is located within our computer's
[11:00] node is located within our computer's memory with a doubly linked list
[11:03] memory with a doubly linked list each node is made up of three parts some
[11:05] each node is made up of three parts some data and two addresses
[11:07] data and two addresses one address for the next node and
[11:09] one address for the next node and another address for the previous node
[11:10] another address for the previous node and it behaves the same way and to
[11:12] and it behaves the same way and to traverse a doubly linked list
[11:14] traverse a doubly linked list we could begin at the head and work our
[11:15] we could begin at the head and work our way towards the tail or
[11:17] way towards the tail or we could begin at the tail and work our
[11:18] we could begin at the tail and work our way towards the head depending on which
[11:20] way towards the head depending on which way is closer to where we need to be
[11:22] way is closer to where we need to be within our linked list
[11:23] within our linked list what are some of the advantages of a
[11:25] what are some of the advantages of a linked list one they're a dynamic data
[11:27] linked list one they're a dynamic data structure
[11:28] structure they can allocate needed memory while
[11:29] they can allocate needed memory while their program is currently running
[11:31] their program is currently running two insertion and deletion of nodes is
[11:33] two insertion and deletion of nodes is really easy
[11:34] really easy if you're familiar with big-o notation
[11:36] if you're familiar with big-o notation this would be in constant time
[11:38] this would be in constant time there's only a few steps regardless of
[11:39] there's only a few steps regardless of the size of our data set
[11:41] the size of our data set and three there is no to low memory
[11:43] and three there is no to low memory waste what are some disadvantages
[11:46] waste what are some disadvantages one there is greater memory usage
[11:48] one there is greater memory usage because we have to store an additional
[11:50] because we have to store an additional pointer
[11:50] pointer each node also stores the address for
[11:53] each node also stores the address for where the next node is located
[11:55] where the next node is located and even more so with a doubly linked
[11:56] and even more so with a doubly linked list this will use a lot more memory
[11:58] list this will use a lot more memory because we need
[11:59] because we need two addresses for each node now two
[12:02] two addresses for each node now two there's no random axis of elements
[12:04] there's no random axis of elements within a linked list
[12:06] within a linked list to find an element we need to begin at
[12:08] to find an element we need to begin at one end and work our way
[12:09] one end and work our way towards the other end and three
[12:12] towards the other end and three accessing and searching of elements is
[12:14] accessing and searching of elements is more time consuming
[12:15] more time consuming this is done in linear time this is
[12:17] this is done in linear time this is where arrays and array lists have an
[12:19] where arrays and array lists have an advantage
[12:20] advantage since they use indexing they can
[12:22] since they use indexing they can randomly access an element of an array
[12:24] randomly access an element of an array or an array list
[12:25] or an array list with a linked list we have to manually
[12:27] with a linked list we have to manually traverse the entire linked list
[12:29] traverse the entire linked list to get to a particular index since we
[12:32] to get to a particular index since we don't have random access
[12:33] don't have random access now what are some uses of linked lists
[12:35] now what are some uses of linked lists one they could implement stacks or
[12:37] one they could implement stacks or queues if you need a stack or queue for
[12:39] queues if you need a stack or queue for anything you could also use a linked
[12:40] anything you could also use a linked list
[12:41] list two maybe gps navigation so let's say
[12:44] two maybe gps navigation so let's say you have a starting position and a final
[12:46] you have a starting position and a final destination
[12:47] destination each step or stop along the way is kind
[12:49] each step or stop along the way is kind of like a node and if you need to take a
[12:50] of like a node and if you need to take a detour
[12:51] detour you can easily change insert or delete a
[12:53] you can easily change insert or delete a node and recalculate how to get to your
[12:55] node and recalculate how to get to your final destination
[12:57] final destination three what about a music playlist so
[12:59] three what about a music playlist so each song within a playlist might not
[13:01] each song within a playlist might not necessarily be next to each other within
[13:02] necessarily be next to each other within your computer's memory
[13:03] your computer's memory you want your playlist to follow a
[13:05] you want your playlist to follow a certain order of songs
[13:07] certain order of songs so that could be another use of a linked
[13:08] so that could be another use of a linked list so those are linked lists if you
[13:11] list so those are linked lists if you would like
[13:11] would like a copy of all my notes here and my code
[13:13] a copy of all my notes here and my code i will post this to the comment section.
[13:15] i will post this to the comment section down below.
[13:16] down below if you can give this video a thumbs up.
[13:18] if you can give this video a thumbs up drop a random comment down below.
[13:19] drop a random comment down below and well yeah those are linked lists in.
[13:22] and well yeah those are linked lists in computer science.

Full Transcript

https://www.youtube.com/watch?v=N6dOwBde7-M
Translation: pt-BR

[00:00] Ei, o que está acontecendo todo mundo, é você
[00:02] Ei, o que está acontecendo todo mundo, é você, mano, espero que você esteja bem
[00:03] Mano, espero que você esteja bem, neste vídeo vamos discutir
[00:05] Neste vídeo, vamos discutir listas ligadas e ciência da computação
[00:06] Listas ligadas e ciência da computação, então sente-se, relaxe e aproveite o show
[00:11] Agora, antes de mergulharmos direto em linked
[00:13] Agora, antes de mergulharmos direto em listas ligadas, vamos dar uma olhada mais de perto
[00:14] Listas, vamos fazer um exame mais detalhado de arrays e listas de arrays, nós
[00:16] Exame de arrays e listas de arrays, veremos quais desvantagens essas
[00:19] Veremos quais desvantagens essas estruturas de dados têm
[00:20] Estruturas de dados têm onde as listas ligadas se destacam, então nós vamos
[00:22] Onde listas ligadas se destacam, então vamos comparar e contrastar as diferenças
[00:24] Comparar e contrastar as diferenças entre os dois
[00:25] Entre os dois com o que entendemos com arrays e
[00:26] Com o que entendemos com arrays e listas de arrays, essas estruturas de dados armazenam
[00:29] Listas de arrays, essas estruturas de dados armazenam elementos em locais de memória contíguos
[00:31] Elementos em locais de memória contíguos, nesta demonstração estou armazenando
[00:33] Nesta demonstração, estou armazenando letras do alfabeto, suponha que o
[00:35] Letras do alfabeto, suponha que o primeiro elemento do meu array tenha uma memória
[00:37] Primeiro elemento do meu array tem um endereço de memória de
[00:38] Endereço de uma duas três fake street, obviamente
[00:40] Uma duas três fake street, obviamente, estes não são endereços de memória reais, mas
[00:41] Estes não são endereços de memória reais, mas é assim que eu gosto de pensar nas coisas
[00:43] É assim que eu gosto de pensar nas coisas, se este fosse um endereço de memória, então o
[00:45] Se este fosse um endereço de memória, então o próximo elemento no meu array pode ter um
[00:47] Próximo elemento no meu array pode ter um endereço de
[00:48] Endereço de uma duas cinco fake street, então uma duas
[00:51] Uma duas cinco fake street, então uma duas sete fake street
[00:52] Sete fake street, uma duas nove fake street e então você
[00:53] Uma duas nove fake street e então você continua nesse padrão
[00:55] Continua nesse padrão, agora arrays são fantásticos em aleatoriamente
[00:57] Agora arrays são fantásticos em acessar elementos aleatoriamente porque eles têm um
[00:58] Acessar elementos porque eles têm um índice
[00:59] Índice, mas eles não são tão bons em inserir ou
[01:01] 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] Aqui está um exemplo.
[01:05] Suponha que eu precise inserir um novo elemento no índice 3.
[01:09] 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] Portanto, o processo de deslocamento é complicado.
[01:19] Mas, uma vez que este elemento esteja vazio, então eu posso inserir um novo valor.
[01:21] Portanto, não é um grande problema se eu tiver um pequeno conjunto de dados.
[01:24] 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] E o mesmo conceito se aplica à exclusão também.
[01:34] Deslocaríamos nossos elementos para a esquerda para fechar a lacuna.
[01:39] Você provavelmente está pensando, cara, por que você está falando sobre arrays em um vídeo sobre linked lists?
[01:44] Bem, onde arrays têm dificuldade em inserir e excluir, linked lists realmente têm a vantagem.
[01:49] Aqui está uma representação de uma linked list.
[01:51] Uma linked list é composta por uma longa cadeia de nós.
[01:53] 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] também referidos como ponteiros, listas ligadas não têm um índice da mesma forma
[02:03] listas não têm um índice da mesma forma que os arrays
[02:04] os arrays têm, mas cada nó contém um endereço para
[02:06] mas cada nó contém um endereço para onde o próximo nó está localizado
[02:08] onde o próximo nó está localizado, então esses nós são não contíguos, eles
[02:10] então esses nós são não contíguos, eles podem realmente estar em qualquer lugar dentro do seu
[02:12] podem realmente estar em qualquer lugar dentro da memória do seu computador
[02:13] memória do computador, se o nosso nó inicial tiver um endereço de memória
[02:15] se o nosso nó inicial tiver um endereço de memória de um dois três rua falsa
[02:17] de um dois três rua falsa, como nosso exemplo de array, então o próximo
[02:19] como nosso exemplo de array, então o próximo nó em nossa lista ligada poderia ter um
[02:21] nó em nossa lista ligada poderia ter um endereço de memória de talvez
[02:23] endereço de memória de talvez 101 Help Boulevard e outro poderia ser
[02:26] 101 Help Boulevard e outro poderia ser 404
[02:26] 404 Nowhere Lane, então 666 Crime Circle
[02:30] Nowhere Lane, então 666 Crime Circle, cada nó sabe onde o próximo nó
[02:31] cada nó sabe onde o próximo nó reside, eu imagino isso como se estivéssemos
[02:33] reside, eu imagino isso como se estivéssemos seguindo uma caça ao tesouro ou
[02:35] seguindo uma caça ao tesouro ou uma série de pistas para encontrar o fim da
[02:37] uma série de pistas para encontrar o fim da lista ligada
[02:38] lista ligada, a cauda, cada nó tem um endereço, uma pista
[02:41] a cauda, cada nó tem um endereço, uma pista de onde a próxima nota está, começamos em
[02:43] de onde a próxima nota está, começamos na cabeça e seguimos nosso caminho
[02:45] a cabeça e seguimos nosso caminho em direção à cauda, seguindo cada pista
[02:47] em direção à cauda, seguindo cada pista, cada endereço de memória encontrado em cada nó
[02:49] cada endereço de memória encontrado em cada nó, então sabemos quando chegamos ao fim da
[02:51] então sabemos quando chegamos ao fim da nossa lista ligada quando verificamos que
[02:53] nossa lista ligada quando verificamos esse endereço
[02:53] endereço, nosso ponteiro, e ele tem um valor nulo
[02:56] nosso ponteiro e ele tem um valor nulo, isso significa que estamos na cauda, estamos em
[02:57] isso significa que estamos na cauda, estamos no fim da nossa lista ligada
[02:58] o fim da nossa lista ligada, inserir um nó é fácil em uma ligação
[03:00] inserir um nó é fácil em uma lista ligada, não há deslocamento de elementos
[03:01] lista, não há deslocamento de elementos envolvido, onde quer que precisemos colocar um novo
[03:04] envolvido onde quer que precisemos colocar um novo nó, pegamos o endereço armazenado no nó.
[03:06] pegamos o endereço armazenado no nó anterior.
[03:07] nó anterior e atribuímos o endereço do nosso novo nó.
[03:09] e atribuímos o endereço do nosso novo nó com o endereço do nó anterior.
[03:12] com o endereço do nó anterior para que nosso novo nó aponte para o próximo nó na linha.
[03:14] para que nosso novo nó aponte para o próximo nó na linha.
[03:15] próximo nó na linha, então podemos pegar e substituir o endereço.
[03:17] então podemos pegar e substituir o endereço no nó anterior.
[03:19] no nó anterior com um endereço que aponte para o nosso novo nó.
[03:20] com um endereço que aponte para o nosso novo nó, é tão simples quanto isso e estamos completando nossa cadeia.
[03:22] nó, é tão simples quanto isso e estamos completando nossa cadeia.
[03:23] completando nossa cadeia simplesmente inserindo um nó em um determinado local.
[03:25] simplesmente inserindo um nó em um determinado local, há apenas alguns passos envolvidos.
[03:27] local, há apenas alguns passos envolvidos, nenhuma movimentação de elementos necessária.
[03:29] envolvida, nenhuma movimentação de elementos necessária, excluir nós também é fácil.
[03:31] necessária, excluir nós também é fácil, onde quer que precisemos excluir um nó, temos o nó anterior.
[03:32] onde quer que precisemos excluir um nó, fazemos o nó anterior apontar em vez disso para o próximo nó na linha.
[03:34] o nó anterior apontar em vez disso para o próximo nó na linha.
[03:36] apontar em vez disso para o próximo nó na linha novamente, nenhuma movimentação de elementos é necessária.
[03:37] novamente nenhuma movimentação de elementos é necessária.
[03:38] necessário, agora é aqui que as listas ligadas tendem a ser inferiores aos arrays.
[03:40] agora é aqui que as listas ligadas tendem a ser inferiores aos arrays.
[03:41] ser inferiores aos arrays, elas são ruins em busca, podemos acessar aleatoriamente um elemento de um array.
[03:43] elas são ruins em busca, podemos acessar aleatoriamente um elemento de um array.
[03:45] acessar aleatoriamente um elemento de um array porque temos um índice com uma lista ligada que não é o caso.
[03:46] porque temos um índice com uma lista ligada que não é o caso.
[03:48] índice com uma lista ligada que não é o caso, para localizar um elemento precisamos começar pela cabeça.
[03:50] caso, para localizar um elemento precisamos começar pela cabeça.
[03:51] começar pela cabeça e trabalhar em direção à cauda até encontrarmos o elemento que estamos procurando.
[03:53] e trabalhar em direção à cauda até encontrarmos o elemento que estamos procurando.
[03:55] encontrarmos o elemento que estamos procurando.
[03:55] 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] isso em si leva tempo, de fato, levaria tempo linear, mas tornar a inserção ou exclusão de um nó é constante.
[03:59] levar tempo linear, mas tornar a inserção ou exclusão de um nó é constante.
[04:00] inserção ou exclusão de um nó é constante, esta variação de uma lista ligada é uma lista ligada simplesmente.
[04:02] ou exclusão de um nó é constante, esta variação de uma lista ligada é uma lista ligada simplesmente.
[04:03] variação de uma lista ligada é uma lista ligada simplesmente, existem single.
[04:06] é uma lista ligada simples, existem links únicos para cada nó.
[04:08] links para cada nó, no entanto, existe outra variação chamada.
[04:10] no entanto, existe outra variação chamada lista duplamente ligada.
[04:11] uma lista duplamente ligada, uma lista duplamente ligada requer ainda mais.
[04:13] uma lista duplamente ligada requer ainda mais memória para armazenar dois endereços em cada.
[04:16] memória para armazenar dois endereços em cada nó, não apenas um, que é o caso de.
[04:18] nó, não apenas um, que é o caso de uma.
[04:18] uma lista ligada simples, um endereço para o.
[04:20] lista ligada simples, um endereço para o próximo nó e outro para o anterior.
[04:22] próximo nó e outro para o nó anterior em nossa cadeia.
[04:23] nó em nossa cadeia, o benefício de uma lista duplamente ligada é.
[04:25] o benefício de uma lista duplamente ligada é que podemos percorrer nossa lista duplamente ligada.
[04:27] que podemos percorrer nossa lista duplamente ligada.
[04:28] lista da cabeça para a cauda ou da cauda para a cabeça.
[04:30] da cabeça para a cauda ou da cauda para a cabeça, ao contrário.
[04:31] ao contrário, cada nó sabe onde o próximo e.
[04:33] cada nó sabe onde está o próximo e o nó anterior.
[04:34] nó anterior está, mas a desvantagem é que uma duplamente ligada.
[04:37] mas a desvantagem é que uma lista duplamente ligada usa ainda mais memória do que uma simplesmente.
[04:39] lista usa ainda mais memória do que uma lista ligada simples.
[04:40] lista ligada, então que tal criarmos uma lista ligada em.
[04:42] então que tal criarmos uma lista ligada na vida real agora, vamos fazer isso.
[04:43] vida real agora, vamos fazer isso. Tudo bem, senhoras e senhores, com tudo.
[04:45] tudo bem, senhoras e senhores, com tudo isso fora do caminho, vamos criar uma.
[04:46] isso fora do caminho, vamos criar uma lista ligada.
[04:47] lista ligada, lista ligada, lista, o tipo de dado do.
[04:50] lista ligada, lista, o tipo de dado dos objetos que armazenaremos nesta.
[04:51] objetos que armazenaremos nesta lista ligada.
[04:52] lista ligada, apenas strings porque são fáceis e eu.
[04:54] apenas strings porque são fáceis e eu nomearei esta lista ligada.
[04:55] nomearei esta lista ligada, lista ligada, lista ligada igual a novo.
[04:58] lista ligada, lista ligada igual a nova ligada.
[04:59] lista ligada e lista o tipo de dado novamente estamos.
[05:01] lista e lista o tipo de dado novamente estamos armazenando strings em um construtor, boom.
[05:03] armazenando strings em um construtor, boom, você tem uma lista ligada.
[05:04] você tem uma lista ligada, agora se eu pegasse meu cursor e passasse o mouse.
[05:06] Agora, se eu fosse pegar meu cursor e passar sobre a declaração da minha lista ligada.
[05:08] Sobre a declaração da minha lista ligada, há uma nota aqui que diz que esta é uma lista duplamente ligada.
[05:11] Há uma nota aqui que diz que esta é uma lista duplamente ligada.
[05:12] Cada nó sabe onde os nós anterior e próximo estão.
[05:14] Lista, cada nó sabe onde os nós anterior e próximo estão.
[05:15] E os nós próximos estão.
[05:17] Agora, se formos para a própria classe de lista ligada, há algumas coisas que preciso mencionar aqui.
[05:19] Classe da lista em si, há algumas coisas que preciso mencionar aqui.
[05:20] Preciso mencionar aqui.
[05:22] Nossa lista ligada armazena a localização na memória de nossos primeiro e último nós.
[05:25] Localização de nossos primeiro e último nós.
[05:27] Estes são efetivamente a cabeça e a cauda de nossa lista ligada.
[05:28] Cauda de nossa lista ligada.
[05:30] E também há uma classe interna chamada nó.
[05:31] Nó.
[05:34] Cada nó conhece o endereço de memória dos nós próximo e anterior dentro desta lista ligada.
[05:36] Nós anteriores dentro desta lista ligada.
[05:38] Agora, dando uma olhada na definição da nossa classe de lista ligada.
[05:40] Definição da classe.
[05:43] Nossa classe de lista ligada implementa a interface deck, e um deck é mais ou menos uma fila de duas pontas.
[05:45] É mais ou menos uma fila de duas pontas.
[05:48] Portanto, com a interface deck, implementamos 12 métodos adicionais.
[05:50] 12 métodos adicionais.
[05:52] Então, aqui estão apenas alguns deles.
[05:53] Então podemos adicionar à cabeça, adicionar à cauda, remover a cabeça, remover a cauda.
[05:55] Adicionar à cauda, remover a cabeça, remover a cauda.
[05:56] A cauda, espiar a cabeça, espiar a cauda.
[05:58] Espiar a cabeça, espiar a cauda.
[06:00] Alguns lançarão exceções, alguns retornarão um valor especial.
[06:01] Valor especial.
[06:03] Então você pode usar qualquer combinação destes, realmente.
[06:05] Realmente.
[06:05] E não só temos estes 12 métodos, mas podemos tratar nossa lista ligada.
[06:07] métodos, mas podemos tratar nossa lista ligada como uma pilha ou uma fila, podemos adicionar
[06:09] como uma pilha ou uma fila, podemos adicionar, podemos remover, podemos puxar, então podemos oferecer
[06:11] podemos remover, podemos puxar, então podemos oferecer, então, apenas para demonstrar, vamos primeiro tratar
[06:13] então, apenas para demonstrar, vamos primeiro tratar nossa lista ligada como uma pilha
[06:15] nossa lista ligada como uma pilha, então listas ligadas têm um método push também
[06:18] então listas ligadas têm um método push também se precisarmos
[06:19] bem, se precisarmos adicionar um elemento à nossa lista ligada como se fosse uma pilha
[06:21] adicionar um elemento à nossa lista ligada como se fosse uma pilha
[06:23] se fosse uma pilha, então vamos adicionar a letra a e então exibirei minha lista ligada
[06:26] exibirei minha lista ligada com uma instrução de impressão
[06:28] com uma instrução de impressão system.out.printline linked list
[06:30] system.out.printline linked list e, claro, temos a letra a, então
[06:32] e, claro, temos a letra a, então vamos adicionar outra letra à nossa pilha
[06:34] vamos adicionar outra letra à nossa pilha, que tal b
[06:35] que tal b, então na parte inferior da nossa lista ligada temos a e então no topo temos b
[06:39] 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] representamos uma escala de notas típica, temos c, d e f, a, b, c
[06:47] c, d e f, a, b, c, d, f, note que estou intencionalmente deixando e de fora, vamos inseri-lo mais tarde
[06:52] mais tarde, então dentro da nossa lista ligada que está se comportando como uma pilha
[06:55] comportando-se como uma pilha, temos f no topo, depois d, c, b e a
[06:59] temos f no topo, depois d, c, b e a, então também temos acesso a um método pop
[07:02] também linked list ponto pop e isso removerá o topo da minha lista ligada, então f deveria não
[07:08] 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] lista como uma pilha, também podemos tratá-la como uma fila
[07:16] também podemos tratá-la como uma fila e, para economizar tempo, vou copiar estas linhas de código
[07:19] 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, então linkedlist.offer e manteremos a ordem, então não vou removê-lo ainda
[07:29] 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] da nossa fila, não usamos pop, usamos pull e a não está mais aqui, temos b c f
[07:43] então você pode usar uma lista encadeada para imitar uma pilha ou uma fila
[07:47] pilha ou uma fila, antes de passarmos para a próxima seção, vou me livrar deste método pull
[07:49] 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] é 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] então isso é muito fácil de fazer com a lista encadeada
[08:06] lista, digitaríamos o nome da nossa lista encadeada ponto add
[08:09] lista ponto adicionar lista e índice como para e nosso objeto
[08:13] 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] ponto remover então listar o objeto e
[08:20] então e não deve mais estar dentro da minha lista ligada
[08:22] 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] no entanto há uma pegadinha nisso
[08:32] com uma lista ligada ainda precisamos percorrer toda a lista ligada para encontrar onde precisamos ir
[08:37] ao contrário de arrays e listas de arrays não há acesso aleatório a uma lista ligada
[08:41] buscar um elemento também é bastante simples
[08:43] 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 vamos procurar por f então isso seria no índice quatro
[08:55] e antes de encerrarmos por aqui aqui estão alguns métodos relacionados a listas ligadas que você pode achar interessantes
[09:00] podemos espiar o nó da cabeça ou da cauda da nossa lista ligada
[09:06] então dentro de uma instrução de impressão vou imprimir a lista ligada
[09:09] vou imprimir a lista ligada ponto e então usar o método peak first.
[09:13] ponto e então usar o método peak first, então o primeiro nó dentro da minha lista ligada.
[09:16] então o primeiro nó dentro da minha lista ligada contém a letra.
[09:17] contém a letra a, então podemos dar uma olhada no último também, ligado.
[09:20] a, então podemos dar uma olhada no último também, lista ligada.
[09:20] lista ponto peak last e o último nó da minha.
[09:24] ponto peak last e o último nó da minha lista ligada contém a letra f.
[09:26] lista ligada contém a letra f, podemos adicionar novos nós na cabeça ou na.
[09:28] podemos adicionar novos nós na cabeça ou na cauda da nossa lista ligada usando o.
[09:30] cauda da nossa lista ligada usando o método add first para a cabeça, então talvez eu.
[09:34] método add first para a cabeça, então talvez eu precise adicionar.
[09:35] preciso adicionar talvez zero porque eu realmente não sei.
[09:37] talvez zero porque eu realmente não sei o que vem antes de a no alfabeto, então.
[09:39] o que vem antes de a no alfabeto, então zero seria uma boa aposta, eu acho, ou nós.
[09:41] zero seria uma boa aposta, eu acho, ou nós poderíamos adicionar à cauda usando.
[09:43] poderíamos adicionar à cauda usando add last e depois.
[09:46] add last e depois de f vem g e agora temos.
[09:50] f vem g e agora temos g na cauda da nossa lista ligada, podemos.
[09:53] g na cauda da nossa lista ligada, podemos remover o primeiro e remover o último.
[09:55] remover o primeiro e remover o último, você também pode armazená-los em uma.
[09:56] você também pode armazená-los em uma variável dois, digamos string.
[09:58] variável dois, digamos string first equals linked list dot.
[10:01] first equals linked list dot remove first, então para remover o último.
[10:04] remove first, então para remover o último nó.
[10:06] nó, poderíamos apenas usar remove last, então.
[10:10] podemos simplesmente usar remover último e então vamos armazenar isso em um diferente
[10:12] e vamos armazenar isso em uma variável diferente remover
[10:13] variável remover último então sim esses são alguns úteis
[10:17] último então sim esses são alguns métodos úteis relacionados a listas ligadas
[10:18] métodos relacionados a listas ligadas em conclusão todos uma lista ligada é
[10:21] em conclusão todos uma lista ligada é uma estrutura de dados que armazena uma série de
[10:23] uma estrutura de dados que armazena uma série de nós
[10:24] nós cada nó contém duas partes alguns dados
[10:26] cada nó contém duas partes alguns dados e um endereço
[10:27] e um endereço nós são armazenados em não consecutivos
[10:30] nós são armazenados em locais de memória não consecutivos
[10:31] locais de memória cada nó pode estar realmente em qualquer lugar dentro
[10:33] cada nó pode estar realmente em qualquer lugar dentro da memória do seu computador
[10:34] a memória do seu computador e elementos são ligados através destes
[10:36] e elementos são ligados através destes ponteiros eles contêm um endereço para
[10:38] ponteiros eles contêm um endereço para onde o próximo
[10:39] onde o próximo nó está discutimos duas variedades de
[10:42] nó está discutimos duas variedades de listas ligadas uma lista ligada simplesmente
[10:44] listas ligadas uma lista ligada simplesmente assim como uma lista ligada duplamente com uma
[10:46] assim como uma lista ligada duplamente com uma lista ligada simplesmente
[10:47] lista ligada simplesmente cada nó é composto por duas partes alguns
[10:50] cada nó é composto por duas partes alguns dados e um endereço
[10:51] dados e um endereço para percorrer uma lista ligada simplesmente nós
[10:53] para percorrer uma lista ligada simplesmente nós começaríamos no nó cabeça
[10:55] começaríamos no nó cabeça e usaríamos o endereço como uma espécie de pista para
[10:57] e usaríamos o endereço como uma espécie de pista para encontrar onde o próximo
[10:58] encontrar onde o próximo nó está localizado dentro do nosso computador
[11:00] nó está localizado dentro da memória do nosso computador com uma lista ligada duplamente
[11:03] memória com uma lista ligada duplamente cada nó é composto por três partes alguns
[11:05] cada nó é composto por três partes alguns dados e dois endereços
[11:07] dados e dois endereços um endereço para o próximo nó e
[11:09] um endereço para o próximo nó e outro endereço para o nó anterior
[11:10] outro endereço para o nó anterior e ele se comporta da mesma forma e para
[11:12] e ele se comporta da mesma forma e para percorrer uma lista duplamente encadeada
[11:14] percorrer uma lista duplamente encadeada podemos começar pela cabeça e trabalhar nosso
[11:15] podemos começar pela cabeça e trabalhar nosso caminho em direção à cauda ou
[11:17] caminho em direção à cauda ou podemos começar pela cauda e trabalhar nosso
[11:18] podemos começar pela cauda e trabalhar nosso caminho em direção à cabeça dependendo de qual
[11:20] caminho em direção à cabeça dependendo de qual caminho está mais próximo de onde precisamos estar
[11:22] caminho está mais próximo de onde precisamos estar dentro da nossa lista encadeada
[11:23] dentro da nossa lista encadeada quais são algumas das vantagens de uma
[11:25] quais são algumas das vantagens de uma lista encadeada um elas são uma estrutura de dados dinâmica
[11:27] lista encadeada um elas são uma estrutura de dados dinâmica
[11:28] estrutura elas podem alocar memória necessária enquanto
[11:29] elas podem alocar memória necessária enquanto seu programa está em execução
[11:31] seu programa está em execução dois inserção e exclusão de nós é
[11:33] dois inserção e exclusão de nós é realmente fácil
[11:34] realmente fácil se você estiver familiarizado com a notação big-o
[11:36] se você estiver familiarizado com a notação big-o isso seria em tempo constante
[11:38] isso seria em tempo constante há apenas algumas etapas independentemente de
[11:39] há apenas algumas etapas independentemente do tamanho do nosso conjunto de dados
[11:41] o tamanho do nosso conjunto de dados e três não há desperdício de memória muito baixo
[11:43] e três não há desperdício de memória muito baixo quais são algumas desvantagens
[11:46] desvantagens quais são algumas desvantagens um há um maior uso de memória
[11:48] um há um maior uso de memória porque temos que armazenar um adicional
[11:50] porque temos que armazenar um ponteiro adicional
[11:50] ponteiro cada nó também armazena o endereço para
[11:53] cada nó também armazena o endereço de onde o próximo nó está localizado
[11:55] onde o próximo nó está localizado e ainda mais com uma duplamente encadeada
[11:56] e ainda mais com uma lista duplamente encadeada isso usará muito mais memória
[11:58] lista isso usará muito mais memória porque precisamos
[11:59] porque precisamos de dois endereços para cada nó agora dois
[12:02] dois endereços para cada nó agora dois não há acesso aleatório a elementos
[12:04] não há acesso aleatório a elementos dentro de uma lista encadeada
[12:06] dentro de uma lista encadeada para encontrar um elemento precisamos começar em
[12:08] para encontrar um elemento precisamos começar em uma extremidade e trabalhar nosso caminho
[12:09] uma extremidade e trabalhar nosso caminho em direção à outra extremidade e três
[12:12] em direção à outra extremidade e três o acesso e a busca de elementos é
[12:14] o acesso e a busca de elementos consomem mais tempo
[12:15] mais demorado isso é feito em tempo linear isso é
[12:17] isso é feito em tempo linear é onde arrays e listas de arrays têm uma
[12:19] onde arrays e listas de arrays têm uma vantagem
[12:20] vantagem pois usam indexação eles podem
[12:22] pois usam indexação eles podem acessar aleatoriamente um elemento de um array
[12:24] acessar aleatoriamente um elemento de um array ou de uma lista de arrays
[12:25] ou uma lista de arrays com uma lista ligada temos que manualmente
[12:27] com uma lista ligada temos que percorrer manualmente toda a lista ligada
[12:29] percorrer toda a lista ligada para chegar a um índice específico pois nós
[12:32] para chegar a um índice específico pois não temos acesso aleatório
[12:33] não temos acesso aleatório agora quais são alguns usos de listas ligadas
[12:35] agora quais são alguns usos de listas ligadas um eles poderiam implementar pilhas ou
[12:37] um eles poderiam implementar pilhas ou filas se você precisar de uma pilha ou fila para
[12:39] filas para qualquer coisa você também poderia usar uma lista ligada
[12:40] qualquer coisa você também poderia usar uma lista ligada
[12:41] lista dois talvez navegação GPS então digamos
[12:44] dois talvez navegação GPS então digamos que você tem uma posição inicial e uma final
[12:46] você tem uma posição inicial e um destino final
[12:47] destino cada passo ou parada ao longo do caminho é tipo
[12:49] cada passo ou parada ao longo do caminho é como um nó e se você precisar fazer um
[12:50] tipo de nó e se você precisar fazer um desvio
[12:51] desvio você pode facilmente mudar inserir ou deletar um
[12:53] você pode facilmente mudar inserir ou deletar um nó e recalcular como chegar ao seu
[12:55] nó e recalcular como chegar ao seu destino final
[12:57] destino final três e quanto a uma playlist de música então
[12:59] três e quanto a uma playlist de música então cada música dentro de uma playlist pode não
[13:01] cada música dentro de uma playlist pode não estar necessariamente próxima uma da outra dentro
[13:02] necessariamente próxima uma da outra dentro da memória do seu computador
[13:03] memória do seu computador você quer que sua playlist siga uma
[13:05] você quer que sua playlist siga uma certa ordem de músicas
[13:07] certa ordem de músicas então esse poderia ser outro uso de uma lista
[13:08] então esse poderia ser outro uso de uma lista ligada então essas são listas ligadas se você
[13:11] lista então essas são listas ligadas se você gostaria
[13:11] gostaria de uma cópia de todas as minhas anotações aqui e do meu código
[13:13] uma cópia de todas as minhas anotações aqui e meu código, postarei isso na seção de comentários.
[13:15] postarei isso na seção de comentários abaixo.
[13:16] abaixo se você puder dar um joinha neste vídeo.
[13:18] se você puder dar um joinha neste vídeo, deixe um comentário aleatório abaixo.
[13:19] deixe um comentário aleatório abaixo e bem, sim, essas são listas ligadas em.
[13:22] e bem, sim, essas são listas ligadas em ciência da computação.

Full Transcript (Bilingual)

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.

https://www.youtube.com/watch?v=N6dOwBde7-M

Summary

TL;DR — Linked lists are dynamic data structures composed of nodes, each containing data and a pointer to the next node, allowing for efficient insertions and deletions. Unlike arrays, they don't store elements contiguously in memory, which makes random access slower but excels in scenarios requiring frequent modifications.

Key points

• Linked lists consist of nodes, where each node holds data and a memory address (pointer) to the subsequent node, forming a chain.

• They do not store elements in contiguous memory locations, offering flexibility but sacrificing direct index-based access.

• Insertion and deletion of nodes are highly efficient (constant time) as they only require updating pointers, unlike arrays which necessitate shifting elements.

• Searching for an element requires traversing the list sequentially from the head, making it less efficient than arrays for random access.

• Two main types exist: singly linked lists (one pointer per node) and doubly linked lists (two pointers per node, allowing bidirectional traversal).

• Common applications include implementing stacks, queues, GPS navigation systems, and music playlists.

Takeaway — Remember that linked lists offer superior performance for insertions and deletions compared to arrays, but at the cost of slower random access and searching.

Resumo / Summary (pt-BR)

Em resumo — Listas ligadas são estruturas de dados dinâmicas compostas por nós, cada um contendo dados e um ponteiro para o próximo nó, permitindo inserções e deleções eficientes. Ao contrário dos arrays, elas não armazenam elementos contiguamente na memória, o que torna o acesso aleatório mais lento, mas se destaca em cenários que exigem modificações frequentes.

Pontos-chave

• Listas ligadas consistem em nós, onde cada nó contém dados e um endereço de memória (ponteiro) para o nó subsequente, formando uma cadeia.

• Elas não armazenam elementos em locais de memória contíguos, oferecendo flexibilidade, mas sacrificando o acesso direto baseado em índice.

• A inserção e deleção de nós são altamente eficientes (tempo constante), pois exigem apenas a atualização de ponteiros, ao contrário dos arrays que necessitam de deslocamento de elementos.

• A busca por um elemento requer a travessia sequencial da lista a partir da cabeça, tornando-a menos eficiente que arrays para acesso aleatório.

• Existem dois tipos principais: listas ligadas simples (um ponteiro por nó) e listas ligadas duplas (dois ponteiros por nó, permitindo travessia bidirecional).

• Aplicações comuns incluem a implementação de pilhas, filas, sistemas de navegação GPS e playlists de música.

Conclusão — Lembre-se que listas ligadas oferecem desempenho superior para inserções e deleções em comparação com arrays, mas ao custo de acesso aleatório e busca mais lentos.