Skip to content

Instantly share code, notes, and snippets.

@laras126
Last active January 4, 2021 01:29
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save laras126/8a057d19d0d4c724e73783b229874d10 to your computer and use it in GitHub Desktop.
Save laras126/8a057d19d0d4c724e73783b229874d10 to your computer and use it in GitHub Desktop.
Linked List in JavaScript
// You can run this code by downloading it and typing in your console: node linked-list.js
// See the accompanying blog post here:
// And all of this is an ES6 adaptation of this excellent tutorial bu Cho S. Kim on CodeTuts: https://code.tutsplus.com/articles/data-structures-with-javascript-singly-linked-list-and-doubly-linked-list--cms-23392
// Create the object prototype for a "Node", that is, a list item (note that there is no technical relation to node.js or a "Node" in terms of the DOM)
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Now create the prototype for the list that will hold references to the nodes
class SinglyList {
constructor(length = 0, head = null) {
// Underscores denote private variables and I don't entirely know how that's relevant here, but it was like that in the tutorial so whatever.
this._length = length;
this.head = head;
}
add(value) {
// Get initial list values
let length = this._length;
let currentNode = this.head;
// Create a new node
let newNode = new Node(value);
// Case 1: if nothing in list, create a node and set head to it
if( !currentNode ) {
this.head = newNode;
this._length++;
return newNode;
}
// Case 2: If the list is not empty (and implicitly has more than 1 item because only 2 or more items would have a currentNode.next)
while( currentNode.next ) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
this._length++;
return newNode;
}
selectNodeAt(position) {
let currentNode = this.head,
length = this._length,
count = 0,
message = {failure: "Non existent node in this list!"};
if(length === 0 || position < 0 || position > length) {
throw new Error(message.failure);
}
while (count < position) {
currentNode = currentNode.next;
count++;
}
return currentNode;
}
// Since we always operate on the head, this would remove the head
remove(position) {
let currentNode = this.head,
length = this._length,
count = 0,
message = {failure: "Failure, no node to delete"},
beforeToDelete = null,
nodeToDelete = null,
deletedNode = null;
// Case 1: Throw and error if there is no node
if(position < 0 || position > length) {
throw new Error(message.failure);
}
// Case 2: If it's the first node
if(position === 1) {
this.head = currentNode.next; // Head is now at node after the one to be deleted
deletedNode = currentNode;
currentNode = null;
this._length--;
return deletedNode;
}
// Case 3: Any other node is selected to removed
while(count < position) {
beforeToDelete = currentNode;
nodeToDelete = currentNode.next;
count++;
}
beforeToDelete.next = nodeToDelete.next;
deletedNode = nodeToDelete;
nodeToDelete = null;
this._length--;
return deletedNode;
}
}
// Test the list by creating one!
const list = new SinglyList();
list.add("hey");
list.add("ho");
list.add("hum");
list.add("bum");
list.remove(1); // Remove "hey"
// Note: We are printing the data of each node for readability's sake
console.log(list.head.data); // This should be "ho" since we have removed "hey"
console.log(list.selectNodeAt(1).data); // This will be "hum" since it is the first index after the head
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment