在数组中添加值的最有效方法是什么？

Question

假设我有一个大小为N（其中N>0）的数组，是否有更高效的方法可以在不需要O(N+1)步的情况下将元素添加到数组的开头？

实际上，在代码中，我目前正在做的是：

function prependArray(value, oldArray) {
  var newArray = new Array(value);

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

  return newArray;
}

- samccone

---

尽管我喜欢链表和指针，但我觉得使用本地JS数据类型可能有更有效的方法来完成任务。 - samccone

@samccone：是的，请忽略我的评论，抱歉，我以为你说的是Java :P - GWW

无论是Java、JavaScript、C还是Python，数组与链表之间的复杂度权衡是相同的。在JavaScript中，由于没有内置类（不像Java）来处理链表，因此链表可能会非常笨重。但是，如果你真正想要的是O(1)的插入时间，那么你确实需要一个链表。 - mgiuca

需要克隆它吗？ - Ryan Florence

如果需要克隆它，则unshift是不合适的，因为它会改变原始数组而不是创建副本。 - mgiuca

Answer 1

对于大 O 表示法来说我不确定是否更有效率，但肯定使用 unshift 方法更加简洁：

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

[编辑]

这个jsPerf质量检测表明，unshift在至少一些浏览器中要稍微快一些，而且无论可能有不同的大O性能 如果您可以接受就地修改数组。 如果您真的不能改变原始数组，那么您将执行以下代码片段之类的操作，但它似乎与您的解决方案没有明显的优势：

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

[编辑2]

为了完整起见，可以使用下面的函数替代OP的示例prependArray(...)，以利用数组的unshift(...)方法：

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

var x = [1, 2, 3];
var y = prepend(0, x);
// x => [1, 2, 3];
// y => [0, 1, 2, 3];
console.log({ x, y });

- maerics

---

谁决定把 prepend 改名为 "unshift"？ - Scott Stafford

在这种数组操作中，“unshift”听起来更合适（它会将元素...或多或少地物理移动）。而对于链表，“prepend”更加适用，因为你会“字面上”在开头添加元素。 - CamilB

unshift是shift的互补函数。将其称为“prepend”会有些奇怪。unshift的作用就像push对应pop一样。 - Sir Robert

这个解决方案只有一个问题。unshift()方法返回的是其长度，而不是数组本身，与这个答案描述的不同。http://www.w3schools.com/jsref/jsref_unshift.asp - iDVB

pushе’ҢunshiftйғҪеҢ…еҗ«еӯ—жҜҚuпјҢиҖҢpopе’ҢshiftеҲҷжІЎжңүгҖӮ - user1663023

Answer 2

使用ES6，您现在可以使用扩展运算符spread operator在原始元素之前插入新元素来创建一个新的数组。

// 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]);

更新 2018-08-17：性能

我旨在提供一种我认为更易记且更简洁的替代语法。需要注意的是，根据某些基准测试（请参见此其他答案），这种语法明显较慢。除非您在循环中执行多个此类操作，否则这可能并不重要。

- Frank Tan

---

这段内容可以翻译为：“根据2017年的标准，这应该被投票赞成。它很简洁。通过使用'spread'，它返回了新的数据流，这对于进一步修改非常有用。它也是纯净的（意思是a和b不会受到影响）。” - Simon

你没有提到相对于 unshift 所需的时间。 - Shashank Vivek

感谢@ShashankVivek。我打算提供一种我认为更易记且更简洁的替代语法。我会进行更新。 - Frank Tan

@FrankTan：干杯 :) +1 - Shashank Vivek

如果 a 很大，这种方法会导致堆栈溢出吗？ - Ayxan Haqverdili

Answer 3

如果你想将一个数组添加到另一个数组的前面，使用 concat 更有效率。 因此：

const newArray = [1, 2, 3].concat([4, 5]);
newArray; // [1, 2, 3, 4, 5]

但是这仍然会随着oldArray的大小而呈O(N)级增长。不过，与手动迭代oldArray相比，它更有效率。另外，根据具体情况，这可能会对你有所帮助，因为如果你要添加很多值，最好先将它们放入一个数组中，然后再在末尾连接oldArray，而不是逐个添加到开头。

由于数组以连续内存的方式存储，并且第一个元素位于固定位置，所以在oldArray的大小上做到比O(N)更快是不可能的。如果您想在第一个元素之前插入元素，则需要移动所有其他元素。如果您需要避免这种情况，请按照@GWW所说使用链表或其他数据结构。

- mgiuca

---

哦，是的，我忘了 unshift。但请注意，a）它会改变 oldArray 的值，而 concat 不会（所以根据情况选择哪一个更好），而且 b）它只插入一个元素。 - mgiuca

哇，这慢多了。嗯，就像我说的，它在复制数组（还创建了一个新的数组 [0]），而 unshift 则是原地修改。但两者都应该是 O(N) 的。还有谢谢你提供那个网站的链接，看起来非常实用。 - mgiuca

这对于一行代码很好，因为concat返回数组，而unshift返回新长度。 - Bernardo Dal Corno

Answer 4

如果你想要将一个数组（a1）和另一个数组（a2）拼接在一起，可以使用以下方法：

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

- uroslates

Answer 5

以不可变的方式，这可能是最好的方式：

const x = 1
const list = [2, 3, 4]
const newList = [x].concat(list) // [1, 2, 3, 4]

- carlesba

Answer 6

我进行了不同的数组头部插入方法的新测试。

对于小型数组（<1000个元素），最佳方法是使用“for”循环和“push”方法组合。

对于大型数组，Unshift方法成为领导者。

但是这种情况仅适用于Chrome浏览器。 在Firefox中，unshift具有出色的优化，并在所有情况下更快。

ES6扩展在所有浏览器中都比其他方法慢100多倍。

https://jsbench.me/cgjfc79bgx/1

- John Klimov

---

很棒的答案！但为了确保您不会失去其中的一部分，您可以在这里重现您的测试用例（可能包括一些样本运行结果），以防 jsbench 不可用。 - ruffin

你只是在前面添加一个值，而使用spread操作符时，你会创建一个新的大数组，这就是为什么unshift快100倍...如果你将一个完整的数组添加到另一个完整的数组中，那么结果会非常不同，而spread操作符则“只”慢了4倍，因为它在内存中创建了一个全新的数组，而unshift则是原地操作。请参考此基准测试：https://jsbench.me/oul3x61nxy/1 - Octo Poulos

Answer 7

如果您需要保留旧数组，可以对旧数组进行切片，并将新值插入到切片的开头。

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
*/

- kennebec

Answer 8

调用unshift仅返回新数组的长度。 因此，为了在开头添加元素并返回一个新数组，我做了这个：

let newVal = 'someValue';
let array = ['hello', 'world'];
[ newVal ].concat(array);

或者简单地使用扩展运算符：

[ newVal, ...array ]

这样，原始数组将保持不变。

- rehman_00001

Answer 9

有一种特殊的方法：

a.unshift(value);

但如果你想在数组前面添加多个元素，最好使用以下方法：

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]

- bjornd

---

不要使用 push 方法，因为它会将数组添加到最后一个参数。相反，使用 unshift 将数组添加为第一个参数：var a = [4, 5]; a.unshift([1,2,3]); console.log(a); // -> [[4, 5], 1, 2, 3] - bjornd

没错！您需要使用 Array.prototype.unshift.apply(a,b);。 - david

Answer 10

我刚刚在Chrome上对4种算法进行了基准测试：

原地算法：

// 1) splice method
{
    let x = [8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44];
    const y = [5, 6, 99, 5, 3, 4];
    x.splice(0, 0, ...y); // 87'426 ops/s (but big variation of 35%)
    // x is [5, 6, 99, 5, 3, 4, 8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44]
}

// 2) unshift method
{
    let x = [8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44];
    const y = [5, 6, 99, 5, 3, 4];
    x.unshift(...y); // 69'471 ops/s
    // x is [5, 6, 99, 5, 3, 4, 8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44]
}

copy:

// 3) spread operator
{
    const x = [8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44];
    const y = [5, 6, 99, 5, 3, 4];
    const z = [...y, ...x]; // 17'118 ops/s
    // z is [5, 6, 99, 5, 3, 4, 8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44]
}

// 4) concat method
{
    const x = [8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44];
    const y = [5, 6, 99, 5, 3, 4];
    const z = y.concat(x); // 6'286 ops/s
    // z is [5, 6, 99, 5, 3, 4, 8, 4, 1, 4, 124, 1, 14, 11, 9, 100, 6, 44]
}

总结：如果你想要在原地进行前置操作，那么unshift和splice都是不错的选择；如果你需要复制数组，则展开运算符（spread operator）似乎是最好的选择……至少在Chrome上是这样。

- Octo Poulos