webdev: (Default)
[personal profile] webdev
Continuing with the series of JavaScript interview questions, here's the next one: given a singly-linked list, delete every entry that has a given value.

This is a great interview question because it tests out the applicant's knowledge of linked lists, which is one of the most basic of data structures. JavaScript of course has no implementation of linked lists, so solving this problem will basically mean implementing a linked list from scratch.

A singly linked list basically is a list of entries, where each entry has a value and a pointer to the next entry. In JavaScript, this is super easy to imagine:
var linkedList = {
    value: 1,
    next: null
}

linkedList.next = {
    value: 2,
    next: null;
}

linkedList.next.next = {
    value: 3,
    next: null;
}

Or, to put it in literal notation:
var linkedList = {
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3,
            next: null
        }
    }
}

Each node has a value and a pointer to the next node. In the last node, the next node is null. Very simple.

Based on this, let's create a simple implementation of a singly linked list in JavaScript. In our case, we will want the class to have the following properties:

  • A public length property, to show how many elements are in the list

  • A public pointer to the first element, called firstNode

  • A public pointer to the last element, called lastNode


and the following methods:

  • getSize, which will return the length of the list

  • addNode, which will add a node with the specified value to the end of the list

  • toString, which will present a delimted list of all values. Default delimiter will be a comma, but can be specified as a parameter

  • removeNode, which will remove all nodes with a specified value from the list and return true if any were found and deleted, or false if not. (This is where most of the work for answering the question will go.)


function SinglyLinkedList() {
    this.firstNode = null;
    this.lastNode = null;
    this.size = 0;

    // Get the size of the list, super-simple: just return this.size
    this.getSize = function() {
        return this.size;
    }

    // Add a node to the list
    this.addNode = function(newVal) {

        // First, create the node
        var newNode = {
            data: newVal,
            next: null
        }

        // If there are no other nodes, then this is the first node
        if (this.firstNode == null) {
            this.firstNode = newNode;
            this.lastNode = newNode;
        } else {
            // Not the first node, so tack it on to the end of the list
            this.lastNode.next = newNode;
            this.lastNode = newNode;
        }

        // Increment size
        this.size++;
    }
    
    // toString method: create a comma-delimited list of values
    this.toString = function(strDelimiter) {
        var currentNode = this.firstNode,
            i = 0,
            strResult = "{";

        // Provide a default delimiter if none was specified.
        if (typeof(strDelimiter) === "undefined") {
            strDelimiter = ","
        }

        // Loop through the list and concatenate all values
        for( i = 0; currentNode != null; i++) {
            if(i > 0) {
                strResult += strDelimiter;
            }
            var dataObject = currentNode.data;

            strResult += (dataObject == null ? "" : dataObject);
            currentNode = currentNode.next;
        }
        strResult += "}";

        return strResult;
    }

    // Remove a node from the list with a given data value
    // Returns true if the value was successfully found and deleted, false if not.
    this.removeNode = function(targetVal) {
        // Are there even any nodes?
        if (this.size === 0) {
            return false;
        }

        // Traverse the list and look for targetVal.
        var currentNode = this.firstNode,
            previousNode = null,
            wasDeleted = false;

        // Check for the edge cases around deleting the first node in the list
        if (targetVal === currentNode.data) {
            
            // One possible edge case is that this is the only node in the list,
            // in which case we just need to reset the list and return.
            if (currentNode.next == null) {
                this.firstNode.data = null;
                this.firstNode = null;
                this.lastNode = null;
                this.size = 0;
                return true;
            }

            // The other possible edge case is that we are deleting the first node
            // in the list, but there are still other nodes to search.
            currentNode.data = null;
            currentNode = currentNode.next;
            this.firstNode = currentNode;
            this.size--;
            wasDeleted = true;
        }

        // Loop through all the remaining nodes and look for values to delete
        currentNode = this.firstNode;
        while (true) {
            if (currentNode == null) {
                // We're done.  Break out of the loop.
                break;
            } else {
                if (targetVal === currentNode.data) {
                    // Found one!
                    // To get rid of this node, just get the next one and
                    // set currentNode to it.
                    var nextNode = currentNode.next;
                    if (nextNode != null) {
                        currentNode.data = nextNode.data;
                        currentNode.next = nextNode.next;
                    } else {
                        // Edge case: Deleting last entry in list.
                        currentNode.data = null;
                        if (previousNode != null) {
                            previousNode.next = null;
                        } else {
                            // Edge case: turns out this was a linked list with multiple entries of targetValue,
                            // and we just deleted the last one.
                            // Reset the list and return.
                            this.firstNode = null;
                            this.lastNode = null;
                            this.size = 0;
                            return true;
                        }
                        this.lastNode = currentNode;
                    }
                    wasDeleted = true;
                    this.size--;
                } else {
                    // Move on to the next node.
                    previousNode = currentNode;
                    currentNode = currentNode.next;
                }
            }
       }
       // Looping all done.  Return result.
       return wasDeleted;
    }
}

Now all you have to do is create a new linked list using that constructor:
var llNumbers = new SinglyLinkedList();
llNumbers.addNode(5);
llNumbers.addNode(5);
console.log(llNumbers.toString()); // Will output {5,5} to console
console.log(llNumbers.removeNode(5)); // Will output true to console
console.log(llNumbers.removeNode(5)); // Will output false to console
console.log(llNumbers.toString()); // Will output {} to console
llNumbers.addNode(1);
llNumbers.addNode(2);
llNumbers.addNode(3);
llNumbers.addNode(4);
console.log(llNumbers.toString()); // Will output {1,2,3,4} to console
console.log(llNumbers.removeNode(4)); // Will output true to console
console.log(llNumbers.removeNode(4)); // Will output false to console
console.log(llNumbers.toString()); // Will output {1,2,3} to console

And there you have it.