Array List vs Linked List | Which one should you use??

so the other day I was doing some analysis on linked lists and ArrayList and I found some very interesting results and I thought it would be really helpful and beneficial to make a video on it so my name is Sam this is the keep on coding channel let's get into it now a lot of people who are new to programming or haven't studied data structure as much often make the mistake of using the wrong data structure for what they're trying to do and by wrong I don't mean that it won't work everything will still work but they're not using the strengths of specific data structures and I'm using array lists because they're probably the most commonly used data structure in Java and most other languages that do have the concept of Lists whether it be Python or C++ so it feel like this will be helpful to everyone so I want to go over a brief diagram about how linked lists and array lists work internally now if you already feel comfortable with how these work internally I will leave a timestamp here so you can just jump to that for the actual analysis but I do highly recommend that you watch the diagrams so let's first take a look at array lists basically an ArrayList is an array that can grow in size so initially let's say we have an ArrayList and what it does internally is it just allocates an array so let's say initially the array is of size four we have four elements three seven nine and four and then the ten eleven twelve and thirteen referred to the memory address of the array so in a normal array say we wanted to add the number five well we couldn't because our array is now full so what an ArrayList does is it basically just adds it but what we can't do is we can't just add a five onto here and that's because an ArrayList initially allocated an array of size four so I've memory address 14 there could be something else that's occupying this space so we can't use it so when an array lists array gets full it allocates a new bigger array it takes the size of the original array which is four and it multiplies it by 1.5 so now it finds a chunk of memory that's size six so now in turn the program has found a new chunk of memory at address 40 that's of size 6 so the first thing it does is it copies the existing elements over and now it has allocated space to add that number 5 and say we added another element here and say we want to add something more it does the same thing it says ok this is size 6 multiply it by 1 point 5 find a new chunk of memory of size 9 one thing to note is that you can also delete from an ArrayList but say we deleted a few numbers it doesn't actually shrink the array it just keeps whatever size that it's currently on so let's talk about these strengths of an ArrayList well say we want to retrieve a specific element from this list so say we want to get the one two three fourth element of the list which happens to be number four it basically takes this address here and says ok I need to go forward four spaces so it basically can directly access this number one of the weaknesses of an array is deleting something from the middle so say we wanted to delete this element well what needs to happen is that it needs to shift everything that's on the right over by one so it takes this five it needs to put it here takes two seven and needs to put it here which is fine in this example but what if we have an ArrayList of a hundred thousand elements it's gonna need to do that a hundred thousand times which is very very time-consuming and the same thing happens when you want to insert something in the middle it needs to shift everything to the right over by one all right so now let's talk about linked lists linked lists are another form of Lists but they're not stored contiguously in memory so say again we had a list with four elements so now as you can see these four elements are stored in different memory locations but they have a pointer that points to the next element so now say we wanted to delete this seven here we don't need to shift anything over so now say we wanted to delete an element in the middle like this seven we don't need to do any shifting all we're gonna do is we need to take this pointer from five and point it over to 10 and this seven will get deleted once the garbage collector runs or in some languages like C++ you'll have to manually delete it so if we go back to the code here we see that we have an ArrayList and a linked list and what we're doing here is we are looping through 10,000 times and we're just adding elements to these lists the next thing we want to do is we want to retrieve a specific element from each of these lists and what we want to do is we want to time both of these methods so we're gonna get the time before it starts and the time after it ends for both functions and then we're gonna take the end time and we're gonna subtract it by the start time and we're gonna store it in a variable called total time and finally we're just gonna print out the total time so if we go ahead and run that we see that the total execution time of the ArrayList is much smaller because remember how we were talking about how if we want to grab something from an ArrayList it just directly can go index that number so that's why the ArrayList time is a lot faster all right so now let's go ahead and change these gets to remove and let's do something a little bit closer to the middle of the list let's do well let's do exactly in the middle and let's remove the element at index 5,000 so removing the element at lists 5,000 in the list as well as the ArrayList now if we go ahead and run that we actually see that the ArrayList is still much faster at removing elements which is very interesting now the reason that this is happening is because the linked lists can't directly go to that index that is deleting it has to iterate all the way till it gets to the element and then it can remove it whereas in the ArrayList it can go directly to the element deleted but it still does have to shift elements over but as we can see in this example it didn't take that big of a hit to do that but let's go ahead and let's make this list from ten thousand let's make it a million elements and see if that makes a difference so now we want to remove element 500,000 and remove ArrayList element 500,000 so if we go ahead and run that we see that again we see that again the ArrayList is a lot faster but let's try and remove the first element so the linked list will directly get it and just delete it whereas the ArrayList will delete the first element and it'll have to shift everything over so if we change index to one and we go ahead and run that now we see the linked list executed a lot faster than the ArrayList so as you can see depending on your use case and if you know that you're gonna be removing a lot from the beginning of the list it'd be more useful to use a linked list otherwise it would be more useful to use an ArrayList so as I was mentioning before a new programmer or someone who's not as familiar with data structures and algorithms might make the mistake of just using an ArrayList always even if they're doing inserts and deletes when in fact we just saw that a linked list would be more efficient for larger list sizes so I hope you guys found that video interesting let me know if you would like me to do more analysis like this on different data structures but other than that I hope you guys enjoyed the video see you guys in the next one and happy coding [Music] you [Music]

Channel: Keep On Coding

Views: 29,306

Rating: 4.9615154 out of 5

Keywords: arraylist in java, linked list, linkedlist, arraylist vs linkedlist, linked list in java, arraylist, java arraylist, java linked list

Id: M_0q6rGUsNc

Length: 7min 56sec (476 seconds)

Published: Wed Apr 29 2020