Data Structures & Algorithms in JavaScript(Single Linked List) Part 2


Hello Everyone, this is part 5.2 in the series of blogs about data structures and algorithms in JavaScript, In the previous blog, I had covered the linked list's pushinsert and getElementAt methods. In this, I cover the remaining methods removeAtremove, and indexOf.


Implementation of linked list in Javascript

IndexOf

This method will return the index of the given element if exists else return -1 ({4}) . To find the index of the element, we will start with the head element ({1}) and loop until the element is found ({2}) and returns its index ({3}) .

   indexOf(element) {
        let current = this.head; //1
        for (let index = 0; index < this.count && current != null; index++) {
            if (current.element == element) { //2
                return index;
            }
            current = current.next; //3
        }
        return -1; //4
    }

RemoveAt

Remove an element at the specified index, we first check if the linked list is empty else return undefined ({1}) ,After that we valid the index's out of bound error, by check is the index, greater than zero and less than count.
  • We want to remove the first element i.e index equal to zero ({2}), shift the head to the next node. We will refer to the first element of the list using the current variable. If we assign head to current's next, we will remove the first element ({3}).
Remove head node from linked list
  • We want to remove the last element or an element from the linked list, we will use getElementAt method to get the one previous element using index -1 ({4}), current will be previous's next ({5}). So, to remove the current node, all we have do is to link the previous.next to current.next ({6}).
Remove any node from linked list



   removeAt(index) {
        if (this.isEmpty()) {
            return undefined; //1
        }        
        if (index >= 0 && index < this.count) {

            let current = this.head
            if (index == 0) { // 2
                this.head = current.next;  //3 
            } else {
                let previous = this.getElementAt(index - 1);  //4               
                current = previous.next; //5
                previous.next = current.next; //6
            }
            this.count--;
            return current.element;
        }
        return undefined;
    }


Remove

To remove an element, we check if the linked list is not empty.
If not then get the index of the element using the indexOf method if the index is -1 then the element doesn't exist else use the index and remove the element from the linked list using removeAt method.

   remove(element) {
        if (this.isEmpty()) {
            return undefined;
        }
        let index = this.indexOf(element);
        if (index != -1) {
            this.removeAt(index);
        }
        return undefined;
    }



you get the full source here

Conclusion :

MethodsComplexity
indexOfO(n)
remove head elementO(1)
remove any element(removeAt)O(n)
So, stay tuned for the next blog, in which I will cover another DS Doubly Linked List.
Data Structures & Algorithms in JavaScript(Single Linked List) Part 2 Data Structures & Algorithms in JavaScript(Single Linked List) Part 2 Reviewed by RS Coder on April 22, 2020 Rating: 5

No comments:

Powered by Blogger.