Linked Lists 🔗

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

Channel: Bro Code

Views: 44,330

Keywords: linked list java, linked list python, linked list java implementation, linked list algorithm, data structures and algorithms

Id: N6dOwBde7-M

Length: 13min 24sec (804 seconds)

Published: Mon Apr 19 2021