Linked List in JavaScript

A linked list consists of a group of nodes which together represent a sequence.

Each node contains two things: the actual data being stored and and a pointer to the next node in the sequence.

In JavaScript, implementation is a little different than other languages. First we create a function, LinkedList. In JS we can add functions and properties inside functions, while using the this keyword to define scope. For a blank linked list, we’re going to want to set the length to 0, and the head element to null.

function LinkedList() {
var length = 0;
var head = null;
}

From here we want to create a variable Node, which we’re going to store in the linked list. In JS we can set a variable to a function, and once again define our scope with this. In addition, we’re going to need some getter methods for head and length.

var Node = function(element) {
this.element = element;
this.next = null;
}
this.head = function() {
return head;
}
this.length = function() {
return length;
}

The first method to implement would be an add method. What’s the goal? We want to put a new Node into the linked list. In order to do this we will have to start at the head node, and then traverse through each node’s next value until we find a null value. Once we find null, our node has found a home! Another piece of data I’ve updated too as well is the length value to increment the size of the linked list.

this.add = function(element) {
var newNode = new Node(element);

if(head === null) {
head = newNode;
} else {
var currentNode = head;
while(currentNode.next !== null) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}

length++;
}

Next method to implement would be a remove method. Here it starts to get a little tricky, we don’t want to lose half of our linked list when removing. What we need to do is first traverse through the linked list, find the node whose next value is the element we’re searching for, then make sure to set that node’s next value to its next next value. Once we lose the reference to the node we’re searching for, it’s gone. Forever.

this.remove = function(element){
if(head === null) {
return “empty linked list, nothing to remove”;
} else {
var currentNode = head;
if(currentNode.element === element){
head = currentNode.next;
length--;
return head;
} else {
while(currentNode.next !== null) {
if(currentNode.next.element === element){
currentNode.next = currentNode.next.next;
length--;
return head;
}
currentNode = currentNode.next;
}
}
}
}

The last method to implement would be to find a given node by it’s value and return it’s position. Same as before, traverse through the linked list, check to see if the element is what was given as a parameter, and if not increment a variable, “position”. Return position, and account for cases where the element is not in the list.

this.find = function(element) {
currentNode = head;
position = 1;
if(head === null){
return “empty linked linked list”;
} else {
if (currentNode.element === element) {
return position;
} else {
while(currentNode.element !== element){
currentNode = currentNode.next;
position++;
}
if (currentNode.element === element){
return position;
} else {
return -1;
}
}
}

Below is the Linked List all together, thanks for reading!