LinkedList vs ArrayList in Java Tutorial - Which Should You Use?

in this video we're going to talk all about linked lists in java how you can create them and use them we'll also talk about how they compare to array lists and also when you might want to use an arraylist over a linked list and vice versa my name is john and i do a new java tutorial video every single week so if you like this video and would like to see more please consider subscribing so you don't miss the new video every week i also have a full java course available in the link down in the description if you're interested i think a great place to start would be to just go ahead and create a linked list and an arraylist right here let's just say we wanted to create a list of names so it'll be a list of strings if we wanted to do that with a linked list we would just say a linked list string because it's a linked list of strings and then we need to give it a name so we can just call it names linked list equals new linked list and if you're using java 7 or higher which you should be you can just use the diamond operator here so just the less than and greater than symbols open and close parentheses and a semicolon in older versions of java you had to specify the type the list holds here as well so you would have had to put string here but now with the newer versions of java it can infer that type by the type that you put here so you can just use this diamond operator now of course we need to add the import for linked list which is just java.util.link list now let's look at how we would create an array list and compare them we just say arraylist string give it a name names arraylist equals new arraylist same diamond operator open and close parentheses and a semicolon and then we just need to import java.util.arraylist as you can see clearly the way you create the two is virtually identical and even the way we would add things to both of these lists is the same so if we want to add something to our linked list we just say nameslinklist dot add and then pass in the string we want so we can add uh the name john it's a good name we can copy paste and add some more paul george and ringo and if we want to add elements to our arraylist it's exactly the same so we can just copy paste that code and change this to the names arraylist and we can add things to our arraylist with the exact same method call just names arraylist.ad a big reason these classes are so similar is because they're both part of the java collections framework and they both implement the list interface so what does that mean now what we can do is we can actually nerd out and like control click into this linked list class and look at the code of the linked list and here's where it implements that list interface that i mentioned and we can hop into this list interface and if we press ctrl o in eclipse it shows all of the methods that a list has to support so you can see we have a lot of basic methods in here like getting its size checking if it's empty getting a certain element in it or setting a certain element in it adding an element to it so because both the arraylist and the linked list implement that list interface they both support those exact same list methods so if you already know the type of code that you have to use to work with arraylist those exact same methods that you use with arraylist will work just fine with your linked list so you might be thinking hey john it looks like these are basically exactly the same i use them the same way what's the difference who cares whether i use one over the other the difference between these two classes comes from how they are implemented behind the scenes and depending on what your specific program actually has to do with these lists that it creates using one versus the other could dramatically impact the performance of your program so let's talk about how these are implemented let's start with arraylist as you might know arraylist actually uses an array as its underlying data structure and just as like a quick refresher you could create like an array of strings in java like this like string array names equals new string array and you have to give it a size let's say we gave it size 4. as you may already know an array in java is a fixed length so once i've given this names array a size of 4 this array will always have exactly four elements in it what if you start your list with four things in it and later on you find you want to add more things to it well you can't you're gonna have to make a brand new array that's a bigger size and then you can add more things to it but if you had to program that yourself that would be a whole lot of work right so what arraylist does is it does all of that work behind the scenes so you never have to know how it's working or that it's even doing that but notice i didn't even have to give it a size here i think by default it gives it a size of 10 an initial capacity of 10. once it reaches that capacity it automatically creates a new array of a larger capacity and moves all of those elements into that new larger array but all of that dynamic resizing can take quite a bit of time and resources now let's compare that implementation with how the linked list works behind the scenes here's kind of a visual representation of how a linked list works a full credit to a geeksforgeeks.org for this image instead of having an array we just have a bunch of different elements each element is called a node and each element in your list has a pointer a reference to the next node so the linked list class starts with just a pointer to the first element in the list and after that each node each element in the list just has a reference a pointer sort of to the next node so the first one has a reference to the second the second one has a reference to the third etc so it's essentially like a big chain like a bunch of paper clips attached together so the linked list itself has just a reference to that first element and then you follow those pointers down the line to get to whatever element that you need you can also have what's called a doubly linked list and that is actually what the linked list class in java is it's a doubly linked list so all that means is that in addition to having a reference to the next node in the list each node also has a reference to the previous element in the list and it's not shown in this image but in the linked list implementation in java it also has a pointer to the very last element called the tail so java starts with a reference to the beginning of the list and the end of the list but to get to any element inside the list it has to follow those pointers to get to whatever element it needs to in any given time those differences in the underlying implementation of both of these classes have dramatic impacts on the performance of some very basic things that you can do with your lists let's say i just wanted to grab the third element in my list and print it out so in this case that would just be george well all i have to do is names linked list dot get and to get the third element in my list i would pass in the number two because it's zero based like everything else in programming so if i wanted to print that out it would just be system.out.printline and i can run my program and of course it prints out george and of course because the arraylist also supports this get method we can do the exact same thing with our arraylist and they both print out george but when you call this method on each of these two classes what they have to do behind the scenes is way different in the arraylist behind the scenes it uses an array to store all of the values and arrays have super fast what's called random access that means you can tell java to get any specific element in that list it doesn't matter which one and it runs in constant time that means it doesn't matter which element you ask java to get it takes the same amount of time to get it it takes the same amount of time to get the first element as it does to get the 5000 element or any element in between so down here when i say hey arraylist give me the object at index2 it does it immediately it can go right to that index and grab me that george value and print it out but how it works in the linked list is way different in a linked list java doesn't start with a reference to all the elements in between it just starts with a reference to the beginning element and the end element and if it wants to get any in between it has to follow these next or previous pointers to get the element that it wants for example if you had a list of like a thousand elements and you wanted to get the 400th element it can't go directly there it has to just start at the first element and keep getting the next value over and over and over again until it gets to that 400th element and then it can finally return it that operation is way slower for a linked list than it is for an arraylist however where a linked list typically kicks the heck out of an arraylist is when you need to add or remove elements let's say i want to do something really simple let's say i wanted to put the name jerry right between john and paul in my list well i can easily do that with names linked list dot add now to insert a value in a certain spot in your list you have to pass in the index that you want that value to go in so because i want it to be second in the list i'll give it an index of one and then i pass the value that i want added which would be jerry and of course the command in the arraylist is going to be exactly the same now let's compare how that insert has to work in both classes so in the linked list if i wanted to insert an element here in between a and b what java has to do is just start at the beginning of the list until it gets to the spot where it wants to insert the value and it just has to change this next reference that a has to be and instead point it to the new node that we're inserting and it also has to change the previous reference that b has to a and instead point it to the new node that we're creating and then it takes the next of that new node that it creates points it to b and it takes the previous of that nude node and points it to a and that's it it doesn't have to do anything with the whole rest of the list all the other links in the chain stay exactly the same there's nothing else i have to shift around or do it just impacts that small area of the list rewires a couple of little things and it's done for an arraylist that really shakes a lot of things up so what java actually has to do is it has to create a whole new array behind the scenes that's large enough to fit all the elements that it needs in it and it starts out empty so it might just look kind of something like this then it has to copy all of the existing entries into their right spots in this new array so it'll have john here paul here because we need to leave space to put jerry then george and ringo finally it takes this new element that it has to add and copies it over into its correct spot in the new array all that just to insert one value into one spot in the array now if we want to remove this jerry element from this spot in the list we would have to take each of the elements after it and shift them over one spot and of course if you have thousands or millions of things in your list that's a lot of work however for a linked list you could just get to that spot in the list rewire your next and previous references to just skip the thing you want to delete and you're done you don't need to shift everything else they just stay in their same spot in the chain so because of that adding and removing things from your list are going to be generally way faster in a linked list than they will be in an arraylist now with all that information where does that leave us when would i want to use a linked list and when would i want to use an arraylist now think about what actions are faster in each implementation so in an arraylist getting an element at a certain position is much faster it's instantaneous on the other hand inserting or removing a value is way faster in a linked list than it will be in an arraylist where it has to shift everything around so here's what the bottom line is first of all if you have a tiny list it probably doesn't matter which one you choose computers are just fast enough nowadays where for very small lists either of these are going to perform basically the same and you won't notice any difference but for very large lists it can really matter which one you choose an arraylist we have learned is very good at retrieving specific values but is worse at adding and removing them so if the program that you're working on is kind of creating a static list that doesn't change very much and has to spend a lot of its time just retrieving different values from it if that's the kind of work that your program has to do then arraylist is probably your best bet on the other hand if your program never really has a need to dive in and directly retrieve some random element from your list and your program is instead more focused on having to add things or remove things from especially the beginning or end of your list then a linked list is going to be able to perform those sorts of actions way faster than an arraylist but either way the methods that you call are going to look the same the list commands and the methods for both of these classes are going to be the same with the way they work behind the scenes is what is different about them so that's what's important to know again please consider subscribing if you got some value from this video so you don't miss the brand new video every week and be sure to check out all my existing java tutorials and walkthroughs too i'm sure you'll get a lot of value from them so thanks a lot for watching and i'll see you next time

Channel: Coding with John

Views: 6,539

Keywords: java, codingwithjohn, coding with john, java beginner lesson, java linkedlist, linkedlist in java, linkedlist vs arraylist, java linkedlist vs arraylist, linked list vs array list java, linked list vs array list, java linkedlist tutorial, linkedlist tutorial, learn java, java tutorial, java tutorial for beginners, java linked list, linkedlist java, arraylist vs linkedlist java, arraylist vs linkedlist, array list vs linked list, arraylist vs linked list java, java arraylist

Id: 5dscMs2hnDI

Length: 11min 43sec (703 seconds)

Published: Sun Jun 06 2021