According to the test results, push() outperforms unshift().

js>function foo() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.unshift(1); return((new Date)-start)}
js>foo()
2190
js>function bar() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.push(1); return((new Date)-start)}
js>bar()
10

function foo() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.unshift(1); return((new Date)-start)}
console.log(foo())

function bar() {a=[]; start = new Date; for (var i=0;i<100000;i++) a.push(1); return((new Date)-start)}
console.log(bar());

Update

The above experiment does not consider array order. To make an accurate comparison, the pushed array must be reversed. Nonetheless, push and then reverse still exhibits better performance by approximately 10ms in my case on chrome using this code snippet:

var a=[]; 
var start = new Date; 
for (var i=0;i<100000;i++) {
  a.unshift(1);
}
var end = (new Date)-start;
console.log(`Unshift time: ${end}`);

var a=[];
var start = new Date;
for (var i=0;i<100000;i++) {
  a.push(1);
}

a.reverse();
var end = (new Date)-start;
console.log(`Push and reverse time: ${end}`);

If you're interested in how the v8 implementation works, check out the source code. When using unshift, the array will adjust itself to accommodate the arbitrary number of arguments passed.

UnshiftImpl eventually calls AddArguments with a start_position of AT_START, which leads to this else statement:

  // If the backing store has enough capacity and we add elements to the
  // start we have to shift the existing objects.
  Isolate* isolate = receiver->GetIsolate();
  Subclass::MoveElements(isolate, receiver, backing_store, add_size, 0,
                         length, 0, 0);

This then takes us to the MoveElements function.

  static void MoveElements(Isolate* isolate, Handle<JSArray> receiver,
                           Handle<FixedArrayBase> backing_store, int dst_index,
                           int src_index, int len, int hole_start,
                           int hole_end) {
    Heap* heap = isolate->heap();
    Handle<BackingStore> dst_elms = Handle<BackingStore>::cast(backing_store);
    if (len > JSArray::kMaxCopyElements && dst_index == 0 &&
        heap->CanMoveObjectStart(*dst_elms)) {
      // Update all the copies of this backing_store handle.
      *dst_elms.location() =
          BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms, src_index))
              ->ptr();
      receiver->set_elements(*dst_elms);
      // Adjust the hole offset as the array has been shrunk.
      hole_end -= src_index;
      DCHECK_LE(hole_start, backing_store->length());
      DCHECK_LE(hole_end, backing_store->length());
    } else if (len != 0) {
      WriteBarrierMode mode = GetWriteBarrierMode(KindTraits::Kind);
      dst_elms->MoveElements(heap, dst_index, src_index, len, mode);
    }
    if (hole_start != hole_end) {
      dst_elms->FillWithHoles(hole_start, hole_end);
    }
  }

It's worth noting that v8 categorizes different element kinds based on the content of the array, impacting performance.

Predicting the exact performance can be tricky as it depends on various factors like the types of elements passed and the presence of holes in the array. Generally speaking, since unshift requires allocating more space in the array, it likely operates at O(N) complexity (scaling linearly with the number of elements). Feel free to correct me if I'm mistaken!

Absolutely correct! The time complexity of push() is O(1) while the time complexity of unshift() is O(n). This is because unshift() needs to shift all existing elements in the array to make space for the new element, whereas push() simply adds the new element at the end without shifting any other elements.

However, it's important to note that even though the average time complexity of push() is O(1), in some cases it can be O(n) due to dynamic memory allocation.

To avoid the O(n) complexity when inserting elements into an array, you can initialize the array with a specific size and fill it with placeholder values:

1. Initialize the array with the required size and fill it with dummy values.

   let array = new Array(size).fill(0)

2. Iterate through the elements you want to insert and update their values based on index.

for (let i = 0; i < size; i++) {
  array[i] = i
}

By directly assigning values to specific positions in the array instead of using push(), we optimize memory usage and reduce complexity. This method ensures that only necessary memory is allocated, minimizing wastage.

Utilizing a combination of fast unshift and push operations within Arrays can be achieved by placing data in the middle of the C-level array, similar to how it is done in perl.

Another approach involves using two separate C-level arrays, where push appends to one array and unshift appends to the other. However, the benefits of this method compared to the first one are not clear at this time.

Regardless of the implementation strategy chosen, performing a push or an unshift operation will typically take O(1) time when there is sufficient memory available in the internal C-level array. In cases where reallocation is necessary, which requires copying old data to a new memory block, the operation may take at least O(N) time.

In my opinion, the performance of unshift on a JavaScript engine will vary based on whether it uses a linked list or not.

Answer Summary

• push: O(n) time complexity
• unshift: O(m + n) time complexity
• pop: O(1) time complexity
• shift: O(n) time complexity, where n is the length of the array.

Explanation of variables:

• m: length of existing array
• n: number of elements to be added

Detailed Answer

This code snippet demonstrates an Array Data Structure implementation in JavaScript.

class XArray {
  constructor() {
    Object.defineProperties(this, {
      length: {
        writable: true,
        enumerable: false,
        configurable: false,
        value: 0,
      },
    });

    /** Configure the output of the Array object to return only values */
    const runtimeConsole = console;
    console = {
      ...console,
      log: function (data) {
        if (XArray.isArray(data)) {
          runtimeConsole.log(Object.values(data));
        } else runtimeConsole.log(data);
      },
    };
  }

  /**
   * Adds element(s) to the end of the array
   *
   * Time Complexity: O(n)
   * @param  {...any} elements
   */
  push(...elements) {
    for (const element of elements) {
      this[this.length] = element;
      this.length++;
    }
    return this.length;
  }

  pop() {
    const element = this[this.length - 1];
    delete this[this.length - 1];
    this.length--;
    return element;
  }

  /**
   * Adds elements to the beginning of the array
   *
   * Time Complexity: O(m + n)
   *
   * @param  {...any} elements
   */
  unshift(...elements) {
    for (let i = this.length - 1; i >= 0; i--) {
      this[i + elements.length] = this[i];
    }
    for (const index in elements) {
      this[index] = elements[index];
      this.length++;
    }
    return this.length;
  }

  shift() {
    const element = this[0];
    this.length--;

    for (let i = 0; i < this.length; i++) {
      this[i] = this[i + 1];
    }
    delete this[this.length];
    return element;
  }

  static isArray(array) {
    return array instanceof XArray;
  }
}

Pushing elements into an array is faster than unshifting them because unshift requires shifting all the existing elements to the left after adding the new element. Therefore, the time complexity for unshift is O(n) compared to O(1) for push.

When using the unshift method, the time complexity is O(n). For example, if we have an array like

["cat", "dog"]

On the other hand, when using the push method, the time complexity is O(1). If we take the same array

["cat", "dog"]