loading...

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

swarup260 profile image Swarup Das Updated on ・3 min read

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 push, insert and getElementAt methods. In this, I cover the remaining methods removeAt, remove, 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 :

Methods Complexity
indexOf O(n)
remove head element O(1)
remove any element(removeAt) O(n)

So, stay tuned for the next blog, in which I will cover another DS Doubly Linked List.

Posted on by:

Discussion

markdown guide