A Gentle Introduction to Linked Lists With MongoDB

1
{
2
   "data": "Cat",
3
   "next": null
4
}

1
{
2
   "data": "Cat",
3
   "next": {
4
      "data": "Dog",
5
      "next": {
6
         "data": "Bird",
7
         "next": null
8
      }
9
   } // these are really a reference to an object in memory
10
}

1
const MongoClient = require("mongodb").MongoClient;
2
3
// Define a new Linked List class
4
class LinkedList {
5
6
   constructor() {}
7
8
   // Since the constructor cannot be an asynchronous function,
9
   // we are going to create an async `init` function that connects to our MongoDB 
10
   // database.
11
   // Note: You will need to replace the URI here with the one
12
   // you get from your MongoDB Cluster. This is the same URI
13
   // that you used to connect the MongoDB VS Code plugin to our cluster.
14
   async init() {
15
      const uri = "PASTE YOUR ATLAS CLUSTER URL HERE";
16
      this.client = new MongoClient(uri, {
17
         useNewUrlParser: true,
18
         useUnifiedTopology: true,
19
      });
20
21
      try {
22
         await this.client.connect();
23
         console.log("Connected correctly to server");
24
         this.col = this.client
25
            .db("YOUR DATABASE NAME HERE")
26
            .collection("YOUR COLLECTION NAME HERE");
27
      } catch (err) {
28
         console.log(err.stack);
29
      }
30
   }
31
}
32
33
// We are going to create an immediately invoked function expression (IFEE)
34
// in order for us to immediately test and run the linked list class defined above.
35
(async function () {
36
   try {
37
      const linkedList = new LinkedList();
38
      await linkedList.init();
39
      linkedList.resetMeta();
40
      linkedList.resetData();
41
   } catch (err) {
42
      // Good programmers always handle their errors
43
      console.log(err.stack);
44
   }
45
})();

1
// This function will be responsible for cleaning up our metadata
2
// function everytime we reinitialize our app.
3
async resetMeta() {
4
   await this.col.updateOne(
5
      { meta: true },
6
      { $set: { head: null, tail: null } },
7
      { upsert: true }
8
   );
9
}
10
11
// Function to clean up all our Linked List data
12
async resetData() {
13
   await this.col.deleteMany({ value: { $exists: true } });
14
}

1
// This function will query our collection for our single
2
// meta data document. This document will be responsible
3
// for tracking the location of the head and tail documents
4
// in our Linked List.
5
async getMeta() {
6
   const meta = await this.col.find({ meta: true }).next();
7
   return meta;
8
}
9
10
// points to our head
11
async getHeadID() {
12
   const meta = await this.getMeta();
13
   return meta.head;
14
}
15
16
// Function allows us to update our head in the
17
// event that the head is changed
18
async setHead(id) {
19
   const result = await this.col.updateOne(
20
      { meta: true },
21
      { $set: { head: id } }
22
   );
23
   return result;
24
}
25
26
// points to our tail
27
async getTail(data) {
28
   const meta = await this.getMeta();
29
   return meta.tail;
30
}
31
32
// Function allows us to update our tail in the
33
// event that the tail is changed
34
async setTail(id) {
35
   const result = await this.col.updateOne(
36
      { meta: true },
37
      { $set: { tail: id } }
38
   );
39
   return result;
40
}
41
42
// Create a brand new linked list node
43
async newNode(value) {
44
   const newNode = await this.col.insertOne({ value, next: null });
45
   return newNode;
46
}

1
// Takes a new node and adds it to our linked lis
2
async add(value) {
3
   const result = await this.newNode(value);
4
   const insertedId = result.insertedId;
5
6
   // If the linked list is empty, we need to initialize an empty linked list
7
   const head = await this.getHeadID();
8
   if (head === null) {
9
      this.setHead(insertedId);
10
   } else {
11
      // if it's not empty, update the current tail's next to the new node
12
      const tailID = await this.getTail();
13
      await this.col.updateOne({ _id: tailID }, { $set: { next: insertedId } });
14
   }
15
   // Update your linked list to point tail to the new node
16
   this.setTail(insertedId);
17
   return result;
18
}

1
// Reads through our list and returns the node we are looking for
2
async get(index) {
3
   // If index is less than 0, return false
4
   if (index <= -1) {
5
      return false;
6
   }
7
   let headID = await this.getHeadID();
8
   let postion = 0;
9
   let currNode = await this.col.find({ _id: headID }).next();
10
11
   // Loop through the nodes starting from the head
12
   while (postion < index) {
13
      // Check if we hit the end of the linked list
14
      if (currNode.next === null) {
15
         return false;
16
      }
17
18
      // If another node exists go to next node
19
      currNode = await this.col.find({ _id: currNode.next }).next();
20
      postion++;
21
   }
22
   return currNode;
23
}

1
// reads through our list and removes desired node in the linked list
2
async remove(index) {
3
   const currNode = await this.get(index);
4
   const prevNode = await this.get(index - 1);
5
6
   // If index not in linked list, return false
7
   if (currNode === false) {
8
      return false;
9
   }
10
11
   // If removing the head, reassign the head to the next node
12
   if (index === 0) {
13
      await this.setHead(currNode.next);
14
15
   // If removing the tail, reassign the tail to the prevNode
16
   } else if (currNode.next === null) {
17
      await this.setTail(prevNode._id);
18
      await this.col.updateOne(
19
         { _id: prevNode._id },
20
         { $set: { next: currNode.next } }
21
      );
22
23
   // update previous node's next to point to the next node referenced by node to be deleted
24
   } else {
25
      await this.col.updateOne(
26
         { _id: prevNode._id },
27
         { $set: { next: currNode.next } }
28
      );
29
   }
30
31
   // Delete found node from memory
32
   await this.col.deleteOne({
33
      _id: currNode._id,
34
   });
35
36
   return true;
37
}

1
// Inserts a new node at the deisred index in the linked list
2
async insert(value, index) {
3
   const currNode = await this.get(index);
4
   const prevNode = await this.get(index - 1);
5
   const result = await this.newNode(value);
6
   const node = result.ops[0];
7
8
   // If the index is not in the linked list, return false
9
   if (currNode === false) {
10
      return false;
11
   }
12
13
   // If inserting at the head, reassign the head to the new node
14
   if (index === 0) {
15
      await this.setHead(node._id);
16
      await this.col.updateOne(
17
         { _id: node._id },
18
         { $set: { next: currNode.next } }
19
      );
20
   } else {
21
      // If inserting at the tail, reassign the tail
22
      if (currNode.next === null) {
23
         await this.setTail(node._id);
24
      }
25
26
      // Update the next property of the new node
27
      // to point to the node that the target node currently points to
28
      await this.col.updateOne(
29
         { _id: prevNode._id },
30
         { $set: { next: node._id } }
31
      );
32
33
      // Update the next property of the node you
34
      // want to insert after to point to the new node
35
      await this.col.updateOne(
36
         { _id: node._id },
37
         { $set: { next: currNode.next } }
38
      );
39
   }
40
   return node;
41
}