Basic Linked List Class in JavaScript to be used to support Stack operations (push/pop), later versions to support Queue operations

0 - JavaScript (ES6) Singly Linked List Class.md

The file 1-list.js below shows how to declare a OO-style class in JavaScript.

Note that the only things assigned to properties of this are anonymous functions. These are the "methods" of the class that access "private" properties. JavaScript doesn't have the keyword private like some other languages. Instead, the "private data members" of a class are the local variables and parameters of the class constructor. Most JavaScript code in the wild doesn't attempt to make anything "private" which is just bad OO design. Here, the "methods" are functions nested inside the constructor to give them access to the constructors local variables.

Typical JavaScript code you see in the wild would have placed the methods as properties of List.prototype which allows for OO-like method invocation syntax using the instance as an implicit first argument named this, but is really semantically equivalent to using a Java static method that takes the instance as an explicit first argument like List.pop(List list). A static method in Java doesn't have access to private data members of the instance, which isn't a problem if you have made all the data members public. Instead of nesting the code for front in the constructor, we could have gotten the same functionality by (with less efficiency) by inserting code between the } at the end of the constructor and the } at the end of the class something like

    front() {
        var top=this.pop();
        this.push(top);
        return top;
    }

In ES5, this would have been code like

     List.prototype.front = function() {...};

Both of these constructs are essentially like Java code

    static <T> T front(List<T> list) {
        T top=list.pop();
        list.push(top);
        return top;
    }

However, in JavaScript we can say var s = list.front() whereas the equivalent in Java would be String s = List<String>.front(list)

The capitalization convention in JavaScript, as in Java, is to give classes capitalized names, but to give functions, methods, variables, and such camelCase names.

In ES6, the syntax is more "Java-like" than in ES5 where the class constructor is a function with a capitalized name so rather than being class List { constructor() { ... } } ES5 would have function List() { ... }

Note that there is no need for a class Node and we simply use object literals to construct the "Node" objects. In fact, the only real need for using the a class is if we want to subclass it or use its prototype property. We could have defined something essentially equivalent like

    function newList() {
        var head = null;
        var tail = null;
        var _length = 0;
        return {
            push: function(item) {
               ...
            },
            
            front: function() {...},
            
            back: funcition() {...}
            
            ...
        };
    }

1-list.js

"use strict";
　
class List {
    constructor() {
        var head = null;
        var tail = null;
        var _length = 0;
　
        this.push = function(item) {
            var node = {data: item, next:head};
            head = node;
            if (tail === null) {
                tail=head;
            }
            _length++;
        };
　
        this.front = function() {return head.data;};
        this.back = function() {return tail.data;};
        this.isEmpty = function() {return head===null;};
        this.length = function() {return _length;};
        
        this.pop = function() {
            var result = head.data;
            _length--;
            head = head.next;
            if (head === null) {
                tail = null;
            }
            return result;
        }
        
        this.dequeue = this.pop;
        
        this.enqueue = function(item) {
            var node = {data: item, next: null};
            _length++;
            if (tail === null) {
                head = node;
            } else {
                tail.next = node;
            }
            tail = node;
        }
     }
  }

2-Getters.md

Rather than making front and back "methods," we could have made them "properties" so that when they were used, no () will be needed:

    class List {
        constructor() {
        ...
        this._front = function() {return head.data;};
        ....
        }
        
        get front() {
            return this._front();
        }
    }
    
    var list = new List();
    list.push(1);
    var one = list.front

This is called "getter" or a "computed property" in some other languages such as C#, which uses similar syntax for this kind of thing. This example is a bit silly, but suppose we had class Point with public numeric data members x and y, then one could have something like get magnitude() {return Math.sqrt(this.x*this.x + this.y*this.y);}. Note the use of the keyword this in the definition of the getter: the getter is defined outside the constructor, so cannot access the "private" local variables of the constructor. Hence, we provided a public method for the getter to call, just so () could be avoided in normal use.

3-Setters.md

Rather than use a push method, and requiring putting something on the "top" of a stack to use syntax like s.push(1), we can provide a "setter" method to allow something like s.top = 1 to do the same thing. Just as with a "getter" we define the "setter" in the {} inside the class definition, but after the {} of the constructor definition with a defition like:

    set top(value) {
        this.push(value);
    }

Again, note that "setters" can rely only on the "public" parts of a class, so must access the parts of the class they belong to via the this keyword. They enable alternate usage syntax, but do not provide special access to the "private" parts of a class.

4-Iterators.md

A for..in loop lets one access the valid indices of an array:

    for(val i in array) {
        console.log(array[i]);
    }

Similarly, a for..of loop lets one access the values in index order, so for similar functionality one coude have:

    for(val a of array) {
        console.log(a);
    }

JavaScript has the notion of an "Iterator" which is an objects with a method named "next" which in turn return objects with a boolean property named "done" and a property named "value" which will be undefined when "done" is true. So, if it were an iterator we could have a loop like:

    var i = it.next();
    while (!i.done) {
        ...  i.value ...
        i = it.next();
    }

Like Java, JavaScript has the notion of an "Iterable" which is an object which has a standard mechanism for delivering an iterator that iterates over the elements of a collection-like class. In Java, the mechanism is to have a method called "iterator." In JavaScript, the method has a non-string name, so rather than defining it as the value of this.iterator which would be equivalent to this["iterator"] the somewhat odd way of accessing the method that returns an iterator is this[Symbol.iterator]. The problem was that this feature was added to the language and the language designers didn't want to break existing code which already may have had methods with the name "iterator." For "collection" classes use this mechanism, one can iterate over the elements in the collection with code that looks just like the code that iterates over the elements of an Array:

     for (item of collection) {
         console.log(item)
     }

The function nested inside the constructor for a List to do this would be pretty ugly, something like:

    this[Symbol.iterator] = function() {
        var node = head;
        return {
            next: function() {
                var oldNode = node;
                node = node ? node.next : node;
                return {
                    value: oldNode!=null ? oldNode.data : undefined,
                    done: oldNode==null
                }
            }
        }
    }

However, ES6 provides "generator" functions that simplify the sytax of doing this sort of thing so you don't have to write code for a function that returns an object with a method named next that is a function that returns an object of the right form. Instead of using the return keyword, such functions use the yield keyword. Instead of using the function keyword, such functions use the keyword function*, and for our List class, would look like:

    this[Symbol.iterator] = function*() {
        for (var node=head; node!=null; node=node.next) {
            yield node.data;
        }
    }

Such code in our class allows us to do more than just do loops like:

    for(var item of list) {
        console.log(item);
    }

This enables a whole category of methods that behave like methods of the Array class that iterate over elements and return an Array such as map(f), filter(p), and reduce(combine, initialValue) which are typical of collections in "functional" languages. In the case of this List class, methods such as map and filter will return another instance of the List class. The important thing in such situations is to return an instance of a class that supports the same set of methods, so that one can chain them with code such as the following (which computes the sum of the squares of the positive numbers in an array):

      [1, 2, -1, 3].filter( x => x > 0 ).map( x => x*x ).reduce( (a,x) => a+x, 0)

The "arrow" functions used here are esentially shorthand for:

      function(x){return x>0;}  // a function that returns a boolean, often called a "predicate"
      function(x){return x*x;}
      function(a,x){return a+x;}  // a is an "accumulator" with an initial value provided by "initialValue",
                                  // the second argument to reduce
                                  // if initialValue is missing, it will have the value "undefined" in which
                                  // case it will be replaced by the first element of the collection

Note that the 0 was not needed in the above example as the second argument for reduce, so if I wanted to find the maximum value in a collection instead of using reduce( (a,x) => a+x), I could use reduce( (a,x) => Math.max(a+x), Number.NEGATIVE_INFINITY) or just reduce( (a,x) => Math.max(a,x))

If I wanted to convert a List to an array, I should be able to use something like list.reduce( (a,x) => a.concat([x]), [])

If I wanted to give List a method like the "join" method of an array, it could look something like

      join(sep) {
          return this.reduce( (a, x) => a+sep+x );
      }

5-list.js

"use strict";
　
class List {
    constructor() {
        var head = null;
        var tail = null;
        var _length = 0;
　
        this.push = function(item) {
            var node = {data: item, next:head};
            head = node;
            if (tail === null) {
                tail=head;
            }
            _length++;
        };
　
        this.front = function() {return head.data;};
        this.back = function() {return tail.data;};
        this.isEmpty = function() {return head===null;};
        this.length = function() {return _length;};
        
        this.pop = function() {
            var result = head.data;
            _length--;
            head = head.next;
            if (head === null) {
                tail = null;
            }
            return result;
        }
　
        this.dequeue = this.pop;
      
        this.enqueue = function(item) {
            var node = {data: item, next: null};
            _length++;
            if (tail === null) {
                head = node;
            } else {
                tail.next = node;
            }
            tail = node;
        }
　
        this.map =  function (f) {
            var list = new List();
            for (var node=head; node; node=node.next) {
                list.push(f(node.data));
            }
            return list;
        }
　
        this.filter =  function (p) {
            var list = new List();
            for (var node=head; node; node=node.next) {
                if (p(node.data)) {
                    list.push(node.data);
                }
            }
            return list;
        }
　
        this.every = function(p) {
            for (var node=head; node; node=node.next) {
                if (!p(node.data)) {
                    return false;
                }
            }
            return true;
        }
　
        this.reduce = function(combine, initialValue) {
            var node = head;
            var accum = initialValue;
            if (initialValue == undefined) {
                accum = node.data;
                node = node.next;
            }
            for (; node; node=node.next) {
                accum = combine(accum, node.data);
            }
            return accum;
        }
　
        // secret sauce to make the List clas conform to the Iterable protocol
        this[Symbol.iterator] = function*() {
            for (var node=head; node; node=node.next) yield node.data;
        }
            
    }
}
　
var list = new List();
list.push(1);
console.log("front=", list.front(), " back=", list.back());
list.push(2);
console.log("front=", list.front(), " back=", list.back());
for (let x of list.map((x=>2*x)))
    console.log(x);
console.log("pop=", list.pop());
console.log("pop=", list.pop());
list.unshift(1);
console.log("front=", list.front(), " back=", list.back());
list.unshift(2);
console.log("front=", list.front(), " back=", list.back());
for (let x of list.filter((x=>x%2==0)))
    console.log(x);
console.log(list.every(x=>x%2==0));
console.log(list.reduce((a,x)=>a+x));