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;
}
This question is related to
javascript
arrays
prepend
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]
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];
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
*/
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]
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]
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._x000D_
const a = [1, 2, 3];_x000D_
console.log([0, ...a]);// Prepend an array._x000D_
const a = [2, 3];_x000D_
const b = [0, 1];_x000D_
console.log([...b, ...a]);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.
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.
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.
Example of prepending in-place:
var A = [7,8,9]_x000D_
var B = [1,2,3]_x000D_
_x000D_
A.unshift(...B)_x000D_
_x000D_
console.log(A) // [1,2,3,7,8,9]I have some fresh tests of different methods of prepending. For small arrays (<1000 elems) the leader is for cycle coupled with a push method. For huge arrays, Unshift method becomes the leader.
But this situation is actual only for Chrome browser. In Firefox unshift has an awesome optimization and is faster in all cases.
ES6 spread is 100+ times slower in all browsers.
Calling unshift only returns the length of the new array.
So, to add an element in the beginning and to return a new array, I did this:
let newVal = 'someValue';
let array = ['hello', 'world'];
[ newVal ].concat(array);
or simply with spread operator:
[ newVal, ...array ]
This way, the original array remains untouched.
Source: Stackoverflow.com