NCZOnline - The Official Web Site of Nicholas C. Zakas

Subscribe to NCZOnline - The Official Web Site of Nicholas C. Zakas feed
The Official Web Site of Nicholas C. Zakas
Updated: 2 hours 20 min ago

Computer science in JavaScript: Doubly linked lists

Mon, 02/04/2019 - 19:00

In my previous post, I discussed creating a singly linked list in JavaScript (if you haven’t yet read that post, I suggest doing so now). A single linked list consists of nodes that each have a single pointer to the next node in the list. Singly linked lists often require traversal of the entire list for operations, and as such, have generally poor performance. One way to improve the performance of linked lists is to add a second pointer on each node that points to the previous node in the list. A linked list whose nodes point to both the previous and next nodes is called a doubly linked list.

The design of a doubly linked list

Similar to a singly linked list, a doubly linked list is made up of a series of nodes. Each node contains some data as well as a pointer to the next node in the list and a pointer to the previous node. Here is a simple representation in JavaScript:

class DoublyLinkedListNode { constructor(data) { this.data = data; this.next = null; this.previous = null; } }

In the DoublyLinkedListNode class, the data property contains the value the linked list item should store, the next property is a pointer to the next item in the list, and the previous property is a pointer to the previous item in the list. Both the next and previous pointers start out as null because the next and previous nodes aren’t known at the time the class is instantiated. You can then create a doubly linked list using the DoublyLinkedListNode class like this:

// create the first node const head = new DoublyLinkedListNode(12); // add a second node const secondNode = new DoublyLinkedListNode(99); head.next = secondNode; secondNode.previous = head; // add a third node const thirdNode = new DoublyLinkedListNode(37); secondNode.next = thirdNode; thirdNode.previous = secondNode; const tail = thirdNode;

As with a singly linked list, the first node in a doubly linked list is called the head. The second and third nodes are assigned by using both the next and previous pointers on each node. The following image shows the resulting data structure.

You can traverse a doubly linked list in the same way as a singly linked list by following the next pointer on each node, such as:

let current = head; while (current !== null) { console.log(current.data); current = current.next; }

Doubly linked list also typically track the last node in the list, called the tail. The tail of the list is useful to track both for easier insertion of new nodes and to search from the back of the list to the front. To do so, you start at the tail and follow the previous links until there are no more nodes. The following code prints out each value in the doubly linked in reverse:

let current = tail; while (current !== null) { console.log(current.data); current = current.previous; }

This ability to go backwards and forwards through a doubly linked list provides an advantage over a singly linked list by allowing searches in both directions.

The DoublyLinkedList class

As with a singly linked list, the operations for manipulating nodes in a doubly linked list are best encapsulated in a class. Here is a simple example:

const head = Symbol("head"); const tail = Symbol("tail"); class DoublyLinkedList { constructor() { this[head] = null; this[tail] = null; } }

The DoublyLinkedList class represents a doubly linked list and will contain methods for interacting with the data it contains. There are two symbol properties, head and tail, to track the first and last nodes in the list, respectively. As with the singly linked list, the head and tail are not intended to be accessed from outside the class.

Adding new data to the list

Adding an item to a doubly linked list is very similar to adding to a singly linked list. In both data structures, you must first find the last node in the list and then add a new node after it. In a singly linked list you had to traverse the entire list to find the last node whereas in a doubly linked list the last node is tracked using the this[tail] property. Here is the add() method for the DoublyLinkedList class:

class DoublyLinkedList { constructor() { this[head] = null; this[tail] = null; } add(data) { // create the new node and place the data in it const newNode = new DoublyLinkedListNode(data); // special case: no nodes in the list yet if (this[head] === null) { this[head] = newNode; } else { // link the current tail and new tail this[tail].next = newNode; newNode.previous = this[tail]; } // reassign the tail to be the new node this[tail] = newNode; } }

The add() method for the doubly linked list accepts one argument, the data to insert into the list. If the list is empty (both this[head] and this[tail] are null) then the new node is assigned to this[head]. If the list is not empty, then a new node is added after the current this[tail] node. The last step is to set this[tail] to be newNode because in both an empty and non-empty list the new node will always be the last node.

Notice that in the case of an empty list, this[head] and this[tail] are set to the same node. That’s because the single node in a one-node list is both the first and the last node in that list. Keeping proper track of the list tail is important so the list can be traversed in reverse if necessary.

The complexity of this add() method is O(1). For both an empty and a non-empty list, the operation doesn’t require any traversal and so is much less complex than add() for the singly linked list where only the list head was tracked.

Retrieving data from the list

The get() method for a doubly linked list is exactly the same as the get() method for a singly linked list. In both cases, you must traverse the list starting from this[head] and track how many nodes have been seen to determine when the correct node is reached:

class DoublyLinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this[head]; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } } }

To reiterate from the singly linked list post, the complexity of the get() method ranges from O(1) when removing the first node (no traversal is needed) to O(n) when removing the last node (traversing the entire list is required).

Removing data from a doubly linked list

The algorithm for removing data from a doubly linked list is essentially the same as with a singly linked list: first traverse the data structure to find the node in the given position (same algorithm as get()) and then remove it from the list. The only significant differences from the algorithm used in a singly linked list are:

  1. There is no need for a previous variable to track one node back in the loop because the previous node is always available through current.previous.
  2. You need to watch for changes to the last node in the list to ensure that this[tail] remains correct.

Otherwise, the remove() method looks very similar to that of the singly linked list:

class DoublyLinkedList { // other methods hidden for clarity remove(index) { // special cases: no nodes in the list or `index` is negative if ((this[head] === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // store the data from the current head const data = this[head].data; // just replace the head with the next node in the list this[head] = this[head].next; // special case: there was only one node, so also reset `this[tail]` if (this[head] === null) { this[tail] = null; } else { this[head].previous = null; } // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this[head]; // used to track how deep into the list you are let i = 0; // same loop as in `get()` while ((current !== null) && (i < index)) { // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove current.previous.next = current.next; // special case: this is the last node so reset `this[tail]`. if (this[tail] === current) { this[tail] = current.previous; } else { current.next.previous = current.previous; } // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); } }

When index is 0, meaning the first node is being removed, this[head] is set to this[head].next, the same as with a singly linked list. The difference comes after that point when you need to update other pointers. If there was only one node in the list, then you need to set this[tail] to null to effectively remove that one node; if there was more than one node, you need to set this[head].previous to null. Remember that the new head was previously the second node in the list and so its previous link was pointing to the node that was just removed.

After the loop, you need to ensure that both the next pointer of the node before the removed node and the previous pointer of the node after the removed node. Of course, if the node to remove is the last node then you need to update the this[tail] pointer.

Creating a reverse iterator

You can make a doubly linked list iterable in JavaScript using the same values() and Symbol.iterator methods from the singly linked list. In a doubly linked list, however, you have the opportunity to create a reverse iterator that produces the data starting from the tail and working its way towards the head. Here is what a reverse() generator method looks like:

class DoublyLinkedList { // other methods hidden for clarity *reverse(){ // start by looking at the tail let current = this[tail]; // follow the previous links to the head while (current !== null) { yield current.data; current = current.previous; } } }

The reverse() generator method follows the same algorithm as the values() generator method in the singly linked list with the exception that current starts equal to this[tail] and the current.previous is followed until the there are no more nodes. Creating a reverse iterator is helpful for discovering bugs in the implementation as well as avoiding rearranging nodes just to access the data in a different order.

Other methods

Most other methods that don’t involve addition or removal of nodes follow the same algorithms as those in a singly linked list.

Using the class

Once complete, you can use the linked list implementation like this:

const list = new DoublyLinkedList(); list.add("red"); list.add("orange"); list.add("yellow"); // get the second item in the list console.log(list.get(1)); // "orange" // print out all items in reverse for (const color of list.reverse()) { console.log(color); } // remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the list console.log(list.get(1)); // "yellow" // convert to an array const array1 = [...list.values()]; const array2 = [...list]; const array3 = [...list.reverse()];

The full source code is available on GitHub at my Computer Science in JavaScript project.

Conclusion

Doubly linked lists are similar to singly linked lists in that each node has a next pointer to the next node in the list. Each node also has a previous pointer to the previous node in the list, allowing you to move both backwards and forwards in the list easily. Doubly linked lists typically track both the first and last node in the list, and that makes adding a node into the list a O(1) operation instead of O(n) in a singly linked list.

However, the complexity of other doubly linked list operations is the same as with a singly linked list because you always end up traversing most of the list. As such, doubly linked lists don’t offer any real advantage over the built-in JavaScript Array class for storing a collection of unrelated data (though related data, such as sibling DOM nodes in the browser) might be useful to represent in some kind of linked list.

Categories: Tech-n-law-ogy

Why I've stopped exporting defaults from my JavaScript modules

Mon, 01/14/2019 - 19:00

Last week, I tweeted something that got quite a few surprising responses:

In 2019, one of the things I’m going to do is stop exporting things as default from my CommonJS/ES6 modules.

Importing a default export has grown to feel like a guessing game where I have a 50/50 chance of being wrong each time. Is it a class? Is it a function?

— Nicholas C. Zakas (@slicknet) January 12, 2019

I tweeted this after realizing that a lot of problems I had with JavaScript modules could be traced back to fights with default exports. It didn’t matter if I was using JavaScript modules (or ECMAScript modules, as many prefer to call them) or CommonJS, I was still stumbling over importing from modules with default exports. I got a variety of responses to the tweet, many of which questioned how I could come to this decision. This post is my attempt to clarify my thinking.

A few clarifications

As is the case with all tweets, my tweet was meant as a snapshot into an opinion I had rather than a normative reference for my entire opinion. To clarify a few points people seem confused by on Twitter:

  • The use case of knowing whether an export is a function or a class was an example of the type of problems I’ve encountered. It is not the only problem I’ve found named exports solve for me.
  • The problems I’ve encountered don’t just happen with files in my own projects, they also happen with importing library and utility modules that I don’t own. That means naming conventions for filenames don’t solve all of the problems.
  • I’m not saying that everyone should abandon default exports. I’m saying that in modules I’m writing, I will choose not to use default exports. You may feel differently, and that’s fine.

Hopefully those clarifications setup enough context to avoid confusion throughout the rest of this post.

Default exports: A primer

To the best of my knowledge, default exports from modules were first popularized in CommonJS, where a module can export a default value like this:

class LinkedList {} module.exports = LinkedList;

This code exports the LinkedList class but does not specify the name to be used by consumers of the module. Assuming the filename is linked-list.js, you can import that default in another CommonJS module like this:

const LinkedList = require("./linked-list");

The require() function is returning a value that I just happened to name LinkedList to match what is in linked-list.js, but I also could have chosen to name it foo or Mountain or any random identifier.

The popularity of default module exports in CommonJS meant that JavaScript modules were designed to support this pattern:

ES6 favors the single/default export style, and gives the sweetest syntax to importing the default.

— David Herman June 19, 2014

So in JavaScript modules, you can export a default like this:

export default class LinkedList {}

And then you can import like this:

import LinkedList from "./linked-list.js";

Once again, LinkedList is this context is an arbitrary (if not well-reasoned) choice and could just as well be Dog or symphony.

The alternative: named exports

Both CommonJS and JavaScript modules support named exports in addition to default exports. Named exports allow for the name of a function, class, or variable to be transferred into the consuming file.

In CommonJS, you create a named export by attaching a name to the exports object, such as:

exports.LinkedList = class LinkedList {};

You can then import in another file like this:

const LinkedList = require("./linked-list").LinkedList;

Once again, the name I’ve used with const can be anything I want, but I’ve chosen to match it to the exported name LinkedList.

In JavaScript modules, a named export looks like this:

export class LinkedList {}

And you can import like this:

import { LinkedList } from "./linked-list.js";

In this code, LinkedList cannot be a randomly assigned identifier and must match an named export called LinkedList. That’s the only significant difference from CommonJS for the goals of this post.

So the capabilities of both module types support both default and named exports.

Personal preferences

Before going further, it’s helpful for you to know some of my own personal preferences when it comes to writing code. These are general principles I apply to all code that I write, regardless of the programming language I use:

  1. Explicit over implicit. I don’t like having code with secrets. What something does, what something should be called, etc., should always be made explicit whenever possible.
  2. Names should be consistent throughout all files. If something is an Apple in one file, I shouldn’t call it Orange in another file. An Apple should always be an Apple.
  3. Throw errors early and often. If it’s possible for something to be missing then it’s best to check as early as possible and, in the best case, throw an error that alerts me to the problem. I don’t want to wait until the code has finished executing to discover that it didn’t work correctly and then hunt for the problem.
  4. Fewer decisions mean faster development. A lot of the preferences I have are for eliminating decisions during coding. Every decision you make slows you down, which is why things like coding conventions lead to faster development. I want to decide things up front and then just go.
  5. Side trips slow down development. Whenever you have to stop and look something up in the middle of coding, I call that a side trip. Side trips are sometimes necessary but there are a lot of unnecessary side trips that can slow things down. I try to write code that eliminates the need for side trips.
  6. Cognitive overhead slows down development. Put simply: the more detail you need to remember to be productive when writing code, the slower your development will be.

The focus on speed of development is a practical one for me. As I’ve struggled with my health for years, the amount of energy I’ve had to code continued to decrease. Anything I could do to reduce the amount of time spent coding while still accomplishing my task was key.

The problems I’ve run into

With all of this in mind, here are the top problems I’ve run into using default exports and why I believe that named exports are a better choice in most situations.

What is that thing?

As I mentioned in my original tweet, I find it difficult to figure out what I’m importing when a module only has a default import. If you’re using a module or file you’re unfamiliar with, it can be difficult to figure out what is returned, for example:

const list = require("./list");

In this context, what would you expect list to be? It’s unlikely to be a primitive value, but it could logically be a function, class, or other type of object. How will I know for sure? I need a side trip. In this case, a side trip might be any of:

  • If I own list.js, then I may open the file and look for the export.
  • If I don’t own list.js, then I may open up some documentation.

In either case, this now becomes an extra bit of information you need in your brain to avoid a second side trip penalty when you need to import from list.js again. If you are importing a lot of defaults from modules then either your cognitive overhead is increasing or the number of side trips is increasing. Both are suboptimal and can be frustrating.

Some will say that IDEs are the answer to this problem, that the IDEs should be smart enough to figure out what is being imported and tell you. While I’m all for smarter IDEs to help developers, I believe requiring IDEs to effectively use a language feature is problematic.

Name matching problems

Named exports require consuming modules to at least specify the name of the thing they are importing from a module. The benefit is that I can easily search for everywhere that LinkedList is used in a code base and know that it all refers to the same LinkedList. As default exports are not prescriptive of the names used to import them, that means naming imports becomes more cognitive overhead for each developer. You need to determine the correct naming convention, and as extra overhead, you need to make sure every developer working in the application will use the same name for the same thing. (You can, of course, allow each developer to use different names for the same thing, but that introduces more cognitive overhead for the team.)

Importing a named export means at least referencing the canonical name of a thing everywhere that it’s used. Even if you choose to rename an import, the decision is made explicit, and cannot be done without first referencing the canonical name in some way. In CommonJS:

const MyList = require("./list").LinkedList;

In JavaScript modules:

import { LinkedList as MyList } from "./list.js";

In both module formats, you’ve made an explicit statement that LinkedList is now going to be referred to as MyList.

When naming is consistent across a codebase, you’re able to easily do things like:

  1. Search the codebase to find usage information.
  2. Refactor the name of something across the entire codebase.

Is it possible to do this when using default exports and ad-hoc naming of things? My guess is yes, but I’d also guess that it would be a lot more complicated and error-prone.

Importing the wrong thing

Named exports in JavaScript modules have a particular advantage over default exports in that an error is thrown when attempting to import something that doesn’t exist in the module. Consider this code:

import { LinkedList } from "./list.js";

If LinkedList doesn’t exist in list.js, then an error is thrown. Further, tools such as IDEs and ESLint1 are easily able to detect a missing reference before the code is executed.

Worse tooling support

Speaking of IDEs, WebStorm is able to help write import statements for you.2 When you have finished typing an identifier that isn’t defined in the file, WebStorm will search the modules in your project to determine if the identifier is a named export in another file. At that point, it can do any of the following:

  1. Underline the identifier that is missing its definition and show you the import statement that would fix it.
  2. Automatically add the correct import statement (if you have enable auto import) can now automatically add an import statement based on an identifier that you type. In fact, WebStorm is able to help you a great deal when using named imports:

There is a plugin for Visual Studio Code3 that provides similar functionality. This type of functionality isn’t possible when using default exports because there is no canonical name for things you want to import.

Conclusion

I’ve had several productivity problems importing default exports in my projects. While none of the problems are necessarily impossible to overcome, using named imports and exports seems to better fit my preferences when coding. Making things explicit and leaning heavily on tooling makes me a productive coder, and insofar as named exports help me do that, I will likely favor them for the foreseeable future. Of course, I have no control over how third-party modules I use export their functionality, but I definitely have a choice over how my own modules export things and will choose named exports.

As earlier, I remind you that this is my opinion and you may not find my reasoning to be persuasive. This post was not meant to persuade anyone to stop using default exports, but rather, to better explain to those that inquired why I, personally, will stop exporting defaults from the modules I write.

References
  1. esling-plugin-import import/named rule 

  2. WebStorm: Auto Import in JavaScript 

  3. Visual Studio Extension: Auto Import 

Categories: Tech-n-law-ogy

Computer science in JavaScript 2019: Linked list

Mon, 01/07/2019 - 19:00

Back in 2009, I challenged myself to write one blog post per week for the entire year. I had read that the best way to gain more traffic to a blog was to post consistently. One post per week seemed like a realistic goal due to all the article ideas I had but it turned out I was well short of 52 ideas. I dug through some half-written chapters what would eventually become Professional JavaScript and found a lot of material on classic computer science topics, including data structures and algorithms. I took that material and turned it into several posts in 2009 and (and a few in 2012), and got a lot of positive feedback on them.

Now, at the ten year anniversary of those posts, I’ve decided to update, republish, and expand on them using JavaScript in 2019. It’s been interesting to see what has changed and what hasn’t, and I hope you enjoy them.

What is a linked list?

A linked list is a data structure that stores multiple values in a linear fashion. Each value in a linked list is contained in its own node, an object that contains the data along with a link to the next node in the list. The link is a pointer to another node object or null if there is no next node. If each node has just one pointer to another node (most frequently called next) then the list is considered a singly linked list (or just linked list) whereas if each node has two links (usually previous and next) then it is considered a doubly linked list. In this post, I am focusing on singly linked lists.

Why use a linked list?

The primary benefit of linked lists is that they can contain an arbitrary number of values while using only the amount of memory necessary for those values. Preserving memory was very important on older computers where memory was scarce. At that time, a built-in array in C required you to specify how many items the array could contain and the program would reserve that amount of memory. Reserving that memory meant it could not be used for the rest of the program or any other programs running at the same time, even if the memory was never filled. One memory-scarce machines, you could easily run out of available memory using arrays. Linked lists were created to work around this problem.

Though originally intended for better memory management, linked lists also became popular when developers didn’t know how many items an array would ultimately contain. It was much easier to use a linked list and add values as necessary than it was to accurately guess the maximum number of values an array might contain. As such, linked lists are often used as the foundation for built-in data structures in various programming languages.

The built-in JavaScript Array type is not implemented as a linked list, though its size is dynamic and is always the best option to start with. You might go your entire career without needing to use a linked list in JavaScript but linked lists are still a good way to learn about creating your own data structures.

The design of a linked list

The most important part of a linked list is its node structure. Each node must contain some data and a pointer to the next node in the list. Here is a simple representation in JavaScript:

class LinkedListNode { constructor(data) { this.data = data; this.next = null; } }

In the LinkedListNode class, the data property contains the value the linked list item should store and the next property is a pointer to the next item in the list. The next property starts out as null because you don’t yet know the next node. You can then create a linked list using the LinkedListNode class like this:

// create the first node const head = new LinkedListNode(12); // add a second node head.next = new LinkedListNode(99); // add a third node head.next.next = new LinkedListNode(37);

The first node in a linked list is typically called the head, so the head identifier in this example represents the first node. The second node is created an assigned to head.next to create a list with two items. A third node is added by assigning it to head.next.next, which is the next pointer of the second node in the list. The next pointer of the third node in the list remains null. The following image shows the resulting data structure.

The structure of a linked list allows you to traverse all of the data by following the next pointer on each node. Here is a simple example of how to traverse a linked list and print each value out to the console:

let current = head; while (current !== null) { console.log(current.data); current = current.next; }

This code uses the variable current as the pointer that moves through the linked list. The current variable is initialized to the head of the list and the while loop continues until current is null. Inside of the loop, the value stored on the current node is printed and then the next pointer is followed to the next node.

Most linked list operations use this traversal algorithm or something similar, so understanding this algorithm is important to understanding linked lists in general.

The LinkedList class

If you were writing a linked list in C, you might stop at this point and consider your task complete (although you would use a struct instead of a class to represent each node). However, in object-oriented languages like JavaScript, it’s more customary to create a class to encapsulate this functionality. Here is a simple example:

const head = Symbol("head"); class LinkedList { constructor() { this[head] = null; } }

The LinkedList class represents a linked list and will contain methods for interacting with the data it contains. The only property is a symbol property called head that will contain a pointer to the first node in the list. A symbol property is used instead of a string property to make it clear that this property is not intended to be modified outside of the class.

Adding new data to the list

Adding an item into a linked list requires walking the structure to find the correct location, creating a new node, and inserting it in place. The one special case is when the list is empty, in which case you simply create a new node and assign it to head:

const head = Symbol("head"); class LinkedList { constructor() { this[head] = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this[head] === null) { // just set the head to the new node this[head] = newNode; } else { // start out by looking at the first node let current = this[head]; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } } }

The add() method accepts a single argument, any piece of data, and adds it to the end of the list. If the list is empty (this[head] is null) then you assign this[head] equal to the new node. If the list is not empty, then you need to traverse the already-existing list to find the last node. The traversal happens in a while loop that start at this[head] and follows the next links of each node until the last node is found. The last node has a next property equal to null, so it’s important to stop traversal at that point rather than when current is null (as in the previous section). You can then assign the new node to that next property to add the data into the list.

Traditional algorithms use two pointers, a current that points to the item being inspected and a previous that points to the node before current. When current is null, that means previous is pointing to the last item in the list. I don’t find that approach very logical when you can just check the value of current.next and exit the loop at that point.

The complexity of the add() method is O(n) because you must traverse the entire list to find the location to insert a new node. You can reduce this complexity to O(1) by tracking the end of the list (usually called the tail) in addition to the head, allowing you to immediately insert a new node in the correct position.

Retrieving data from the list

Linked lists don’t allow random access to its contents, but you can still retrieve data in any given position by traversing the list and returning the data. To do so, you’ll add a get() method that accepts a zero-based index of the data to retrieve, like this:

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this[head]; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } } }

The get() method first checks to make sure that index is a positive value, otherwise it returns undefined. The i variable is used to keep track of how deep the traversal has gone into the list. The loop itself is the same basic traversal you saw earlier with the added condition that the loop should exit when i is equal to index. That means there are two conditions under which the loop can exit:

  1. current is null, which means the list is shorter than index.
  2. i is equal to index, which means current is the node in the index position.

If current is null then undefined is returned and otherwise current.data is returned. This check ensures that get() will never throw an error for an index that isn’t found in the list (although you could decide to throw an error instead of returning undefined).

The complexity of the get() method ranges from O(1) when removing the first node (no traversal is needed) to O(n) when removing the last node (traversing the entire list is required). It’s difficult to reduce complexity because a search is always required to identify the correct value to return.

Removing data from a linked list

Removing data from a linked list is a little bit tricky because you need to ensure that all next pointers remain valid after a node is removed. For instance, if you want to remove the second node in a three-node list, you’ll need to ensure that the first node’s next property now points to the third node instead of the second. Skipping over the second node in this way effectively removes it from the list.

The remove operation is actually two operations:

  1. Find the specified index (the same algorithm as in get())
  2. Remove the node at that index

Finding the specified index is the same as in the get() method, but in this loop you also need to track the node that comes before current because you’ll need to modify the next pointer of the previous node.

There are also four special cases to consider:

  1. The list is empty (no traversal is possible)
  2. The index is less than zero
  3. The index is greater than the number of items in the list
  4. The index is zero (removing the head)

In the first three cases, the removal operation cannot be completed, and so it makes sense to throw an error; the fourth special case requires rewriting the this[head] property. Here is what the implementation of a remove() method looks like:

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this[head] === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this[head].data; // just replace the head with the next node in the list this[head] = this[head].next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this[head]; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); } }

The remove() method first checks for two special cases, an empty list (this[head] is null) and an index that is less than zero. An error is thrown in both cases.

The next special case is when index is 0, meaning that you are removing the list head. The new list head should be the second node in the list, so you can set this[head] equal to this[head].next. It doesn’t matter if there’s only one node in the list because this[head] would end up equal to null, which means the list is empty after the removal. The only catch is to store the data from the original head in a local variable, data, so that it can be returned.

With three of the four special cases taken care of, you can now proceed with a traversal similar to that found in the get() method. As mentioned earlier, this loop is slightly different in that the previous variable is used to keep track of the node that appears just before current, as that information is necessary to propely remove a node. Similar to get(), when the loop exits current may be null, indicating that the index wasn’t found. If that happens then an error is thrown, otherwise, previous.next is set to current.next, effectively removing current from the list. The data stored on current is returned as the last step.

The complexity of the remove() method is the same as get() and ranges from O(1) when removing the first node to O(n) when removing the last node.

Making the list iterable

In order to be used with the JavaScript for-of loop and array destructuring, collections of data must be iterables. The built-in JavaScript collections such as Array and Set are iterable by default, and you can make your own classes iterable by specifying a Symbol.iterator generator method on the class. I prefer to first implement a values() generator method (to match the method found on built-in collection classes) and then have Symbol.iterator call values() directly.

The values() method need only do a basic traversal of the list and yield the data that each node contains:

class LinkedList { // other methods hidden for clarity *values(){ let current = this[head]; while (current !== null) { yield current.data; current = current.next; } } [Symbol.iterator]() { return this.values(); } }

The values() method is marked with an asterisk (*) to indicate that it’s a generator method. The method traverses the list, using yield to return each piece of data it encounters. (Note that the Symbol.iterator method isn’t marked as a generator because it is returning an iterator from the values() generator method.)

Using the class

Once complete, you can use the linked list implementation like this:

const list = new LinkedList(); list.add("red"); list.add("orange"); list.add("yellow"); // get the second item in the list console.log(list.get(1)); // "orange" // print out all items for (const color of list) { console.log(color); } // remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the list console.log(list.get(1)); // "yellow" // convert to an array const array1 = [...list.values()]; const array2 = [...list];

This basic implementation of a linked list can be rounded out with a size property to count the number of nodes in the list, and other familiar methods such as indexOf(). The full source code is available on GitHub at my Computer Science in JavaScript project.

Conclusion

Linked lists aren’t something you’re likely to use every day, but they are a foundational data structure in computer science. The concept of using nodes that point to one another is used in many other data structures are built into many higher-level programming languages. A good understanding of how linked lists work is important for a good overall understanding of how to create and use other data structures.

For JavaScript programming, you are almost always better off using the built-in collection classes such as Array rather than creating your own. The built-in collection classes have already been optimized for production use and are well-supported across execution environments.

Categories: Tech-n-law-ogy

My (somewhat) complete salary history as a software engineer

Mon, 10/29/2018 - 20:00

It’s 2018 and somehow women are still getting paid less than men, even in supposedly progressive industries like software.[1] Whether that be from companies offering women less than men for the same position, women being less likely to negotiate or less successful in negotiations, or any of the other myriad reasons, the results are still the same: women make less than men for the same job. That’s something that shouldn’t be happening in today’s world and it’s up to us (read: men) to step up and make things right. This is my attempt to do just that.

Why am I doing this?

Longtime followers know that I’ve been dealing with serious health issues for several years. Two and a half years ago I had to stop working to focus on my health and it will likely be a couple more years before I’m able to even consider working a full-time job again. The people responsible for my last compensation package have long since left that company. That puts me in a unique position where I am not beholden to any past employers, and any future employers are far enough into the future that the information I’m sharing here will be mostly useless by then. Plus, as a white man, I know I’m going to be able to negotiate for my salary without backlash[2] when I do start working again. As such, the information in this post is more valuable to others than it is to me.

As an aside, I’ve been annoyed that throughout my career I’ve been lectured many times to avoid discussing my compensation with colleagues. Usually it’s with the warning that, “not everyone is getting what you’re getting, and we don’t want to hurt feelings.” It took me a long time to realize that the “hurt feelings” they’re talking about come from an overall lack of transparency into the compensation process, and that simply explaining why people are compensated in certain ways would be a better solution than to hide all of the information from everyone. Yes, there will always be people who think they deserve to be making more but who don’t actually deserve it. That seems like a great way to communicate that they aren’t doing a good enough job and figure out ways to improve.

The bottom line is that nothing gets better unless people are willing to share information. And while I could just share my last salary, I don’t think that’s very useful, especially when compared with the variety of already-available sources of information online. No, to be useful, I felt like I would need to reveal my entire salary history so people can determine for themselves if they’re seeing enough improvement in their salaries over time.

Where did this data come from?

The data in this post comes from the following sources:

  1. My memory. Yes, memory is fallible, but there are some data points that are so important on an emotional level that they tend to stick in my brain. I’ll point those out.
  2. Offer letters. As my offer letters post-2006 were always emailed to me, I’ve been able to be 100% sure of those details. Prior to 2006, my offer letters were always mailed to me, and I have no record of those.

Where my memory fails me and I don’t have an offer letter, I’ve made an attempt to guess the salary range I had at the time.

The data

The table below contains all of my salary (and some other compensation history). I’m including what I believe to be data relevant to evaluating the compensation include the year I received the salary, the years of experience I had at the time (YOE), the starting and ending salary to take into account raises, and any signing bonus (Signing $) and stock options (Options) I might have received. Any amount with a question mark indicates that I’m guessing. I did not include any restricted stock units I might have received because I only ever received them at Yahoo as part of my initial offer.

Year YOE Company State Title Starting $ Ending $ Signing $ Options 2000 0 Radnet, Inc. MA Webmaster $48,000 $55,000 - ? 2001 0 Radnet, Inc. MA UI Developer $62,500 $62,500 - - 2001 0 MatrixOne, Inc. MA UI Designer/Developer $68,000? ? $2,000 ? 2003 3 MatrixOne, Inc. MA Senior Software Engineer ? $75,000? - - 2005 5 Vistaprint, Inc. MA Lead Software Engineer $82,000? $98,000 - 3,000 2006 6 Yahoo, Inc. CA Senior Front-end Engineer $115,000 ? $10,000 3,500 2008 8 Yahoo, Inc. CA Principal Front-end Engineer ? ? - - 2011 11 Yahoo, Inc. CA Presentation Architect ? $165,000? - - 2013 13 Box, Inc. CA Staff Software Engineer $175,000 ? $25,000 50,000 2014 14 Box, Inc. CA Principal Architect $208,000 $220,000 - - Job Details

The data alone doesn’t really tell the full story, so here are the details around each position. I’ve also included how I came to work at each company, as I think it’s important to recognize blind resume submissions from having contacts as a company.

Radnet (2000-2001)

My first job out of college was at a small startup in Wakefield, MA called Radnet, Inc. I got this job because the woman who used to babysit me as a child was running human resources at the company. My official title was webmaster, and I thought I would be coming in to run the company website. As it turned out, between the time they offered me the job and my starting day, they had hired someone to oversee both UI development and the website. As it turned out, I would never manage the website and instead would spend time making JavaScript components for the company’s web application.

I know that my starting salary was $48,000 (about $70,284 in 2018 dollars) because I was very excited about it. After spending summers working jobs that ranged from $2/hour to $6/hour, this seemed like an incredible amount of money to me. A few months in, they gave me a raise to $55,000 because I was doing a good job. Towards the end of 2000, they believed the company would be bought and so they changed my title to UI Developer and upped my salary to $62,500 with the belief that an acquirer would immediately fire the “webmaster” and ensuring I’d benefit from the acquisition.

As it turned out, the company never got bought and so it shutdown in January 2001. I never really saw much of the $62,500, and eight months after I had started my first job, I was unemployed.

Note: I did receive stock options for this position, but I don’t remember what they were. I didn’t really understand what stock options were at the time so that information never stuck in my brain.

MatrixOne (2001-2005)

When Radnet closed down, my manager ended up at MatrixOne and asked if I would like to join him. I had enjoyed working with him at Radnet so I accepted. It’s important to understand that this was during the dot-com crash and there weren’t a lot of tech jobs to be had in Massachusetts at the time. I considered myself lucky to have formed a good relationship that allowed me to find a new job fairly quickly after Radnet shut down.

I don’t remember all of the details but I’m pretty sure my starting salary was close to $68,000 ($96,814 in 2018 dollars). I’m also reasonably certain that I got a small signing bonus, maybe around $2,000, that my manager negotiated for me. I also received some stock options, but once again, I didn’t really understand what they were and so didn’t even register them as part of my compensation. It didn’t matter, though, because the company stock was never again as high as the day I joined. I was never able to exercise options, even when I got some repriced options later in my career there because the stock only ever went down. (Eventually the company would be bought out by a competitor.)

My salary didn’t improve much there because the company was in perpetually poor financial health. There was a salary freeze in place almost the entire time I was there. I survived four rounds of layoffs. I was eventually “promoted” to the position of Senior Software Engineer, but it was a promotion in title only. There was no increase in salary (because of the salary freeze) and no change in my responsibilities (because the organization was weird). It was just a pat on the back to say, “good job, please don’t leave.” Spoiler alert: I left as soon as I could.

Right before I left, I did get a salary increase to around $75,000. It wasn’t enough to make me want to stay.

Vistaprint (2005-2006)

I often refer to my position at Vistaprint as my first real software engineering job. It was the first time I applied for a software engineering job without having a connection at the company; I just sent my resume in to their email address. I reported into the engineering organization (as opposed to the design organization in my prior jobs), and I got what I considered to be a good offer. The company was pre-IPO, and I was excited to get 3,000 stock options. (By this time, I actually understood what stock options were.)

I don’t recall the starting salary but I suspect it was around $82,000 ($105,867 in 2018 dollars). I definitely recall the ending salary as $98,000 for a few reasons. First, I was complaining a lot about the boring project they had assigned me to so I expected that would eliminate me from any serious raise considerations. I was shocked to get a raise and even more shocked at the amount. Second, I was bummed they didn’t give me the extra $2,000 to make an even $100,000. Last, I was secretly interviewing with both Google and Yahoo, and upping my salary meant that I could use that number when it came time to talk compensation with them.

I was only at Vistaprint for a little over a year before deciding to move to California to work for Yahoo. Vistaprint did go public while I was there, but since I left after a year, I didn’t see much from those stock options.

Yahoo (2006-2011)

Yahoo’s initial offer was the best I had received up to that point. In addition to a $115,000 base salary ($143,833 in 2018 dollars), it included $10,000 signing bonus, 3,500 stock options, 1,500 RSUs, and relocation expenses. This was the first time I tried to negotiate for a higher starting salary and was summarily rejected. At least I tried.

I ended up at Yahoo through a circuitous route. I had heard that Yahoo was using my first book, Professional JavaScript for Web Developers, to teach JavaScript at the company. As such, I had an open invitation to stop by the campus if I was ever in the area. I had traveled to Mountain View to interview Google (they had found me through my second book, Professional Ajax) and so reached out to the folks at Yahoo to meet up. I didn’t realize that conversation would turn into an invitation to apply to work at Yahoo as well.

I don’t remember a lot of my pay details after I joined. Being at Yahoo for almost five years, I got several raises and two promotions, so my pay did keep increasing. All of that information was sent to my Yahoo corporate email address, and as such, I no longer have any of the documentation. That was intermixed with periods of layoffs and salary freezes. My initial stock options ended up worthless because the company stock price never again reached the level it was at when the options were priced. I would later get repriced stock options and more RSUs, but I don’t have specifics on that.

By the time I left, I suspect I was making around $165,000 based on how I felt about the offer from Box.

It’s worth noting that I left Yahoo to try to start a company with some friends and so didn’t have a regular salary for about 18 months.

Box (2013-2016)

My offer from Box was also strong. The starting salary of $175,000 ($189,415 in 2018 dollars) was more than enough to make me happy at the time, and the offer included 50,000 stock options. Box was pre-IPO so that high stock option allocation (which I was told was higher than what they usually gave people at my level) was a big consideration for me. I negotiated for a $25,000 signing bonus, as well.

As part of my consulting business, I would regularly give talks at different companies. I agreed to give a talk for free at Box because a friend worked there and mentioned that they were having trouble managing their growing JavaScript code base. I spoke with a few people after the talk, including the VP of engineering, and we decided to explore if working at Box was a good fit for the company and me. Through several more discussions, it seemed like a good opportunity to get back into the stability of a regular salary with some interesting problems to tackle.

My memory is a bit hazy around what happened between joining and the end of my time at Box as this was the period when my health was on a steep decline. I think I got one raise as a Staff Software Engineer about three months after I joined, and was informed of being promoted to Principal Architect six months after I joined (although I wouldn’t get the pay increase for another six months). I’m reasonably certain the promotion pay increase bumped me to $208,000. I recall clearly that I got one last raise to push me to $220,000 during 2014 because I had started working from home full time due to my health and I thought it was very nice of them to give me a raise regardless.

I left Box when I was no longer physically able to work from home.

Conclusion

In my sixteen year career, I averaged a pay increase of $10,000 per year, even when taking into account several years of salary freezes at MatrixOne and Yahoo. As such, I suspect I’d be making around $250,000 if I was working full time today.

It’s also important to understand that I never asked for a raise and only negotiated other details occassionally (as mentioned in the post). I never really felt comfortable with negotiations prior to working for myself, and generally was happy with the offers I received.

With the exception of my one year at Vistaprint (during which I was a grouchy pain in the ass), I was consistently reviewed as a top former at my position. I wasn’t put on any sort of improvement plan and most of my feedback had to do with improving interactions and communication with colleagues. And again, with the exception of Vistaprint (because…pain in the ass), I took the feedback to heart and worked to improve in those areas.

Being single and not having a family to support throughout my entire career meant that I had more options. I could afford to take salary that was lower than what I wanted or could get elsewhere, and I could also afford to walk away from valuable stock options (such as with Vistaprint) to find a job that was more fulfilling. I recognize that not everyone has that option, so I think it’s important to make my situation clear here.

I have two hopes from sharing this information. First, I hope that having this information will make it easier for women to understand how much they should be paid for similar work and just how their pay should be increasing throughout their career. Second, I hope that other men who are in a similarly independent position will also share their compensation history to benefit others.

We can all be better if we’re willing to share.

References
  1. By the Numbers: What pay inequality looks like for women in tech (forbes.com)
  2. Women Know When Negotiating Isn’t Worth It (theatlantic.com)
Categories: Tech-n-law-ogy