A Gentle Introduction to Linked Lists With MongoDB
Rate this tutorial
Are you new to data structures and algorithms? In this post, you will learn about one of the most important data structures in Computer Science, the Linked List, implemented with a MongoDB twist. This post will cover the fundamentals of the linked list data structure. It will also answer questions like, "How do linked lists differ from arrays?" and "What are the pros and cons of using a linked list?"
Did you know that linked lists are one of the foundational data structures in Computer Science? If you are like many devs that are self-taught or you graduated from a developer boot camp, then you might need a little lesson in how this data structure works. Or, if you're like me, you might need a refresher if it's been a couple of years since your last Computer Science lecture on data structures and algorithms. In this post, I will be walking through how to implement a linked list from scratch using Node.js and MongoDB. This is also a great place to start for getting a handle on the basics of MongoDB CRUD operations and this legendary data structure. Let's get started with the basics.
A linked list is a data structure that contains a list of nodes that are connected using references or pointers. A node is an object in memory. It usually contains at most two pieces of information, a data value, and a pointer to next node in the linked list. Linked lists also have separate pointer references to the head and the tail of the linked list. The head is the first node in the list, while the tail is the last object in the list.
A node that does NOT link to another node
A node that DOES link to another node
There are a lot of reasons why linked lists are used, as opposed to other data structures like arrays (more on that later). However, we use linked lists in situations where we don't know the exact size of the data structure but anticipate that the list could potentially grow to large sizes. Often, linked lists are used when we think that the data structure might grow larger than the available memory of the computer we are working with. Linked lists are also useful if we still need to preserve order AND anticipate that order will change over time.
Linked lists are just objects in memory. One object holds a reference to another object, or one node holds a pointer to the next node. In memory, a linked list looks like this:
- Linked lists are dynamic in nature, which allocates the memory when required.
- Insertion and deletion operations can be easily implemented.
- Stacks and queues can be easily executed using a linked list.
- Memory is wasted as pointers require extra memory for storage.
- No element can be accessed randomly; it has to access each node sequentially starting from the head.
- Reverse traversing is difficult in a singly linked list.
Now, you might be thinking that linked lists feel an awful lot like arrays, and you would be correct! They both keep track of a sequence of data, and they both can be iterated and looped over. Also, both data structures preserve sequence order. However, there are some key differences.
- Arrays are simple and easy to use.
- They offer faster access to elements (O(1) or constant time).
- They can access elements by any index without needing to iterate through the entire data set from the beginning.
- Did you know that arrays can waste memory? This is because typically, compilers will preallocate a sequential block of memory when a new array is created in order to make super speedy queries. Therefore, many of these preallocated memory blocks may be empty.
- Arrays have a fixed size. If the preallocated memory block is filled to capacity, the code compiler will allocate an even larger memory block, and it will need to copy the old array over to the new array memory block before new array operations can be performed. This can be expensive with both time and space.
- To insert an element at a given position, operation is complex. We may need to shift the existing elements to create vacancy to insert the new element at desired position.
A doubly linked list is the same as a singly linked list with the exception that each node also points to the previous node as well as the next node.
A circular linked list is the same as a singly linked list with the exception that there is no concept of a head or tail. All nodes point to the next node circularly. There is no true start to the circular linked list.
- Connect to a MongoDB or Atlas cluster, navigate through your databases and collections, get a quick overview of your schema, and see the documents in your collections.
- Create MongoDB Playgrounds, the fastest way to prototype CRUD operations and MongoDB commands.
- Quickly access the MongoDB Shell, to launch the MongoDB Shell from the command palette and quickly connect to the active cluster.
MongoDB for VS Code can connect to MongoDB standalone instances or clusters on MongoDB Atlas or self-hosted. Once connected, you can browse databases, collections, and read-only views directly from the tree view.
For each collection, you will see a list of sample documents and a quick overview of the schema. This is very useful as a reference while writing queries and aggregations.
Once installed, there will be a new MongoDB tab that we can use to add our connections by clicking "Add Connection." If you've used MongoDB Compass before, then the form should be familiar. You can enter your connection details in the form or use a connection string. I went with the latter, as my database is hosted on MongoDB Atlas.
To obtain your connection string, navigate to your "Clusters" page and select "Connect."
Choose the "Connect using MongoDB Compass" option and copy the connection string. Make sure to add your username and password in their respective places before entering the string in VS Code.
Once you've connected successfully, you should see an alert. At this point, you can explore the data in your cluster, as well as your schemas.
Alright, now that we have been able to connect to our MongoDB Atlas database, let's write some code to allow our linked list to connect to our database and to do some cleaning while we are developing our linked list.
The general strategy for building our linked lists with MongoDB will be as follows. We are going to use a MongoDB document to keep track of meta information, like the head and tail location. We will also use a unique MongoDB document for each node in our linked list. We will be using the unique IDs that are automatically generated by MongoDB to simulate a pointer. So the next value of each linked list node will store the ID of the next node in the linked list. That way, we will be able to iterate through our Linked List.
So, in order to accomplish this, the first thing that we are going to do is set up our linked list class.
Next, let's create some helper functions to reset our DB every time we run the code so our data doesn't become cluttered with old data.
Now, let's write some helper functions to help us query and update our meta document.
The steps to add a new node to a linked list are:
- Add a new node to the current tail.
- Update the current tails next to the new node.
- Update your linked list to point tail to the new node.
In order to traverse a linked list, we must start at the beginning of the linked list, also known as the head. Then, we follow each next pointer reference until we come to the end of the linked list, or the node we are looking for. It can be implemented by using the following steps:
- Start at the head node of your linked list.
- Check if the value matches what you're searching for. If found, return that node.
- If not found, move to the next node via the current node's next property.
- Repeat until next is null (tail/end of list).
Now, let's say we want to remove a node in our linked list. In order to do this, we must again keep track of the previous node so that we can update the previous node's next pointer reference to the node that is being deleted next value is pointing to. Or to put it another way:
- Find the node you are searching for and keep track of the previous node.
- When found, update the previous nodes next to point to the next node referenced by the node to be deleted.
- Delete the found node from memory.
The following code inserts a node after an existing node in a singly linked list. Inserting a new node before an existing one cannot be done directly; instead, one must keep track of the previous node and insert a new node after it. We can do that by following these steps:
- Find the position/node in your linked list where you want to insert your new node after.
- Update the next property of the new node to point to the node that the target node currently points to.
- Update the next property of the node you want to insert after to point to the new node.
Many developers want to learn the fundamental Computer Science data structures and algorithms or get a refresher on them. In this author's humble opinion, the best way to learn data structures is by implementing them on your own. This exercise is a great way to learn data structures as well as learn the fundamentals of MongoDB CRUD operations.
If you want to learn more about linked lists and MongoDB, be sure to check out these resources.
Check out the following resources for more information: