Skip to content

Instantly share code, notes, and snippets.

@JoeKarlsson
Last active November 6, 2023 03:43
Show Gist options
  • Save JoeKarlsson/86daa799e65f86d6919ff9f79dc27ba0 to your computer and use it in GitHub Desktop.
Save JoeKarlsson/86daa799e65f86d6919ff9f79dc27ba0 to your computer and use it in GitHub Desktop.
A linked list implemented using MongoDB documents
const MongoClient = require("mongodb").MongoClient;
class LinkedList {
constructor() {}
async init() {
const uri =
"ATLAS CLUSTER URL HERE";
this.client = new MongoClient(uri, {
useNewUrlParser: true,
useUnifiedTopology: true,
});
try {
await this.client.connect();
console.log("Connected correctly to server");
this.col = this.client.db("demos").collection("linked-list");
} catch (err) {
console.log(err.stack);
}
}
async getMeta() {
const meta = await this.col.find({ meta: true }).next();
return meta;
}
async resetMeta() {
await this.col.updateOne(
{ meta: true },
{ $set: { head: null, tail: null } },
{ upsert: true }
);
}
async resetData() {
await this.col.deleteMany({ value: { $exists: true } });
}
// points to our head
async getHeadID() {
const meta = await this.getMeta();
return meta.head;
}
async setHead(id) {
const result = await this.col.updateOne(
{ meta: true },
{ $set: { head: id } }
);
return result;
}
// points to our tail
async getTail(data) {
const meta = await this.getMeta();
return meta.tail;
}
async setTail(id) {
const result = await this.col.updateOne(
{ meta: true },
{ $set: { tail: id } }
);
return result;
}
// Create a new node
async newNode(value) {
const newNode = await this.col.insertOne({ value, next: null });
return newNode;
}
// Takes a new node and adds it to our linked list
async add(value) {
const result = await this.newNode(value);
const insertedId = result.insertedId;
// init empty LL
const head = await this.getHeadID();
if (head === null) {
this.setHead(insertedId);
} else {
// if it's not empty
const tailID = await this.getTail();
await this.col.updateOne({ _id: tailID }, { $set: { next: insertedId } });
}
// Happy Path
this.setTail(insertedId);
return result;
}
/**
* Reads through our list and returns the node we are looking for
* @param {[type]} index [description]
* @return {[type]} [description]
*/
async get(index) {
// If index is less than 0, return false
if (index <= -1) {
return false;
}
let headID = await this.getHeadID();
let postion = 0;
let currNode = await this.col.find({ _id: headID }).next();
// Loop through all the nodes
while (postion < index) {
// Check if we hit the end of the LL
if (currNode.next === null) {
return false;
}
// If node exists go to next node
currNode = await this.col.find({ _id: currNode.next }).next();
postion++;
}
return currNode;
}
/**
* reads through our list and removes desired node
* @param {[type]} index [description]
* @return {[type]} [description]
*/
async remove(index) {
const currNode = await this.get(index);
const prevNode = await this.get(index - 1);
// If index not in LL, return false
if (currNode === false) {
return false;
}
// If removing the head, reassign the head to the next node
if (index === 0) {
await this.setHead(currNode.next);
// If removing the tail, reassign the tail to the prevNode
} else if (currNode.next === null) {
await this.setTail(prevNode._id);
await this.col.updateOne(
{ _id: prevNode._id },
{ $set: { next: currNode.next } }
);
// Happy Path
} else {
await this.col.updateOne(
{ _id: prevNode._id },
{ $set: { next: currNode.next } }
);
}
await this.col.deleteOne({
_id: currNode._id,
});
return true;
}
/**
* Inserts a new node at the deisred index
* @param {[Num]} index
* @param {[*]} value
* @return {[Node]} node
*/
async insert(value, index) {
const currNode = await this.get(index);
const prevNode = await this.get(index - 1);
const result = await this.newNode(value);
const node = result.ops[0];
console.log(node, "node");
// If the index is not in the LL, return false
if (currNode === false) {
return false;
}
// If inserting at the head, reassign the head to the new node
if (index === 0) {
await this.setHead(node._id);
await this.col.updateOne(
{ _id: node._id },
{ $set: { next: currNode.next } }
);
} else {
// If inserting at the tail, reassign the tail
if (currNode.next === null) {
await this.setTail(node._id);
}
await this.col.updateOne(
{ _id: node._id },
{ $set: { next: currNode.next } }
);
await this.col.updateOne(
{ _id: prevNode._id },
{ $set: { next: node._id } }
);
}
return node;
}
}
(async function () {
try {
const linkedList = new LinkedList();
await linkedList.init();
linkedList.resetMeta();
linkedList.resetData();
await linkedList.add("Dog");
await linkedList.add("Turtle");
await linkedList.add("Cat");
await linkedList.add("Bird");
await linkedList.insert("Pig", 2);
} catch (err) {
console.log(err.stack);
}
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment