Most efficient way to prepend a value to an array

Most efficient way to prepend a value to an array

Assuming I have an array that has a size of N (where N > 0), is there a more efficient way of prepending to the array that would not require O(N + 1) steps?
In code, essentially, what I currently am doing is
function prependArray(value, oldArray) {
var newArray = new Array(value);

for(var i = 0; i < oldArray.length; ++i) { newArray.push(oldArray[i]); } return newArray; }

Solutions/Answers:

Solution 1:

I’m not sure about more efficient in terms of big-O but certainly using the unshift method is more concise:

var a = [1, 2, 3, 4];
a.unshift(0);
a; // => [0, 1, 2, 3, 4]

[Edit]

This jsPerf benchmark shows that unshift is decently faster in at least a couple of browsers, regardless of possibly different big-O performance if you are ok with modifying the array in-place. If you really can’t mutate the original array then you would do something like the below snippet, which doesn’t seem to be appreciably faster than your solution:

a.slice().unshift(0); // Use "slice" to avoid mutating "a".

[Edit 2]

Related:  Node JS, traditional data structures? (such as Set, etc), anything like Java.util for node?

For completeness, the following function can be used instead of OP’s example prependArray(...) to take advantage of the Array unshift(...) method:

function prepend(value, array) {
  var newArray = array.slice();
  newArray.unshift(value);
  return newArray;
}

var x = [1, 2, 3];
var y = prepend(0, x);
y; // => [0, 1, 2, 3];
x; // => [1, 2, 3];

Solution 2:

With ES6, you can now use the spread operator to create a new array with your new elements inserted before the original elements.

// Prepend a single item.
const a = [1, 2, 3];
console.log([0, ...a]);
// Prepend an array.
const a = [2, 3];
const b = [0, 1];
console.log([...b, ...a]);

Update 2018-08-17: Performance

I intended this answer to present an alternative syntax that I think is more memorable and concise. It should be noted that according to some benchmarks (see this other answer), this syntax is significantly slower. This is probably not going to matter unless you are doing many of these operations in a loop.

Solution 3:

If you are prepending an array to the front of another array, it is more efficient to just use concat. So:

var newArray = values.concat(oldArray);

But this will still be O(N) in the size of oldArray. Still, it is more efficient than manually iterating over oldArray. Also, depending on the details, it may help you, because if you are going to prepend many values, it’s better to put them into an array first and then concat oldArray on the end, rather than prepending each one individually.

Related:  HTML5 Drag and Drop effectAllowed and dropEffect

There’s no way to do better than O(N) in the size of oldArray, because arrays are stored in contiguous memory with the first element in a fixed position. If you want to insert before the first element, you need to move all the other elements. If you need a way around this, do what @GWW said and use a linked list, or a different data structure.

Solution 4:

If you would like to prepend array (a1 with an array a2) you could use the following:

var a1 = [1, 2];
var a2 = [3, 4];
Array.prototype.unshift.apply(a1, a2);
console.log(a1);
// => [3, 4, 1, 2]

Solution 5:

f you need to preserve the old array,
slice the old one and unshift the new value(s)
to the beginning of the slice.

var oldA=[4,5,6];
newA=oldA.slice(0);
newA.unshift(1,2,3)

oldA+'\n'+newA

/*  returned value:
4,5,6
1,2,3,4,5,6
*/

Solution 6:

There is special method:

a.unshift(value);

But if you want to prepend several elements to array it would be faster to use such a method:

var a = [1, 2, 3],
    b = [4, 5];

function prependArray(a, b) {
    var args = b;
    args.unshift(0);
    args.unshift(0);
    Array.prototype.splice.apply(a, args);
}

prependArray(a, b);
console.log(a); // -> [4, 5, 1, 2, 3]