12 min readMay 28, 2018

Map-List: JavaScript Data Structure That Models Applications

Front-end developers create data-driven web sites. Whether we render forms or data visualizations, we are trying to communicate and maintain the state of our data using visuals. It makes sense to develop an underlying structure that parallels the rendering and interaction with that data. Map-List is a structure that does that. While it’s common to develop such structures in a language like Java, JavaScript applications tend to use the array functions. A look at performance will show that it could be worthwhile to have such an underlying structure, in addition to providing a model for the application data.

Information is provided in how to use a JavaScript module packaged for npmjs in a browser application.

A JavaScript Data Structure For Indexed and Direct Access

Recognizing patterns in software development can lead to algorithms and data structures that produce more efficient and more maintainable code. This discussion introduces a data structure called Map-List that supports a common front-end pattern. The pattern could help with code organization and maintenance. There is also some code that measure performance to support the fact that it can help with performance. The Map-List data structure can be used in both the back end (node) and the front end (browser), so instructions are provided to see how that can be done.

A Front End Pattern

In the course of writing web applications, a familiar pattern emerges:

a chunk of data is returned from a service call
a list that allows the user to view a summary of the data is rendered
the user selects an item from the list
the user can then view more data about the item and take action on it

CRUD: Create Read Update Delete

Images from a front-end application example for managing a list of hikes are shown below. The application consists of a list of hikes with an “Add hike” button to create a new hike. The name of the hike is a link that takes the user to a page with information about the hike and a map that enable the user to see its location. Each row contains two buttons labeled “Edit” and “Delete”. When you click on the “Add Hike” button the user gets an empty form. When the user clicks the “Edit” the form is shown populated so that it can be updated. When the user clicks on “Delete” they are given a form with a button to delete the hike. The pattern implementing List, Display, Add, Edit, Delete uses a pattern familiar to database programmers: CRUD which is an acronym for Create Read Update Delete. The images below show the mapping of front end forms and interactivity to the CRUD pattern.

For a front-end developer, the JavaScript required to support this pattern involves iterating over a list to render it and then retrieving a user-selected value to lookup an item in the list. The JavaScript Array is a suitable data structure for iteration, and with the functions provided by the Array class such as filter, it’s possible to find any element within it. Frameworks that provide data binding to the DOM make this an even smoother process.

Apps With Local Data

There are some front-end apps in which the user may execute the display list/display single item pattern many times. For these apps, it’s useful to maintain a structure for iteration and a structure for direct lookup.

In a single-page app, where the developer is allowing multiple actions to take place in the midst of multiple routes, the need to iterate over and do a lookup on, the same dataset increases.

Data visualization apps supply arrays of data to bind to the chart generating code. For example in the D3 app below, an array loads the network visualization. The user is also encouraged to interact with the chart to get more information about a specific node. If there is a lot of data associated with each node, the developer can use a minimal subset of the data to create the node, but then rely on a fast lookup to get the full data set if the user indicates through click or hover that more information is needed.

Map-List: A JavaScript Data Structure

map-list is a node module and can be installed from npmjs.org and the code is available on GitHub.

Map-List is implemented as a class that encapsulates both an ordered object (JavaScript Array) and a keyed object (JavaScript Object). The methods (functions) in this class provide an interface to add to, and access from the encapsulated data. Vanilla JavaScript doesn’t provide a way to make functions private, but I have prefixed the array and object collection names with an underscore to indicate the intention is that they are treated as private. There are also two helper functions whose names are prefixed with an underscore and again the intention is that they are treated as private. All interaction with the class should take place via functions whose names do not begin with an underscore.

The Map-List interface is highly influenced by the Java Collection interface which Java full-stack developers will be familiar with.

The constructor accepts two parameters: 1) the key parameter is a string that indicates which property of the item added to the Map-List will serve as a key, and 2) the errOnDuplicates parameter is a Boolean value and, if set to true, causes an exception to be thrown if the user attempts to enter a duplicate key. If the errOnDuplicates parameter is set to false (implemented as the default), the first item is stored and subsequent items with the same key value are ignored. The Map-List is therefore a Set and guarantees unique keys with a single item per key.

The add function accepts an item and looks for the property value that corresponds to the key designated in the construct call to serve as the key for the mapCollection. The remove function accepts an item’s key and removes the item from the underlying array and object collections. The update function accepts an item and updates the existing item base on the key-value provided in the constructor.

Items may be retrieved by a key value using getItemByKey or using a numeric index value using getItemByIndex. The items in the _listCollection and the _mapCollection reference the same object, so there is no duplication of data. The whole dataset may also be retrieved as an Array or an Object by using the asList and asMap methods respectively. A getter method keys return an array of keys that are used to identify the items in the collection.

Details of Maintaining Two Structures

The Map-List code is focused on maintaining a collection of objects that are accessible via an array index or an object key.

The possibility of two items having duplicate keys add some complexity to the add method. A decision has to be made as to whether to throw out a duplicate key, override an existing key with a new value, or let the user know via an exception. The case in which the duplicate indicated an error led to the creation of an option errOnDuplicates. This leaves it up to the user as to whether or not to throw an exception. The default is for errOnDuplicates to be false which results in a duplicate being ignored. Ignoring the duplicate was a design decision. If errOnDuplicates is set to true, an exception will be thrown if there are duplicate keys.

if (this.errOnDuplicates === true) {
  if (this._mapCollection[item[this.key]] !== undefined) {
    this._clearCollections();
    throw new Error(`Item with ${this.key} = ${item[this.key]} already exists`);
  } else {
    this._addToCollections(item);
  }
} else {
  this._addToCollections(item);
}

The update method tests whether the item exists before proceeding with the update. For both update and delete, there must be an iteration to locate the position of the item in the array. Once this is located the appropriate action can be taken for both the array (_listCollection) and the object (_mapCollection). For the delete method, it is necessary to remove the item from both the array and the object. It is also a good idea to set the item to null as it should not be referenced or reference anything once removed to support garbage collection. The code to remove the object is shown below.

this._listCollection.some((item, index)=>{
  if (item[this.key] === keyToRemove){
    this._listCollection.splice(index,1);
    delete this._mapCollection[keyToRemove];
    itemToRemove = null;
    return true;
  }
}, this);

Because Map-List is managing two different structures there might be questions about whether the changes are atomic. In a language like Java or C, a lock might be needed around the two instructions which update each of the two structure. However, in JavaScript, the Event Loop promises to complete the function before allowing another instruction to take place. This is described in Mozilla Developer Network Documents: “ This offers some nice properties when reasoning about your program, including the fact that whenever a function runs, it cannot be pre-empted and will run entirely before any other code runs (and can modify data the function manipulates). This differs from C, for instance, where if a function runs in a thread, it can be stopped at any point to run some other code in another thread.”

Unit Testing

A set of unit tests can help to clarify how to use the functions. The unit tests are run by travis ci when changes are checked into GitHub. A badge at the bottom of the Readme.md indicates the status of the tests. Tests are run using mocha and chai.

Performance

JavaScript is a functional language. The Array functions such as filter, map, and foreach are optimized for speed and can provide the functionality that direct access via a keyed lookup provides. There are benefits to using functions to represent data over encapsulating data in objects, namely eliminating side effects. While the Map-List was created to help with code organization and the codifying of a pattern, it is important to consider the effects on performance. Unit tests can be constructed to help eliminate unwanted side effects, but if performance is noticeably degraded, it would not be worth using the data structure.

There are a couple of tests aimed at determining the effect on memory space. There is also a test for a time that compares the use of the filter function with direct access via key. The methods and results are summarized below.

The net effect for space is that there is more space used when you construct a Map-List over constructing just an Array or an Object, but if you are looking for the benefits of both an Array and an Object, the Map-List does not double the memory. This is because the Map-List is referencing a single item with two structures. The net effect for time is that the Map-List’s direct access via key is faster than the filter function.

Space Measures

To test space requirements, three tests were conducted: array_only, object_only, and maplist_memory. Each of the tests loads 1,000,000 unique items into a data structure and then tests the number of MegaBytes used by the process.

const used = process.memoryUsage().heapUsed / 1024 / 1024;

The results of these tests of the amount of memory used by each data structure are:

Array Only: 202.3 MB

Object Only: 346.2MB

MapList: 374.6 MB

MapList uses 8% more space than an Object structure and 85% more space than an array. However, an Object uses 71% more space than an array as well, indicating that Objects are more costly in terms of space than arrays. Direct access requires adding redundant data (the key) to memory and there is a cost for that.

Time Measures

To test whether the Map-List improves the speed at which data access, one test was conducted: direct-vs-filter.js.

console.time("direct access");
console.log("direct",mapList.getItemByKey("test999").value);
console.timeEnd("direct access");console.time("filter");
let filterArr = arrData.filter(item=>item.name === "test999");
console.log(filterArr[0].value);console.log("direct",mapList.getItemByKey("test999").value);
console.timeEnd("filter");

There are two timers: “direct access” measures the time to retrieve an item from an Object using direct keyed access, and “filter” measures the time to retrieve an item using the Array filter function. The results are shown below are averages calculated after running the code 10 times as times vary. The average increase in speed using the Map-List direct keyed access is 146% over using the Array filter function.

Direct Access: 1.3 ms

Filter: 191.4 ms

Using Map-List in the Browser

The Map-List described here is available on npm.js is and ready for use in a Node application. It can also be used in a browser application, where the trade-off between speed and the amount of memory required may not be as important because a front-end developer might be looking for ways to minimize the amount of data downloaded for the page.

There is a sample index.html that uses Map-List constructed in main.js and then browserified into bundle.js, which is used for demonstration in index.html. Map-List is imported using the ES6 Import instruction and because the code is local, a relative path to the code.

import { MapList } from './index.js';

In package.json, there is a script build-example that can be run from the command line with npm run build-example.Map-List can be used in backend or front end code.

Using Map-List with a Framework: Vue.js

hikes is a Vue.js application that can be downloaded from GitHub.

The hikes application, from which the CRUD images above were created, is a Vue.js application that maintains a list of information about hikes. The data is not persisted and any changes are lost on a page refresh. This app demonstrates how to incorporate a Map-List structure into a front-end framework app.

The Map-List module is installed from npm and then the ES6 import instruction is used with the name specified in the Map-List package.json. The Vue.js CLI provides the webpack config to transpile all the ES6 for the browser.

import MapList from 'map-list'

Code from the Crud: Read component, Hike.vue, shows the data that is supplied for binding: a single hike is retrieved by a single function call where this would have required an iteration (using the filter function) without Map-List.

data() {    
    return {      
       hike: mapList.getItemByKey(this.$route.params.hike_id),
       hikes: mapList}

The component that supplies the list of hikes, List, supplies just mapList renamed as “hikes’.

data() { return { 
    hikes: mapList, 
    searchKey: "" }

The application provides filtering for the name of the hike in the list and therefore the template provides a call to a computed filter function.

<tr v-for="(hike,index) in filteredHikes" v-bind:key="index">

The filteredHikes function makes use of the Map-List asList function to get an array representation of the data so that it can apply the JavaScript filter to the data. The filteredHikes function provides an array to the Vue.js v-for directive.

computed: {
  filteredHikes: function() {
    let search = this.searchKey.toLowerCase();
      return this.hikes.asList().filter((hike)=> {
        return (
          search.length === 0 || 
          hike.name.toLowerCase().indexOf(search) !== -1);
      }, this);
    }
}

When updating a hike in HikeEdit.vue, data is provided for just the hike and the hikes Map-List

data() {return { hike: mapList.getItemByKey(this.$route.params.hike_id), hikes: mapList };},

and then the hikes Map-List calls the update method with the hike object.

this.hikes.update(this.hike);

When deleting a hike in HikeDelete.vue, data is provided for both the hike and the hikes Map-List, so that a key for the hike can be passed to the Map-List remove method.

this.hikes.remove(this.hike.id)

Establishing Code Patterns with Data Structures

So, what’s the point of creating this data structure? Isn’t it just more code to maintain when you could easily get the same effects by just using Object and Array structures as needed? There are performance tradeoffs: more memory required but faster lookups. Why create a utility class that bundles the two structures?

The technical gain is due to the fact that a single object is referenced in the two ways that objects need to be referenced to satisfy access based on order and key.

The biggest gains are made when working on a team where much of the communication occurs through the code. Establishing a data structure that supports the common UI patterns of “show a list, select and item, show the item detail” communicates to the team how the data should be accessed and encourages the coders to use this data structure to support the pattern. Over the life of a product, this can make it easier to learn and maintain the code.