Skip to content

Instantly share code, notes, and snippets.

@nickangtc
Last active June 15, 2022 04:37
Show Gist options
  • Save nickangtc/086c6a9391ed150725cd05e007e7ff3d to your computer and use it in GitHub Desktop.
Save nickangtc/086c6a9391ed150725cd05e007e7ff3d to your computer and use it in GitHub Desktop.
Linked list in JavaScript
/**
* Read the original blog post for a detailed explanation!
* http://www.nickang.com/linked-list-explained-part-1/
* http://www.nickang.com/linked-list-implementation-part-2/
*/
/**
* Constructor functions
*/
function LinkedList() {
this.head = null;
this.tail = null;
}
function Node(value, next, prev) {
this.value = value;
this.next = next;
this.prev = prev;
}
/**
* Methods added to prototype chain
*/
LinkedList.prototype.addToHead = function(value) {
var newNode = new Node(value, this.head, null);
if (this.head) this.head.prev = newNode;
else this.tail = newNode;
this.head = newNode;
};
LinkedList.prototype.addToTail = function(value) {
var newNode = new Node(value, null, this.tail);
if (this.tail) this.tail.next = newNode;
else this.head = newNode;
this.tail = newNode;
};
LinkedList.prototype.removeFromHead = function() {
// empty list, return null
if (!this.head) return null;
var value = this.head.value;
// update head pointer to new head
this.head = this.head.next;
if (this.head) this.head.prev = null;
else this.tail = null; // linked list is empty
return value;
};
LinkedList.prototype.removeFromTail = function() {
if (!this.tail) return null;
var value = this.tail.value;
this.tail = this.tail.prev;
if (this.tail) this.tail.next = null;
else this.head = null;
return value;
}
LinkedList.prototype.search = function(searchValue) {
var currentNode = this.head;
while (currentNode) {
if (currentNode.value === searchValue) return currentNode;
currentNode = currentNode.next;
}
return null;
}
LinkedList.prototype.indexOf = function(searchValue) {
var currentNode = this.head;
var currentIndex = 0;
var indexes = [];
while (currentNode) {
if (currentNode.value === searchValue) indexes.push(currentIndex);
currentNode = currentNode.next;
currentIndex++;
}
return indexes;
}
var ll = new LinkedList();
ll.addToHead(10);
ll.addToTail(15);
ll.addToTail(99);
ll.addToTail(105);
ll.addToTail(40);
ll.addToTail(20);
ll.removeFromTail();
console.log('LOG: linked list object');
console.log(ll); // should show head as node with 10 and tail as node with 40
console.log('\nLOG: search for node with 99');
console.log(ll.search(99)); // should show node object with value 99
console.log('\nLOG: find indexOf node with 99');
console.log(ll.indexOf(99)); // should log [2]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment