When first learning about Computer Science, arrays were one of the first things that I learned about. For the longest time, I had no idea what a linked list was. Linked lists are pretty important though, and if you are a serious student of the Computer Sciences then they are definitely worth learning about. So let’s learn about linked lists!
What is an Array?
Before we delve too deeply into the realm of the linked list, let’s make sure that we are on the same page when it comes to arrays. There are similarities and differences between arrays and linked lists, so it is important to have a solid understanding of both.
First, let’s take a look at an array:
Each item in an array is referred to as a data element. The array above has four data elements. The number of data elements stored in an array is known as the size of the array. The data elements in an array are assigned values known as the index. The index values are the numbers in blue on top of the boxes above. The first element in an array is stored at index 0 and the last one at index size-1.
Storing to Memory
When an array is created, it needs a certain amount of memory. In our example array pictured above, let’s say that each data element required 1 byte of memory. So 4 bytes of memory in total would be required to create that array. Those 4 bytes of memory have to all be in one place — all in one contiguous block of memory.
The same cannot be said for linked lists. Let’s say that there is also a linked list that takes up 4 bytes of memory. Those 4 bytes do not have to all be stored in one contiguous block of memory.
This is the most fundamental difference between arrays and linked lists. Arrays are static data structures and linked lists are dynamic data structures.
At the time of creation, the amount of memory that a static data structure will require needs to be declared. A static data structure is incapable of growing or shrinking in size. If elements need to be added or removed from a static data structure, then it first needs to be copied to a new static data structure that has the appropriate amount of memory to accommodate the desired changes. This process would have to be performed every time that a static data structure needs to grow or shrink in size.
As you can see, because an array is a static data structure, it might not be the best choice if data elements need to be frequently added or removed.
If data elements need to be frequently added or removed then perhaps a linked list would be a better option. Linked lists, being dynamic data structures, do not need a specific amount of memory to be declared at the time of creation. Also the amount of memory that it uses is able to change as well.
So now we know about arrays and we know the fundamental difference between arrays and linked lists. But, we don’t know much about linked lists. Sounds like a good time to learn more about linked lists!
What is a Linked List?
A linked list is structured a lot like an array, in that it is a linear data structure. So that picture above of the array is a lot like what a linked list looks like. There are a few differences though.
For starters, a linked list starts with a head and it ends with null. Also every data element in a linked list is referred to as a node. Each node is comprised of data and a pointer. The data is the information that a node contains and a pointer simply provides the directions to the next node.
Now here comes another fundamental difference between arrays and linked lists. While arrays have index values and their size is known, this is not the case with linked lists. In linked lists, nodes aren’t indexed and the size of the linked list isn’t known. While this is a good thing if we need a data structure that needs to be flexible in its size, it is a bad thing if we need to find a specific node in a linked list.
The only way that we can find a specific node is if the entire linked list is traversed. That means going from one node to the next. We might get lucky and the node we are looking for might be at the beginning, but what if it is at the end? That might not be a problem if the linked list is small, but what if it is big? Finding a node in a large linked list can be a timely endeavor, and time is money.
So far, this post has only described sinlgy linked lists. It should be noted that are some other types of linked lists in the world of Computer Science. Although, we won’t be discussing them in much detail, it should be noted that there are also doubly linked lists and circular linked lists.
Arrays vs Linked Lists
As mentioned earlier, a linked list is a great option if data elements need to frequently be added or removed. However, it might not be so great of an option when it comes to looking for a single node. The node can be be towards the end of the linked list and the linked list might be quite large.
Let’s put all of the pros and cons of arrays and linked lists in one place.
Arrays
Pros
Because of indexes, searching is fast.
Good option if the size of the data structure is known and isn’t likely to change.
Cons
- Because the array is a static data structure, adding and removing data elements is a slow process.
Linked Lists
Pros
It is a dynamic data structure, so adding and removing nodes is a fast process.
Good option if it is not known how much memory will be required and if the size of the data structure is likely to change.
Cons
- Searching can be a slow process. The nodes aren’t indexed, so to find a specific node may require traversal of the linked list.
Well there you have it! That’s the story of linked lists and arrays. When I first started writing this post, I thought that I would only be describing linked lists. However, the more that I started writing, the more I realized that it only makes sense to include arrays in the discussion as well.
Thanks for reading! Hope that it was helpful!
Top comments (0)