Linked Lists And Data Structures - What They Are And Why You Should Care.
A few months ago I was blissfully unaware of linked lists, data structures and algorithms. However, as my graduation from a web development bootcamp draws closer I know that they’ll be an important factor in determining the direction that my career path takes. If you’re considering a career in software development, or even looking to level up in your career, then this article is for you.
What Are Linked Lists And Data Structures?
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. — Wikipedia
So, what exactly does that mean? At the heart of computer science lay the concepts of data structures and algorithms. Data structures describes how information is organized and stored within a computer system, with the aim to structure it in a way where it can be accessed and manipulated as efficiently as possible.
An algorithm, as it relates to data structures, is a set of instructions that we provide to a computer in order to work with that data. Data structures come in many shapes and sizes, each having their own use cases, but the main forms are Linear, Hash, Tree and Graph. For this article, we’ll be focusing mostly on the Linear form and more specifically, linked lists.
Linked Lists — A Chain Of A Different Kind
It’s natural upon first hearing the term “linked list” to imagine a chain. In our everyday life, the chains we encounter are made up of contiguous links that hold fast to one another. In computer science, these chains have a beginning and end, referred to as the head and tail respectively (the tail can also refer to all the links following the head). However, these links — referred to as nodes — are not connected in any physical or spatial sense and act more like clues in a scavenger hunt, with each node pointing us towards the next and containing its own set of data.
In the case of a singly linked list, we’re only pointed in the direction of the next node, and unless you’ve been keeping track of where you’ve found previous nodes, we can only ever move forward. Each node offers no information about the others, other than where to find the next, and we can never be sure if we’ve found all the nodes we’re looking for until we find the last one and it tells us there are no more after it.
Doubly linked lists are much the same, except they point towards both the previous and next nodes, which allow us to travel forwards or backwards along the chain. Multiply linked lists are more like a choose your own adventure novel, with each node giving us multiple options about how we traverse the list which can act like an internal ordering mechanism. There are also circularly linked lists, with the “last” node pointing to the “first” (and vice versa in the case of doubly linked lists) and much like a snake swallowing its own tail, it raises some questions about where a circular list starts and ends.
Other types of linked lists are Stacks and Queues. Stacks operate on the LIFO principle (Last in, first out) and Queues on FIFO (First in, first out). This means that they limit their operations to elements only at the beginning or end of a list. Stacks use “push” and “pop” operations to add or remove items from the top of the stack, and Queues “enqueue” and “dequeue” elements from their respective ends. Everyday examples of these would be a stack of dishes, or a queue at the bank. Like a stack of dishes, or queue of people, it’s immediately apparent which dish is on the top, or who comes next in line and where to start lining up.
When you’re waiting in line, you may not know exactly when it will be your turn, but you certainly know it will be after the person in front of you and before the person behind you. In these cases, cutting in line is considered to be very rude, and you’re likely to receive immediate negative feedback. Just the same with a stack of dishes, it’s very easy to grab one off the top but if you try to take one from the middle, the whole thing will come crashing down.
Trade Offs
A major drawback for linked lists is that in order to retrieve data from a particular node, the list must always be traversed starting from one of the ends. This allows for quick access to the head or tail of a list, but poses a potential problem for nodes in the middle. In the worst case scenario, the data you are looking for will be on the opposite end of where you started, or not present at all, but every node still has to be checked. This means that nodes cannot be accessed out of turn. For very large datasets it can take a lot of time to find what you’re looking for, compared to something like a dynamic array or hash table that directly provides the addresses to find a particular node. The trade off that comes with slower retrieval, however, provides us with a much more efficient method for adding or removing nodes.
Like a chain, the process of adding or removing a node involves only cutting the bonds between two links and adding or removing any length of chain that is desired. What’s more, singly linked lists can even share the tail of another without any changes needed to the original list. The number of changes required varies between varieties of linked lists, but scales linearly with the size of the dataset.
Contrast that to something like a dynamic array or hash table, which is more like a knitted garment, where even a small change requires unravelling the entire structure and having to reassemble it afterwards.
At the end of the day, there are many different data structures to choose from, with each having its own particular strengths and weaknesses, but there is no one size fits all solution. Underpinning the foundation of our digital world sits an ever growing mass of data. As that data balloons to monumental proportions we need to arrange it in a way that allows us to make efficient use of it. We use technology to connect with the people around us, to find products and services and now more than ever for our jobs.
During the writing and research of this article I learned some new concepts, and I hope you did as well, or at the very least gained a new way of thinking about data structures.
