JavaScript data types and data structures

  • Revision slug: Web/JavaScript/Data_structures
  • Revision title: Javascript Data structures
  • Revision id: 416975
  • Created:
  • Creator: Sheppy
  • Is current revision? No
  • Comment Moved From JavaScript/Data_structures to Web/JavaScript/Data_structures

Revision Content

Programming languages all have built-in data structures, but these often differ from one language to another. This article attempts to list the built-in data structures available in JavaScript and what properties they have; these can be used to build other data structures. When possible, comparisons with other languages are drawn.

The ECMAScript standard defines six data types:

  • Number
  • String
  • Boolean
  • Null
  • Undefined
  • Object

In the following sections, we will see how these types can be used to represent data and be combined to implement more complex data structures.

Primitive values

All types except objects define immutable values. Specifically, strings are immutable (unlike in C for instance). We refer to values of these types as "primitive values." This is explained in more detail in the section on {{ anch("Strings") }} below.

Booleans, null, and undefined

Within these types, four constants can be found: true, false, null, and undefined. Since these are constants, they cannot represent rich data (or data structures).

Numbers

According to the ECMAScript standard, there is only one number type: the "double-precision 64-bit binary format IEEE 754 value". There is no specific type for integers. In addition to being able to represent floating-point numbers, it has some symbolic values: +Infinity, -Infinity, and NaN (not-a-number).

Although a number often represents only its value, JavaScript provides some binary operators. These can be used to represent several Boolean values within a single number using bit masking. This is usually considered a bad practice, however, since JavaScript offers other means to represent a set of Booleans (like an array of Booleans or an object with Boolean values assigned to named properties). Bit masking also tends to make code more difficult to read, understand, and maintain. It may be necessary to use such techniques in very constrained environments, like when trying to cope with the storage limitation of local storage or in extreme cases when each bit over the network counts. This technique should only be considered when it is the last measure that can be taken to optimize size.

Strings

Unlike in languages like C, JavaScript strings are immutable. This means that once a string is created, it is not possible to modify it. However, it is still possible to create another string based on an operation on the original string. For example:

  • A substring of the original by picking individual letters or using String.substr().
  • A concatenation of two strings using the concatenation operator (+) or String.concat().

Beware of "stringly-typing" your code!

It can be tempting to use strings to represent complex data. Doing this comes with short-term benefits:

  • It is easy to build complex strings with concatenation.
  • Strings are easy to debug (what you see printed is always what is in the string).
  • Strings are the common denominator of a lot of APIs (input fields, local storage values, {{ domxref("XMLHttpRequest") }} responses when using responseText, etc.) and it can be tempting to only work with strings.

With conventions, it is possible to represent any data structure in a string. This does not make it a good idea. For instance, with a separator, one could emulate a list (while a JavaScript array would be more suitable). Unfortunately, when the separator is used in one of the "list" elements, then, the list is broken. An escape character can be chosen, etc. All of this requires conventions and creates an unneccessary maintenance burden.

Use strings for textual data and symbolic data. When representing complex data, parse strings and use the appropriate abstraction.

Objects

In JavaScript, objects can be seen as a bag of properties. With the object literal syntax, a limited set of properties are initialized; then properties can be added and removed. Property values can be values of any type, including other objects, which enables building complex data structures.

"Normal" objects, and functions

A JavaScript object is a mapping between keys and values. Keys are strings and values can be anything. This makes objects a natural fit for hashmaps. However, the non-standard __proto__ pseudo property must be used with caution. In environments that support it, assigning a new value to __proto__ also changes the value of the internal object prototype. In a context where it is not necessarily known where the string comes from (like an input field), caution is required: others have been burned by this. In that case, an alternative is to use a proper StringMap abstraction.

Functions are regular objects with the additional capability of being callable.

Arrays

Arrays are regular objects for which there is a particular relationship between integer-key-ed properties and the 'length' property. Additionally, arrays inherit from Array.prototype which provides to them a handful of convenient methods to manipulate arrays like indexOf (searching a value in the array) or push (adding an element to the array), etc. This makes arrays a perfect candidate to represent lists or sets.

Dates

When representing dates, the best choice is to use the built-in Date utility.

WeakMaps, Maps, Sets

Non-standard. Likely to be standardized as part of ECMAScript 6.

These data structures take object references as keys. A Set represents a set of objects, while WeakMaps and Maps associates a value to an object. The difference between Maps and WeakMaps is that in the former, object keys can be enumerated over. This allows garbage collection optimizations in the latter case.

One could implement Maps and Sets in pure ECMAScript 5. However, since objects cannot be compared (in the sense of "less than" for instance), look-up performance would necessarily be linear. Native implementations of them (including WeakMaps) can have look-up performance that is approximately logarithmic to constant time.

Usually, to bind data to a DOM node, one could set properties directly on the object or use data-* attributes. This has the downside that the data is available to any script running in the same context. Maps and WeakMaps make easy to privately bind data to an object.

TypedArrays

Non-standard. Likely to be standardized as part of ECMAScript 6.

See also

Revision Source

<p>Programming languages all have built-in data structures, but these often differ from one language to another. This article attempts to list the built-in data structures available in JavaScript and what properties they have; these can be used to build other data structures. When possible, comparisons with other languages are drawn.</p>
<p>The ECMAScript standard defines six data types:</p>
<ul>
  <li><span style="background-color:#ffff00;">Number</span></li>
  <li><span style="background-color:#ffff00;">String</span></li>
  <li><span style="background-color:#ffff00;">Boolean</span></li>
  <li><span style="background-color:#ffff00;">Null</span></li>
  <li><span style="background-color:#ffff00;">Undefined</span></li>
  <li><span style="background-color:#ffff00;">Object</span></li>
</ul>
<p>In the following sections, we will see how these types can be used to represent data and be combined to implement more complex data structures.</p>
<h2 id="Primitive_values">Primitive values</h2>
<p>All types except objects define immutable values. Specifically, strings are immutable (unlike in C for instance). We refer to values of these types as "primitive values." This is explained in more detail in the section on {{ anch("Strings") }} below.</p>
<h3 id="Booleans.2C_null.2C_and_undefined">Booleans, null, and undefined</h3>
<p>Within these types, four constants can be found: <code><span style="background-color:#ffff00;">true</span></code>, <code><span style="background-color:#ffff00;">false</span></code>, <code><span style="background-color:#ffff00;">null</span></code>, and <code><span style="background-color:#ffff00;">undefined</span></code>. Since these are constants, they cannot represent rich data (or data structures).</p>
<h3 id="Numbers">Numbers</h3>
<p>According to the ECMAScript standard, there is only one number type: the "<span style="background-color:#ffff00;">double-precision 64-bit binary format IEEE 754 value</span>". There is no specific type for integers. In addition to being able to represent floating-point numbers, it has some symbolic values: <code>+Infinity</code>, <code>-Infinity</code>, and <code>NaN</code> (not-a-number).</p>
<p>Although a number often represents only its value, JavaScript provides <a href="/en/JavaScript/Reference/Operators/Bitwise_Operators" title="en/JavaScript/Reference/Operators/Bitwise_Operators">some binary operators</a>. These can be used to represent several Boolean values within a single number using <a class="external" href="http://en.wikipedia.org/wiki/Mask_%28computing%29">bit masking</a>. This is usually considered a bad practice, however, since JavaScript offers other means to represent a set of Booleans (like an array of Booleans or an object with Boolean values assigned to named properties). Bit masking also tends to make code more difficult to read, understand, and maintain. It may be necessary to use such techniques in very constrained environments, like when trying to cope with the storage limitation of local storage or in extreme cases when each bit over the network counts. This technique should only be considered when it is the last measure that can be taken to optimize size.</p>
<h3 id="Strings">Strings</h3>
<p>Unlike in languages like C, <span style="background-color:#ffff00;">JavaScript strings are immutable</span>. This means that once a string is created, it is not possible to modify it. However, it is still possible to create another string based on an operation on the original string. For example:</p>
<ul>
  <li>A substring of the original by picking individual letters or using <a href="/en/JavaScript/Reference/Global_Objects/String/substr" title="substr"><code>String.substr()</code></a>.</li>
  <li>A concatenation of two strings using the concatenation operator (<code>+</code>) or <a href="/en/JavaScript/Reference/Global_Objects/String/concat" title="concat"><code>String.concat()</code></a>.</li>
</ul>
<h4 id="Beware_of_.22stringly-typing.22_your_code!">Beware of "stringly-typing" your code!</h4>
<p>It can be tempting to use strings to represent complex data. Doing this comes with short-term benefits:</p>
<ul>
  <li>It is easy to build complex strings with concatenation.</li>
  <li>Strings are easy to debug (what you see printed is always what is in the string).</li>
  <li>Strings are the common denominator of a lot of APIs (<a href="/en/DOM/HTMLInputElement" title="HTMLInputElement">input fields</a>, <a href="/en/Storage" title="Storage">local storage</a> values, {{ domxref("XMLHttpRequest") }} responses when using <code>responseText</code>, etc.) and it can be tempting to only work with strings.</li>
</ul>
<p>With conventions, it is possible to represent any data structure in a string. This does not make it a good idea. For instance, with a separator, one could emulate a list (while a JavaScript array would be more suitable). Unfortunately, when the separator is used in one of the "list" elements, then, the list is broken. An escape character can be chosen, etc. All of this requires conventions and creates an unneccessary maintenance burden.</p>
<p>Use strings for <span style="background-color:#ffff00;">textual data</span> and <span style="background-color:#ffff00;">symbolic data</span>. When representing complex data, parse strings and use the appropriate abstraction.</p>
<h2 id="Objects">Objects</h2>
<p>In JavaScript, <span style="background-color:#ffff00;">objects can be seen as a bag of properties</span>. With the <a href="/en/JavaScript/Guide/Values,_variables,_and_literals#Object_literals" title="en/JavaScript/Guide/Values,_variables,_and_literals#Object_literals">object literal syntax</a>, a limited set of properties are initialized; then properties can be added and removed. Property values can be values of any type, including other objects, which enables building complex data structures.</p>
<h3 id=".22Normal.22_objects.2C_and_functions">"Normal" objects, and functions</h3>
<p>A JavaScript object is a <span style="background-color:#ffff00;">mapping between keys and values</span>. <span style="background-color:#ffff00;">Keys are strings</span> and <span style="background-color:#ffff00;">values can be anything</span>. This makes objects a natural fit for <a class="external" href="http://en.wikipedia.org/wiki/Hash_table">hashmaps</a>. However, the non-standard <code><a href="/en/JavaScript/Reference/Global_Objects/Object/proto" title="__proto__">__proto__</a></code> pseudo property must be used with caution. In environments that support it, <span style="background-color:#ffff00;">assigning a new value to <code>__proto__</code> also changes the value of the internal object prototype</span>. In a context where it is not necessarily known where the string comes from (like an input field), caution is required: <a class="external" href="http://productforums.google.com/forum/#!category-topic/docs/documents/0hQWeOvCcHU">others have been burned by this</a>. In that case, an alternative is to use a proper <a class="external" href="http://code.google.com/p/google-caja/source/browse/trunk/src/com/google/caja/ses/StringMap.js?r=4779"><span style="background-color:#ffff00;">StringMap abstraction</span></a>.</p>
<p>Functions are regular objects with the additional capability of being callable.</p>
<h3 id="Arrays">Arrays</h3>
<p><a href="/en/JavaScript/Reference/Global_Objects/Array" title="Array">Arrays</a> are <span style="background-color:#ffff00;">regular objects</span> for which there is a <span style="background-color:#ffff00;">particular relationship between integer-key-ed properties and the 'length' property</span>. Additionally, arrays inherit from <code>Array.prototype</code> which provides to them a handful of convenient methods to manipulate arrays like <code><a href="/en/JavaScript/Reference/Global_Objects/Array/indexOf" title="en/JavaScript/Reference/Global_Objects/Array/indexOf">indexOf</a></code> (searching a value in the array) or <code><a href="/en/JavaScript/Reference/Global_Objects/Array/push" title="en/JavaScript/Reference/Global_Objects/Array/push">push</a></code> (adding an element to the array), etc. This makes arrays a perfect candidate to represent lists or sets.</p>
<h3 id="Dates">Dates</h3>
<p>When representing dates, the best choice is to use the built-in <a href="/en/JavaScript/Reference/Global_Objects/Date" title="en/JavaScript/Reference/Global_Objects/Date"><code>Date</code> utility</a>.</p>
<h3 id="WeakMaps.2C_Maps.2C_Sets">WeakMaps, Maps, Sets</h3>
<p>Non-standard. Likely to be standardized as part of ECMAScript 6.</p>
<p>These data structures take object references as keys. A Set represents a set of objects, while WeakMaps and Maps associates a value to an object. The difference between Maps and WeakMaps is that in the former, object keys can be enumerated over. This allows garbage collection optimizations in the latter case.</p>
<p>One could implement Maps and Sets in pure ECMAScript 5. However, since objects cannot be compared (in the sense of "less than" for instance), look-up performance would necessarily be linear. Native implementations of them (including WeakMaps) can have look-up performance that is approximately logarithmic to constant time.</p>
<p>Usually, to bind data to a DOM node, one could set properties directly on the object or use <code>data-*</code> attributes. This has the downside that the data is available to any script running in the same context. Maps and WeakMaps make easy to privately bind data to an object.</p>
<h3 id="TypedArrays">TypedArrays</h3>
<p>Non-standard. Likely to be standardized as part of ECMAScript 6.</p>
<h2 id="See_also">See also</h2>
<ul>
  <li><a class="link-https" href="https://github.com/nzakas/computer-science-in-javascript/">Nicholas Zakas collection of common data structure and common algorithms in JavaScript.</a></li>
</ul>
Revert to this revision