Last active
January 4, 2021 01:29
-
-
Save laras126/8a057d19d0d4c724e73783b229874d10 to your computer and use it in GitHub Desktop.
Linked List in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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