Learn The Basics Of A Linked List Data Structure
Chances are, in the giant world of computer science and software development, you will stumble across something called a linked list data structure, whether it be implemented in your future company’s software, or if it’s the topic of a question in your upcoming coding interview. If like me, you’re relatively new to coding and software development you may be thinking “I barely even know what a data structure is let alone a Linked List data structure.”
Hopefully, by the end of this short article, your curiosity for learning about data structures will be piqued and you’ll understand the basics of a linked list data structure.
What’s a Data Structure?
Before we can comprehend the details of a linked list we must understand what a data structure is. Although at first this term can be intimidating and overwhelming, in its simplest form a data structure is fundamentally a method or scheme to assist in the organization of data. With our organized data we can use algorithms to interact with these data structures.
The topic of data structures boils down into two types, linear data structures, which include arrays, linked lists, and stacks, as well as hierarchical data structures which include trees, graphs, and heaps. For this article, we will be focusing on linear data structures. A linear data structure is when the data elements are sequentially attached to the previous and subsequent elements.
What’s a Linked List?
Now, let’s take a shallow dive into the details of a linked list. A linked list is a linear storage method that can structure many data elements. Each element is contained as a node(a basic unit of a data structure). The nodes have a pointer, or also known as a link, that can reference the “next“ node in the sequence. Using the pointer to access nodes, we can implement algorithms to traverse through the linked list.
Each linked list has a head that represents the starting point of the list, and a tail whose pointer references the value null if the “next” node is nonexistent.
Another way to visualize this if you’re familiar with other programming languages is to picture how arrays are traversed using the index of the elements.
//JS syntax
const array = [1, 2, 3]array[0] // outputs => 1
array[array.length-1] // outputs => 3
But, in comparison to how arrays in other programming languages function, with linked lists, you don’t have random access available to all elements as you must sequentially iterate through the list.
A unique feature of linked lists is how they’re stored into memory. Although a linked list is a linear data structure, each node could have different physical locations in memory. Unlike most data structures, the nodes of a linked list point to the subsequent node so they don’t physically have to be touching or be next to each other.
What problem do they solve?
You might be thinking, why were they created and what problem did they solve? The history of linked lists dates back to the mid-1950s when Allen Newell, Cliff Shaw, and Herbert A. Simon created them for their Information Procession Language.
Memory used to be very expensive and there was not an excessive amount of it because computers were much less developed. Computers would be packed to capacity when creating data structures that reserved a certain amount of memory. For example, dynamic arrays would allocate all elements in contiguous memory, meaning that the elements would share the same border, and if the space within the dynamic array was exceeded, it would have to be reallocated which was an expensive operation.
The solution was linked lists, a data structure that can spread out in memory since each node can point to the next node and a data structure that only uses the necessary amount of memory by adding and removing from the tail.
Analogy Time!
Using an analogy to hammer down this point, say you’re at a corporate event and you’re looking for someone named Jack but you don’t know anyone at this event.
Let’s imagine that you have all of the confidence in the world and ask the first person you see saying “Are you, Jack?” And that person says “No. But go over to that person in the blue shirt.” You do the same thing and ask, “Are you, Jack?” The Lady says “No go over to the person with the grey suit,” and this process repeats until Jack has been found.
To offer an observation, linked lists appear to be a simple structure, but they would be repetitive, especially if you frequently need to iterate through a long list. This is certainly true because nodes are only available through sequential access. Different variations of linked lists were created to patch this problem. For example, the doubly linked list can traverse through the list forwards and backward, presenting more access to nodes.
To understand the details of the different types of linked lists, a more in-depth explanation would be required. Linked lists will always be relevant but like any other data structure, they have their pros and cons. You never know if a question concerning linked lists will show up in a coding interview so it will never hurt to be more prepared.
Conclusion
With the world of technology being so vast, there is always the possibility that you’ll be exposed to this data structure. You now know that a linked list is a data structure that uses nodes and pointers to access the “next” node in a sequence. These nodes are not stored in contiguous memory locations so this allows for efficient insertion and removal of elements. Of course, this raises the issue of more difficult element access.
You received a small introduction into data structures but I hope that this triggers some curiosity to learn more about them.
- Data Structure Fundamentals: https://cs-fundamentals.com/data-structures/introduction-to-data-structures#:~:text=Data%20structures%20can%20be%20broadly,its%20own%20strengths%2C%20and%20weaknesses.
- Linked Lists in Javascript: https://humanwhocodes.com/blog/2019/01/computer-science-in-javascript-linked-list/
- Linked Lists: https://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays
