Data Structures & Algorithms 101: Linked Lists
Welcome back! I wanted to continue my discussion on data structures and algorithms and discuss Linked Lists! They are one of the basic structures in data structures and algorithms that you may encounter in a technical interview! When I first came across linked lists, I had a bit of trouble understanding how to implement them, but I hope this blog will help you grasp the concept a bit quicker.
What are Linked Lists and Why are They Important
Linked lists are linear data structures that have similarities to arrays in that they are ordered collections of data elements. However, linked lists are different in how they are stored in memory. Unlike arrays, the elements in a linked list are not stored in contiguous memory, they are instead separate objects (nodes) that contain the data stored and a link (pointer) to the next object in the list. The link to the next node is why the data structure is called a linked list. The first node or entry point to a linked list is known as a head and the last node in the list will always have a pointer that points to “null”. Below is a diagram that illustrates the concept of a linked list.
The linked list is an important data structure to learn about because depending on the situation, they may be more beneficial to use over an array when storing data. One main example where a linked list would be more useful than an array is if the size of the data is dynamic and needs to change at runtime. Since arrays can only be stored in contiguous blocks of memory, its size cannot be altered at runtime and you would need to create a new array each time you added or deleted data elements. However, since linked lists have a pointer, each node points to the next which means that each element can be placed anywhere in memory without needing to create a whole new collection of data. Thus, linked lists are often preferred over arrays when the size of the data elements is unknown and nodes need to be easily removed or added without reorganizing the entire data structure.
Types of Linked Lists
There are three types of linked lists, Singly Linked Lists (which we discussed above), Doubly Linked Lists, Circular Linked Lists. I will describe each one below.
Singly Linked List: A singly linked list is where each node only contains one pointer to the following node. This type of node is what we have talked about thus far.
Doubly Linked List: The doubly linked list is where each node contains two pointers, one which points to the next node and another that points to the previous node. The two pointers are what gives it the name “doubly” linked list.
Circular Linked List: A circular linked list is a linked list where the last node points back to the first node or any other node before it. Unlike the other linked lists, the last node of a circular linked list has a pointer that points to a previous node, thereby forming a loop (circular).
For the rest of the blog though, I will be discussing and working with Singly Linked Lists primarily.
How do we Implement Linked Lists in JavaScript
First let’s start by creating two classes, one for a Linked List and the other for a List Node. The Linked List will have a constructor method that will initialize the head of the linked list. If the head node is not passed, the head will automatically initialize to “null”.
Once the LinkedList class is created, we’ll create a class for each node in the linked list. The node class will include a constructor with two items, the data and the pointer.
Now let’s put everything together and create a linked list with list nodes! We’ll start by creating two list nodes, node1 and node2, which will hold data 2 and 5. Then we will set a pointer from node1 to node2.
Now that we’ve created list nodes, let’s create a linked list and place node1 as out head.
Once the new linked list is created, we can access the nodes on the list we just created!
We are also able to add another node to node2 by creating a new list node and setting node2’s pointer to it. We can continue doing this as much as we want. We can also remove nodes by reassigning pointers to a different node.
Conclusion
I hope this weeks Data Structures 101 was a helpful resource for you to understand Linked Lists. I know it took me some time to understand them, but when you practice using them, they are not very difficult. They are very useful when you have an unknown amount of data and want to save memory, but they are not extremely common otherwise. Due to the nodes having both data and a pointer, linked lists actually take up more memory than arrays. Regardless, they are an important data structures to have in your tool box and can come in handy for technical interviews. I’m glad you joined me to learn about Linked Lists and I hope to see you back here next week!