TIL: ArrayList vs LinkedList
Today I learned when you you would use ArrayLists vs LinkedLists in your code.
A few days back I had concluded one of my posts wondering if LinkedLists would behave any differently in code, or if they could just be swapped out for the ArrayLists I had already configured and “just work”.
After doing some more reading and playing around, it looks like the answer to that question is yes: they can just be swapped out. While
LinkedLists add in a few additional methods unique to them, there shouldn’t be any real issues for you to swap out the ArrayList with the LinkedList in your code and move on with your life. All of the differences between their implementations (indexing vs doubly-linked pointers) is handled behind the scenes for you.
But as I read on the question really seemed to be more of a should you use
ArrayLists in your code, rather than can you. As I read more into the topic I found that it’s actually a pretty heated discussion as to whether or not
LinkedLists have any real value at all.
Since they both behave more or less the same, it really boils down to performance. The following table shows the Big-O notation for the various operations that you would be performing between the two types of Lists:
|seek to back||O(1)||O(1)|
|seek to index||O(1)||O(N)|
|insert at front||O(N)||O(1)|
|insert at back||O(1)||O(1)|
|insert after an item||O(N)||O(1)|
Looking at this table it seems like
LinkedList has a lot of positives going for it. So why is it is it such a debatable implementation?
Well, unfortunately Big-O notation doesn’t really fit every scenario. It really depends on a lot of factors, like how many elements are in your List, what you’re going to be doing with your list, etc. These values might be true in the most extreme cases, but if you’re working with a list that only has 10-100 values in it, most of this is for naught anyways.
The argument FOR
LinkedList is due to it’s inserts and deletes, especially inserting at the beginning. Where as an
ArrayList will constantly need to manage the position of elements in the array (indexes),
LinkedList will just be updating the pointers.
There is also an issue with the amount of memory required for each of these kinds of Lists. While an ArrayList will take more memory initially up front, LinkedLists quickly grow much much larger in memory size compared to an ArrayList of equivalent size. This is something else to consider when you’re trying to decide which type of List is right for your implementation.
So why not use LinkedLists
From the arguments that I’ve read, it pretty much comes down to “If you think you need to use a LinkedList, there’s probably a better Collection you could be using”. I see a lot of mention regarding the different types of Queues should be preferred rather than trying to use a LinkedList for that purpose.
I still haven’t covered those kinds of Collections yet, so I can’t really comment on how I feel about this. Like most things, people have a very specific way that they’re used to doing their work and they become very passionate about it. That said, I have no reason not to believe it at this point.
It seems like 99% of the time and
ArrayList is going to be the correct List for the job, but it’s good to know that
LinkedList does serve some purpose. I’m just glad that I spent time looking into this before I went out and did an entire demo lesson specifically on
LinkedLists only to never touch them in practice.
Hopefully you found this useful and were able to learn something along with me.