Understanding Dense and Sparse Arrays in JavaScript

Posted on: by Rajeev Edmonds

Arrays are an integral part of almost every programming language. We extensively use this term in domains (electronics, construction) other than software development. JavaScript arrays are primarily are of two types, viz., Dense Arrays and Sparse Arrays.

We generally work with the former type, but the latter one exists too. Let's understand the difference between the two, and specifically, how to handle the latter one.

A colorful brick wall

JavaScript arrays are objects, which inherit all of their traits from Array.prototype and behave like a typical ordered list-like data structure.

Beginners often confuse an array as a primitive data type. If you want to create a primitive one, go for a typed array.

In JavaScript, dense array elements get contiguous memory blocks, while sparse one have non-contiguous memory locations. Internally, the latter one represents itself in the form of a linked sparse matrix.

Here's how we use a dense array. That's the most common use case in our day-to-day programming. There's no hole between the elements.

// A dense array
const a = [ 1, 2, 3, 4, 5 ];

console.log(a); // => [ 1, 2, 3, 4, 5 ]
console.log(a.length); // => 5

And, here's a sparse array! Note, the third element has a hole. There's nothing in that location.

// A sparse array
const a = [ 1, 2, , 3, 4, 5 ];
console.log(a); // => [ 1, 2, <empty slot>, 3, 4, 5 ]
console.log(a.length); // => 6

Pay attention to the length property of a sparse array. It's six, though only five elements exist. Furthermore, these filled elements are allocated non-contiguous memory locations.

A sparse array can be declared in different ways. Let's take a look!

// Different ways a sparse array can be created
let a = new Array(10);
let b = [];
b[25] = 'Hello World!';
const c = [ 1, 2, 3, 4, 5 ];
delete c[1]; // Deleting second element creates a hole (sparse array)
console.log(a); // => [ <10 empty slots> ] length: 10
console.log(b, b[0], b.length); // => [ <10 empty slots>, ... ] undefined 26

The last line in the code snippet shown above is worth noticing. You can see that trying to access a hole b[0] returns undefined which is confusing.

Accessing a non-existing array index (hole) returns undefined in JavaScript. It's different from the undefined assigned to an existing variable. We can confirm the non-existing index through the Object.keys() method.

// Display available array keys (index values)
const a = [ 1, 2, , 3, 4, 5 ];

console.log(Object.keys(a)); // => [ "0", "1", "3", "4", "5" ]

So, if accessing a sparse array hole and an element with an undefined value gives the same undefined result, how do we distinguish a hole from a valid element reference?

Here's a simple check for the same.

// Check for a hole in a sparse array
const sparseArray = [ undefined, , ];

console.log(sparseArray.hasOwnProperty(0)) // => true
console.log(sparseArray.hasOwnProperty(1)); // => false

And, what about copying a sparse array?

You can try it in 3 different ways. An assignment operator, use of a spread [ ...Object ] operator, or use of slice() method.

Which one is the correct way to make a copy (not a reference) of a sparse array? Let's see!

// Making a copy of a sparse array
let source = [ undefined, , ];
let badCopy = source; // => it's a reference and not a copy
let anotherBadCopy = [ ...source ];
let goodCopy = source.slice();

console.log(source); // => [ undefined, <1 empty slot> ]
console.log(anotherbadCopy); // => [ undefined, undefined ]
console.log(goodCopy) // => [ undefined, <1 empty slot> ]

So, you can see, it's the slice() method that gives the correct result. The spread operator replaces the hole with an element having an undefined value. That's not what we want.

I've never used sparse arrays while coding real-world projects. Whenever there is a need to use one, I'll suggest using either a Map or a Set data structure.

Previous Post: Client-Developer Relationship - Demystified
Next Post: Git Objects - How They Work Internally?