In today´s article, you will learn the basics of Lists, the differences between them and arrays, and when to use which one. Then we will dive into some common operations we want to do with them to understand the pros and cons.
What is a List?
A list is a collection of elements.
That´s an abstract definition that would also fit arrays and any other data structure that contains several items. To make it more concrete we are going to be talking specifically about Linked Lists. A Linked List is a dynamic ordered collection of elements. Each item in the list contains the data for said item and a pointer to the next element. These are usually called nodes too.
And why would we need this? Well, as I said before, Linked Lists are dynamic, which means they can grow and shrink without limitations (virtually). And that solves one of the big challenges we had with Arrays. When we were working with Arrays we needed to define the size of the array we needed on instantiation time. We don´t have to care about that when creating and working with a list, and that is GREAT! But there is a price to pay. Let’s take a look at the pros and cons of working with arrays versus lists.
Lists vs Arrays
Arrays are great when you are certain about the maximum amount of items you are going to be handling, but ALSO you know you will be using a fair amount of the slots you allocate at creation time. Let´s assume you know you won´t ever have more than 1000 items in your carsForSale array. If so, on creation time you would allocate an array for 1000 cars. After that, if your program only uses 5 of those 1000 cars guess what? You still allocated 1000 slots for cars in memory. So not only do you need to worry about the top limit but also making sure that you don´t over-allocate memory, otherwise you are wasting resources.
Lists on the other hand are way more flexible. You only allocate what you need, each time you have a new node you add it and fill the pointer (memory direction) into the previous item to point to this new item and you are done. You can scale as much as you want (as long as there is memory available) and you don´t care about how many items you are using because you didn´t preallocate any resources.
So far Lists looks like a clear winner. But the problem is on the usage. Remember that an array is a clump of memory together and because of that, you have direct access using an index. Well, we don´t have that on Lists. On a linked list to get to the 4th element we have to go from the first one, then use the pointer to get to the second, use the pointer to get to the third, and finally use the pointer to get to the item we want. Now it doesn´t sound so good right? As usual, there is no perfect solution, just tradeoffs on each option and we have to pick what suits our use case better.
Let´s take a look at what happens for insertions:
When inserting at the end (provided that the array has space) there is no problem for both structures. On the list side we would just modify the pointer of the last item to point to the new element and we are done. And on the array we would have to just add the value at the last position used index + 1.
Now what is interesting is what happens when we want to add in the middle (order matters in this scenario). For the List we just need to find the position we want our new node to be in and change the pointer of the previous node to the new one and make the new one point to the next item, pretty cool ha?. Well… for the array this is a tad bit more complicated. We would have to move all the items from the position we want to insert into and forward down 1 position and then we can insert our new item in the now available space. This can be problematic and very expensive to do depending on amount of items needed to move.
I want to leave to you the exercise of thinking and even drawing the scenarios for adding at the beginning (very similar to add in the middle, easier for list, harder for array) and removing items from both structures!
To close up this article lets recap, a List is a dynamic data structure that will be more flexible but harder to use. And depending on the circumstances, can perform better and avoid wasting resources or perform worse than an Array. What is important is for you to understand the difference between static and dynamic structures because you will need this knowledge to build into more complex data structures and algorithms.