EventGet 50% off your ticket to MongoDB.local NYC on May 2. Use code Web50!Learn more >>
MongoDB Developer
JavaScript
plus
Sign in to follow topics
MongoDB Developer Centerchevron-right
Developer Topicschevron-right
Languageschevron-right
JavaScriptchevron-right

A Gentle Introduction to Linked Lists With MongoDB

Joe Karlsson13 min read • Published Jan 18, 2022 • Updated Sep 23, 2022
MongoDBJavaScript
Facebook Icontwitter iconlinkedin icon
Rate this tutorial
star-empty
star-empty
star-empty
star-empty
star-empty
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?"

Intro to Linked Lists

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.
Diagram of a singly linked list
Diagram of a singly linked list
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

Why Use a Linked List?

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:
Diagram that demonstrates how linked lists allocate use pointers to link data in memory
Diagram that demonstrates how linked lists allocate use pointers to link data in memory

Advantages of Linked Lists

  • 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.

Disadvantages of Linked Lists

  • 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.

Comparison Between Arrays and Linked Lists

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.

Advantages of Arrays

  • 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.

Disadvantages of Arrays

  • 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.
Diagram that demonstrates how arrays allocate continuous blocks of memory space
Diagram that demonstrates how arrays allocate continuous blocks of memory space
Diagram that demonstrates how linked lists allocate memory for new linked list nodes
Diagram that demonstrates how linked lists allocate memory for new linked list nodes
  • 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.

Other Types of Linked Lists

Doubly Linked List

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.
Diagram of a doubly linked list
Diagram of a doubly linked list

Circular Linked List

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.
Diagram of a circular linked list
Diagram of a circular linked list

Let's Code A Linked List!

First, Let's Set Up Our Coding Environment

Creating A Cluster On Atlas

First thing we will need to set up is a MongoDB Atlas account. And don't worry, you can create an M0 MongoDB Atlas cluster for free. No credit card is required to get started! To get up and running with a free M0 cluster, follow the MongoDB Atlas Getting Started guide.
After signing up for Atlas, we will then need to deploy a free MongoDB cluster. Note, you will need to add a rule to allow the IP address of the computer we are connecting to MongoDB Atlas Custer too, and you will need to create a database user before you are able to connect to your new cluster. These are security features that are put in place to make sure bad actors cannot access your database.
If you have any issues connecting or setting up your free MongoDB Atlas cluster, be sure to check out the MongoDB Community Forums to get help.

Connect to VS Code MongoDB Plugin

Next, we are going to connect to our new MongoDB Atlas database cluster using the Visual Studio Code MongoDB Plugin. The MongoDB extension allow us to:
  • 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.
To install MongoDB for VS Code, simply search for it in the Extensions list directly inside VS Code or head to the "MongoDB for VS Code" homepage in the VS Code Marketplace.
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.

Creating Functions to Initialize the App

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.

Add A Node

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.

Find A 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).

Delete A Node

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.
Diagram that demonstrates how linked lists remove a node from a linked list by moving pointer references
Diagram that demonstrates how linked lists remove a node from a linked list by moving pointer references

Insert A Node

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.
Diagram that demonstrates how a linked list inserts a new node by moving pointer references
Diagram that demonstrates how a linked list inserts a new node by moving pointer references

Summary

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.
When you're ready to implement your own linked list in MongoDB, check out MongoDB Atlas, MongoDB's fully managed database-as-a-service. Atlas is the easiest way to get started with MongoDB and has a generous, forever-free tier.
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:

Facebook Icontwitter iconlinkedin icon
Rate this tutorial
star-empty
star-empty
star-empty
star-empty
star-empty
Related
Tutorial

Manage Game User Profiles with MongoDB, Phaser, and JavaScript


Feb 03, 2023 | 11 min read
Tutorial

MongoDB Atlas Vector Search and AWS Bedrock modules RAG tutorial


Feb 20, 2024 | 10 min read
Tutorial

Demystifying Stored Procedures in MongoDB


Feb 27, 2024 | 6 min read
Article

Realm Meetup - Realm JavaScript for React Native Applications


Mar 21, 2023 | 32 min read
Table of Contents