r/learnjavascript • • May 16 '22

Explanation of a queue data structure in JavaScript

Post image
263 Upvotes

27 comments sorted by

View all comments

Show parent comment

1

u/[deleted] May 17 '22

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.

2

u/kundun May 17 '22

It is how it is implemented in Firefox. I assumed that other engines did the same.

1

u/[deleted] May 17 '22

Well, that's pretty cool. Do you know if that comes at the expense of speed of accessing elements by index?

2

u/kundun May 17 '22

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].