4
\$\begingroup\$

I'm currently going over Robert Sedgewick Algorithms book. Here I'm implementing a Symbol Table using a Linked List. The Sequential Search Symbol table is implemented in JavaScript. The book mentiones that this Abstract Data Structure is not a good solution when dealing with big amounts of data.

I would like feedback on the implementation and on following JavaScript best practices. I'm coming from Ruby so having this implementation follow the best practices in JavaScript is a plus for me.

// Symbol Table using Sequential search (Linked List)
//
class SequentialSearchST {

  constructor() {
    this.first = null;
  }

  get(key) {
    for(let x = this.first; x != null; x = x.next) {
      if(x.key === key) {
        return x.val
      }
    }
    return null;
  }

  put(key, val) {
    for(let x = this.first; x != null; x = x.next) {
      if(x.key === key) {
        return x.val = val
      }
    }
    this.first = new Node(key, val, this.first);
  }

}

class Node {
  constructor(key, val, next) {
    this.key = key;
    this.val = val;
    this.next = next;
  }
}

st = new SequentialSearchST();
st.put('s', 0)
st.put('e', 1)
st.put('a', 2)
st.put('r', 3)
st.put('c', 4)
st.put('h', 5)
st.put('e', 6)
st.put('x', 7)
st.put('a', 9)
st.put('m', 10)
st.put('p', 11)
st.put('l', 12)
st.put('e', 13)
console.dir(st.get('s'));

\$\endgroup\$
1
  • \$\begingroup\$ You do know everything in JS is a dictionary, right? \$\endgroup\$ – FreezePhoenix Sep 24 '20 at 14:44
3
\$\begingroup\$

Naming

What you are implementing is a Symbol Table. How you implement the symbol table is nobody's business, it is a private internal implementation detail that nobody should need to care about.

Yet, your name is exactly the opposite: what your class actually is, is hidden behind an obscure acronym and tacked on at the end, whereas the part that I shouldn't even know about in the first place, screams at me from the front.

I would name the class SymbolTable:

class SymbolTable {
  // …
}

Triple equals

There are two places where you use the Abstract Equality Comparison Operator == or more precisely its negation !=. It is generally best if you forget about its existence and never use it.

Always use the Strict Equality Comparison Operator === or its negation !== instead.

Consistency

Sometimes you use the Abstract Equality Comparison Operator and sometimes the Strict Equality Comparison Operator. Sometimes you use semicolons and sometimes you don't.

Class fields

There is a stage-3 proposal for class fields. Whether you can use them or not depends on your environment. I personally quite like them. In this case, it allows us to get rid of the constructor.

class SymbolTable {
  first = null;

  get(key) {
    // …
  }

  put(key, val) {
    // …
  }
}

Private fields

There is a stage-3 proposal for private fields. Whether you can use them or not depends on your environment. I personally quite like them.

class SymbolTable {
  #first = null;

  get(key) {
    for(let x = this.#first; x !== null; x = x.next) {
      if(x.key === key) {
        return x.val
      }
    }
    return null;
  }

  put(key, val) {
    for(let x = this.#first; x !== null; x = x.next) {
      if(x.key === key) {
        return x.val = val
      }
    }
    this.#first = new Node(key, val, this.#first);
  }
}

You don't necessarily have to initialize them, they will default to undefined which arguably is "more correct" than null anyway in this case.

Data classes / records / structs

I agree with CertainPerformance that simple data classes / records / structs / whatever you want to call them are unnecessary in ECMAScript. In fact, confusingly, what ECMAScript calls an "object" is actually technically a record and not an object in the sense of "OOP". If you want an object in the sense of OOP, you use a function (more precisely, a closure).

So, for simple records, just use objects. There is no need for Node. IFF you want to keep Node, it would make sense to hide it inside SymbolTable, since it shouldn't be exposed to clients. Something like this:

class SymbolTable
  static #Node = class Node {
    key;
    val;
    next;

    constructor(key, val, next) {
      this.key = key;
      this.val = val;
      this.next = next;
    }
  };
}

Map

Note that the ECMAScript core library does contain a Map datatype which more or less does what you want already.

Also, since you are implementing a symbol table, the restriction that object keys can only be strings or symbols is not really much of a restriction, and you can simply use objects for your symbol tables.

I am assuming this is actually an exercise for implementing a linked list, and not an exercise about writing a compiler, though.

The Result

This is what it looks like, merging in also CaptainPerformance's improvement providing an iterator. I left the Node class in, just as an example, but normally, I would eliminate it and simply use an object, as in CaptainPerformance's answer.

class SymbolTable {
    #first;

    static #Node = class Node {
        key;
        val;
        next;

        constructor(key, val, next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    };

    *[Symbol.iterator]() {
        for (let node = this.#first; node; node = node.next) {
            yield node;
        }
    }

    get(key) {
        for (const node of this) {
            if (node.key === key) {
                return node.val;
            }
        }
    }

    put(key, val) {
        for (const node of this) {
            if (node.key === key) {
                node.val = val;
                return;
            }
        }

        this.#first = new SymbolTable.#Node(key, val, this.#first);
    }
}

const st = new SymbolTable();

st.put('s', 0);
st.put('e', 1);
st.put('a', 2);
st.put('r', 3);
st.put('c', 4);
st.put('h', 5);
st.put('e', 6);
st.put('x', 7);
st.put('a', 9);
st.put('m', 10);
st.put('p', 11);
st.put('l', 12);
st.put('e', 13);

console.dir(st.get('x'));

for (const { key, val } of st) {
    console.dir(`${key} : ${val}`);
}

Ruby

Compared to Ruby, two main differences stand out:

ECMAScript's core library is much smaller. (For example, there isn't even a way to get user input or generate output!) This is by design. ECMAScript is designed to be embedded into an application, and the core objects and operations are provided by that application. E.g. embedded into a web browser, the browser provides the DOM, with e.g the console.log method.

Object literals. Often, you don't need to create a class just so you can instantiate an object of the right shape. You can just write down the object you want. (See the nodes in CaptainPerformance's answer.)

\$\endgroup\$
1
  • \$\begingroup\$ in the sections Data classes / records / structs you used the static to declare #Node. In it you declare key, val, next without assigning it any value and then you declare those variables again inside the constructor. What is the name of this convention? Or is there specific reason as to why you did this? Would declaring them outside the constructor provides some functionality? \$\endgroup\$ – Steven Aguilar Sep 28 '20 at 11:58
4
\$\begingroup\$

Iterators When you have a data structure that needs to be iterated over sometime, consider providing an iterator to make things easier and more abstract for consumers. That is, you don't really want to write

for(let x = this.first; x != null; x = x.next) {

every time, nor would you want consumers of SequentialSearchST to have to do that if they wanted to examine the data manually. Instead, put an iterator on the class, and call that iterator by using for..of whenever needed.

class SequentialSearchST {
  *[Symbol.iterator]() {
    for (let node = this.first; node; node = node.next) {
      yield node;
    }
  }

Variable names x is not an informative variable name. Like I did above, maybe call a node node instead.

Semicolons Either use semicolons wherever appropriate, or don't use semicolons. Anything in-between looks inconsistent and can result in you eventually getting tripped up by the rules of Automatic Semicolon Insertion. If you're a beginner in JS, I'd highly recommend using semicolons. You can use a linter to enforce a particular style - to warn you of potential bugs before they turn into runtime errors that you need to spend time tracking down.

Declare your variables before using them. If you don't, you'll either implicitly create a global variable (an easy source of bugs), or an error will be thrown (in strict mode, and strict mode is recommended). Change

st = new SequentialSearchST();

to

const st = new SequentialSearchST();

Class usage A class is useful when you need to tie together data with methods that operate on that data. If you have only data, a class doesn't provide any benefit, and is simply noise, IMO. If I were you, I'd remove the Node class and change

this.first = new Node(key, val, this.first);

to

this.first = { key, val, next: this.first };

null Rather than assigning null as the initial value, and returning null when no matching node is found, you might consider if simply omitting a return statement entirely would do the trick. It's perfectly fine for a function call to return undefined; omitting null requires less code, less potential for inconsistencies, and one less thing to think about. (If this is for an exercise that requires null to be used, that's fine)

(If you do use null, make sure to verify it by using !== null, not != null; sloppy comparison requires more cognitive overhead than strict comparison)

This is how I'd refactor it:

class SequentialSearchST {
  *[Symbol.iterator]() {
    for (let node = this.first; node; node = node.next) {
      yield node;
    }
  }
  get(key) {
    for (const node of this) {
      if (node.key === key) {
        return node.val;
      }
    }
  }
  put(key, val) {
    for (const node of this) {
      if (node.key === key) {
        node.val = val;
        return;
      }
    }
    this.first = { key, val, next: this.first };
  }
}

const st = new SequentialSearchST();
st.put('s', 0)
st.put('e', 1)
st.put('a', 2)
st.put('r', 3)
st.put('c', 4)
st.put('h', 5)
st.put('e', 6)
st.put('x', 7)
st.put('a', 9)
st.put('m', 10)
st.put('p', 11)
st.put('l', 12)
st.put('e', 13)
console.dir(st.get('s'));

Another approach Maps hold key-value pairs. (Objects do too, but objects can only contain string and symbol keys, which is a limitation.) If this was a real-world problem I had to solve, I'd just use a Map:

const st = new Map();
st.set('s', 0)
st.set('e', 1)
st.set('a', 2)
st.set('r', 3)
st.set('c', 4)
st.set('h', 5)
st.set('e', 6)
st.set('x', 7)
st.set('a', 9)
st.set('m', 10)
st.set('p', 11)
st.set('l', 12)
st.set('e', 13)
console.dir(st.get('s'));

\$\endgroup\$
2
  • \$\begingroup\$ The fact that you can't override the subscript operator (well, at least not without using reflective proxies to completely intercept property access) is mightily annoying. It would be so much more natural to say st['m'] = 10. \$\endgroup\$ – Jörg W Mittag Sep 25 '20 at 10:45
  • \$\begingroup\$ "objects can only contain string and symbol keys, which is a limitation" – In general, yes, although in this case, we only need strings, since it's a symbol table. \$\endgroup\$ – Jörg W Mittag Sep 25 '20 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.