A question that often comes to mind for any programmer, is how to organize the data in your program. There are plenty of ways to organize data, but it’s important to understand the fundamentals of each structure to figure out what is the best way to organize the data for a specific problem. In this article, I'll be diving into one of the most common data structures in computer science known as a linked list.
Real-life applications of a linked list
To understand what a linked list is, here are a few real-life applications of this data structure.
- Web browsing history: This is a good tech application of a linked list. You can navigate this list through the “back” and “forward” buttons.
- Music playlist: navigating your Spotify playlist with the next and back buttons, is also an example of a linked list traversal.
- Trains: Although not necessarily tech-related, trains are a great way to think about a linked list if you’re looking for a tangible representation. Each cart is connected together in a linear fashion which you can traverse sequentially. You can also insert, and remove different carts in the train sequence.
What is a linked list?
To put it simply, A linked list is a collection of data that are connected together in a linear fashion. Each “element” or “node” of the list consists of the following:
- Some data value (this can be any data type!)
- A pointer/reference to the next node
The starting point of the list has a reference to the first node and is commonly known as the head. The end of the list is referenced by a node that points towards a null or an empty value.
Linked lists are linear data structures by nature, which means when we go through the items of a linked list, we do it sequentially from the beginning to the end. There is always a single item that a node in a linked list is connected to and the order matters.
When compared to non-linear data structures like a hash table (different keys can map to different values, does not have to be traversed sequentially) this can point to some obvious benefits/drawbacks to a linked list. More on this later.
A linked list is also known as a dynamic data structure. In simple terms, this means it can grow, shrink and change in memory and does not need all its resources to be allocated all at once before the creation of the data structure. An array must have a continuous block of memory, while a linked list can have all its nodes scattered within memory, but still be connected in a linear fashion through the pointers/references of each node.
If you’re primarily a programmer in a language such as JavaScript or Python which deals with memory allocation for us, we may take this fact for granted. However, dynamic memory allocation relates to one of the many benefits of a linked list.
Why use Linked Lists?
At this point, you may be wondering why you should use a linked list in comparison to something like an array.
Advantages:
Better Memory Usage: Because the memory is dynamically allocated for a linked list, they are viewed as more efficient because the size is not predefined. Making it easier to change a linked list throughout your program.
To better highlight this example let's make a comparison to an array. With an array when you add or delete elements because the memory allocation is already fixed, it’ll need to set a new block of memory for the array. However, if you delete an item from a linked list, it could just be a matter of rearranging the pointers. Memory usage is also optimized for a linked list, for example, if you declare an array with size eight, and it only stored four data elements, then four “blocks” of memory would be wasted. With a linked list, only the memory used is allocated.
Fast insertion and deletion time: In an array, elements must be shifted when you make insertions or deletions. However, as seen in the example above, insertions and deletions to the beginning and end of linked lists are a matter of changing the pointer reference. This makes these operations extremely fast which is a major benefit of linked lists.
The fundamental basis for other complex data structures: Linked lists are also the basis of implementation in other data structures such as stacks and queues. I won’t go into too much detail about this as I want to focus on linked lists as the primary data structure. but more can be read about this here.
Disadvantages:
Slower Search Times: To search for items in a linked list, we must traverse the array sequentially through each item starting from the beginning of the list. If the item you’re looking for is near the end of the linked list, then you will have to traverse through every element before that. Thus, this search must happen in linear time.
No Random Access: In comparison to arrays, which are indexed, Arrays also have the benefit of random access based on the index, in a linked list we do not have this luxury so to access a data element we must traverse through the list sequentially, whereas an array you can pass a reference to the index to extract the data from the element.
More On Linked Lists Types
There are also various types of data structures for a linked list. I will go over each of these briefly, however, a great explanation of each can be found in this article here.
- Single linked list: This is the linked list type we explored in this article. There is only a single direction for traversal, and we start from a single head and travel until the very last node where we get a pointer to a null value.
- Double linked list: The key difference between a single and doubly linked list is that there is a pointer in both the forward and reverse directions for each node. This can be helpful when we want to traverse backward in a linked list. However, the drawback is an additional pointer for each node takes up more memory.
- Circular linked list: This type of linked list is a variation where the pointers are a little different. Instead of the last element pointing to a null element, the last item points towards the first item of the linked list.
Conclusion
Linked lists are one of the most common and essential data structures in computer science. They are comprised of nodes that have a data value and a pointer to the next node. These are linear and dynamic data structures by design and have useful implementations where you may need to dynamically insert or delete data within your program with memory efficiency.
However, like with all data structures, they have some drawbacks, primarily with search times and a lack of random access.
Feel free to check out some of the resources below I used as a reference, and for additional reading.
Resources
What’s a Linked List, Anyway? [Part 1] by Vaidehi Joshi, 2017
A Beginner’s Guide to Linked Lists by Connor Finnegan, 2019
What is a linked list? from Edspresso
How to Implement a Linked List In JavaScript by Sarah Chima Atuonwu, 2020
Data Structures: Linked Lists Video from HackerRank, 2016