In this post, I will be implementing a linked list using javascript, and explain what is necessary for a linked list, and how each part of this linked list class is implemented.
Making the Node class
// User defined class node
class Node {
constructor(element)
{
this.element = element;
this.next = null
}
}
As mentioned in the previous post, nodes in a linked list contain two properties, the data and the reference to the next node. In this class, element is the property that holds the data and next holds the pointer to the next node.
Now we're gonna make a Linked List class, which will contain the pointer to the first node in the list, and the length/size of the list.
class LinkedList {
constructor()
{
this.head = null;
this.size = 0;
}
}
Add element
The class still needs some methods. We would like to add elements to the list, so let's go ahead and add that to the class.
add(element)
{
// creates a new node
var node = new Node(element);
// to store current node
var current;
// if list is Empty add the
// element and make it head
if (this.head == null)
this.head = node;
else {
current = this.head;
// iterate to the end of the
// list
while (current.next) {
current = current.next;
}
// add node
current.next = node;
}
this.size++;
}
This method will iterate through the entire list and add an element to the end of the list if it is not empty, otherwise the element will become the head of the list.
Inserting at a particular index
This next method is for inserting at a particular index.
insertAt(element, index)
{
if (index > 0 && index > this.size)
return false;
else {
// creates a new node
var node = new Node(element);
var curr, prev;
curr = this.head;
// add the element to the
// first index
if (index == 0) {
node.next = head;
this.head = node;
} else {
curr = this.head;
var it = 0;
// iterate over the list to find
// the position to insert
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// adding an element
node.next = curr;
prev.next = node;
}
this.size++;
}
}
The conditions we are considering are if the index is 0, greater than 0 but less than size - 1, and the last position of the list. If the index is 0, we add the element at the front of the list and make it head. If the index is between 0 and size - 1, then we will iterate through the list while keeping track of the current and previous nodes and eventually adding that element at the specified index. If the index is the last position, it will be appended at the end of the list.
Removing from a particular index
Next, we will put in removeFrom(index) which removes the element from the list at that index and returns it.
removeFrom(index)
{
if (index > 0 && index > this.size)
return -1;
else {
var curr, prev, it = 0;
curr = this.head;
prev = curr;
// deleting first element
if (index == = 0) {
this.head = curr.next;
} else {
// iterate over the list to the
// position to removce an element
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// remove the element
prev.next = curr.next;
}
this.size--;
// return the remove element
return curr.element;
}
}
Just as we added an element at a position in the list, we can remove from it the same way. In this method, we are taking into account whether the index is 0, if it is size - 1, or if it is between 0 and size - 1. If the index is 0, we remove the head and make the next node the head of the list. If it is size - 1, we remove the last element from the list and make the previous element the last element of the list. If it is between 0 and size - 1, then we remove the element by using the previous and current node, by making the previous node's next element the current node's next element.
Removing a particular element
Next we will create removeElement(element). This method removes element from the list. It returns the removed element, or if its not found it returns -1.
removeElement(element)
{
var current = this.head;
var prev = null;
// iterate over the list
while (current != null) {
// comparing element with current
// element if found then remove the
// and return true
if (current.element == = element) {
if (prev == null) {
this.head = current.next;
} else {
prev.next = current.next;
}
this.size--;
return current.element;
}
prev = current;
current = current.next;
}
return -1;
}
This method is just a slight modification from the last method, the only difference being it searches for a particular element rather than a particular index.
We've covered all of the core methods with transforming a linked list. Let's cover some helper methods that are useful with dealing with a linked list and helping provide information.
Finding index of element
indexOf(element)
{
var count = 0;
var current = this.head;
// iterate over the list
while (current != null) {
// compare each element of the list
// with given element
if (current.element == = element)
return count;
count++;
current = current.next;
}
// not found
return -1;
}
This method will take in an element, compare it with each element of the list, and return the index if found, or -1 if not found.
Is the list empty
isEmpty()
{
return this.size == 0;
}
This one checks if the list is empty by returning a boolean check with the list's size.
List size
size_of_list()
{
console.log(this.size);
}
This one just logs the size of the list.
Print the list
printList()
{
var curr = this.head;
var str = "";
while (curr) {
str += curr.element + " ";
curr = curr.next;
}
console.log(str);
}
This one prints out the whole list by iterating through it concatenating each element together with a space.
Top comments (0)