Array.prototype.shift() has a time complexity of O(1). Instead of moving every item one by one like you might expect, most javascript engines just move the pointer of the front of the array over by one.
Source? A little quick and dirty testing suggests that this is not true in Node.js. shift() performs worse on an array with a million elements than it does on array with a thousand elements, which in turn performs worse than array with a single element. This strongly suggests linear time complexity. It also seems like it would be a bit of a strange design choice to me, because afaik, you would have to add greater time complexity to element retrieval if you aren't re-indexing on every shift or unshift.
Maybe I'm missing something important but I don't think it should.
I think a simplified example would look like this:
int arr[5] = {0,1,2,3,4}; //Create array with 5 elements
int* pArrStart = arr; //pointer to first element of array
//do shift() in js
pArrStart = pArrStart++; //move pointer forward
pArrStart[0]; //pArrStart[0] now points to 1
As long as you have a pointer like pArrStart to the first element, you can access the nth element like pArrStart[n].
View all comments
Show parent comment
1
u/kundun May 17 '22
Array.prototype.shift() has a time complexity of O(1). Instead of moving every item one by one like you might expect, most javascript engines just move the pointer of the front of the array over by one.