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.

Blog

Implementation of Linked Lists

Daniel Zaltsman