Ghosts in JavaScript Arrays!

© 2012, Martin Rinehart

Yes, there are ghosts that haunt JavaScript arrays. You do not need an exorcist to cast them out—you need knowledge. Whether you choose to be your own exorcist, or just live with the ghosts (they're relatively peaceful spooks) is up to you.

Prerequisite: You should have JavaScript basics, such as JavaScript with Native Objects, Volume III of the five-volume Frontend Engineering series, mastered. This discussion is near the edge where the wise coder starts to worry.

JavaScript arrays are inherently sparse. The existence of array[1] and array[3] does not imply the existence of array[2].

JavaScript's native Array object has methods Array.slice(), to extract a set of contiguous elements from an array, and Array.splice() to remove some contiguous elements and, optionally, replace them with others. Almost all documentation of these methods assumes that they are operating on zero-origin arrays of contiguous elements. This page looks at the other possibilities, one of which is the existence of ghost elements.

Array Defined

There is no true array in JavaScript. Arrays are a type of Object, a set of name/value pairs. Array elements' names are strings, as are all object property names. Unlike other objects, array elements' names look like small, non-negative integers: "0", "1", etc.

Arrays may be created with the Array() constructor or with an array literal:

// Using Array() constructor
var array0 = new Array( 10 );

// Using array literal
var array1 = ['cat', 'dog', 'mouse'];

What Is a Sparse Array?

The term "sparse array" refers both to an implementation technique and to the toolset available to the programmer. Assume that an array of ten elements, holding ten values, is created. This does not appear "sparse" to the programmer. Every element has a value.

Internally, as in JavaScript, a non-sparse array may be implemented as a sparse array so that assigning another element, say array[15] (when elements zero through nine are defined and length is ten) is not a problem. A non-sparse implementation could create a contiguous array of sixteen elements, leaving five empty spaces. We will leave implementation details to the implementors from now on and only consider the appearance the array has for the programmer.

For a programmer, a sparse array is one which may have non-contiguous subscripts. This may be created by assignments to non-contigous elements or by deletion of elements:

// non-contiguous by assignment
var array0 = [];
    array0[2] = 'yellow';
    array0[5] = 'indigo';

// non-contiguous by deletion
var array1 = ['red', 'orange', 'yellow'];
    delete array1[1];

array[i] === undefined

What do we know if we find that array[i] is undefined. (See the undefined page for more about undefined in JavaScript.) Actually, we don't even know what is undefined.

Name Undefined

If we have array[i] === undefined we have a special case of the general object[property_name] === undefined. This is true when property_name is undefined. In our case, the array subscript, i, when coerced to a string, is the property name. If there is no property named "1", then array[1] is undefined.

Value Undefined

On the other hand, there could be a property named "1" and yet array[1] might still be undefined. This occurs when the value of the property is undefined.

// contiguous but undefined
var array1 = ['red', 'orange', 'yellow'];
    array1[1] = undefined;

In this case, the name "1" is a valid property name in the array, but the value it finds is undefined.

Deleted Elements

When you use the delete operator the property name you deleted is removed from the array, the name and its associated value are discarded. In the following, the name "1" is gone:

// non-contiguous by deletion
var array1 = ['red', 'orange', 'yellow'];
    delete array1[1];

Did we say "gone"? Well, almost. If old Uncle Fred passed away but his ghost still haunts the attic, would you say he's "gone"?

The above array, after the deletion, has two elements named "0" and "2". However, array1.length is still three. Deleting elements does not change the array's length. (This is true even if you delete the final element.) Importantly, the non-existing elements have a certain ghostly existence.

Slicing Sparse Arrays

Slicing is simpler than splicing. It extracts values from an array, but does not change the array—it just returns the extracted values. It also has no ability to insert new values.

In the following example, we create a sparse array. Because we assign to array[9], it's length is ten. The results of the slices appear to be slices from a contiguous array containing elements zero through nine. (Remember that when the "end" argument is specified, the values are returned up to, but not including, "end" . You may want to make a copy of our Array Quick Reference page.)

var array = [];
    array[6] = 6;
    array[9] = 9;

alert( array.slice(2, 6) );
    // ,,,,

alert( array.slice(2, 7) );
    // ,,,,6

Splicing Sparse Arrays

Splicing, like slicing, returns a slice taken from an array. Unlike slicing it actually removes the elements from the array. We'll show this first. Second, splicing can insert new elements, which will come next.

Removing Elements with a Splice

In the following, remember that the second argument to Array.splice is not the "end" argument for Array.slice, it is the number of elements to remove.

var array = [];
    array[6] = 6;
    array[9] = 9;

alert( array.splice(2, 5) );
    // ,,,,6

alert( array );
    // ,,,,9

The slice removed is an array of five elements, four empty and the last one 6. These elements are removed from the array, the remainder of which is five elements long.

As with Array.slice(), the splice operation appears to work on an array where the non-existing elements have a certain amount of existence, after all. The ghosts count.

Inserting Elements with a Splice

Now we're ready for the final complication: adding elements at the spot of the deletion.

var array = [];
    array[6] = 6;
    array[9] = 9;

alert( array.splice(2, 5, 11, 12) );
    // ,,,,6

alert( array );
    // ,,11,12,,,9

The value returned by the splice operation is the same as it was without the insertion. For a clear mental picture, after the deletion you can think of the array as also unaffected by the insertion. Then an additional step inserts the new values. (The final array is seven long: original ten minus five deleted plus two inserted.) Again, ghosts count.

Conclusion

Slicing and splicing sparse arrays is defined as if the arrays were contiguous. Ghost elements fill in the discontinuous elements while the operations are performed. If you ask JavaScript about the ghosts, it will disavow their existence. They are undefined. If you ask JavaScript about Array.length you will see the evidence that ghosts are there. If you are comfortable with the concept of ghosts in your arrays, the slicing and splicing operations are highly regular.

A note on exorcism: If you delete an array, you delete the ghosts. (We do not claim that garbage collection is infallible in all implementations. We only claim that you will not see the ghosts, nor hear them in your code's attic.) Just copy the non-ghosts to a new array and delete the old one. Or, when you loop through arrays, check for undefined, even though the check is ambiguous.


This page is based on tests of the latest versions of Chrome, Firefox, Internet Explorer and Opera, 3 July, 2012. All four browsers gave identical results.

Feedback: MartinRinehart at gmail dot com.

# # #