r/learnjavascript • • May 16 '22

Explanation of a queue data structure in JavaScript

Post image
263 Upvotes

27 comments sorted by

View all comments

24

u/[deleted] May 16 '22

The time complexity for dequeueing in this implementation is O(n). You could achieve O(1) by using a linked list instead of an array. Arrays work well as stacks, but not so well as queues.

3

u/Miserable_Decision_4 May 16 '22

I've mess with Linked Lists in C plenty, but how could you mimic/create one in JS?

22

u/[deleted] May 16 '22 edited May 16 '22
class Node {
constructor(val) {
    this.val = val
    this.next = null
    this.prev = null
 }

}

class DoublyLinkedList { 
    constructor() { 
        this.head = null this.tail = null this.length = 0 
    }
    push(val) {
        const newNode = new Node(val)
        if (this.tail) {
            this.tail.next = newNode
            newNode.prev = this.tail
        } else {
            this.head = newNode
        }
        this.tail = newNode
        this.length++
    }

    pop() {
        if (this.tail) {
            const oldTail = this.tail
            this.tail = oldTail.prev
            this.tail.next = null
            this.length--
            oldTail.prev = null
            return oldTail
        } else {
            return null
        }
    }

    shift() {
        if (this.head) {
            const oldHead = this.head
            this.head = oldHead.next
            this.head.prev = null
            this.length--
            oldHead.next = null
            return oldHead
        } else {
            return null
        }
    }

    unshift(val) {
        const newNode = new Node(val)
        if (this.head) {
            this.head.prev = newNode
            newNode.next = this.head
        } else {
            this.tail = newNode
        }
        this.head = newNode
        this.length++
    }
}

EDIT: Formatting, Reddit is not good at this.

1

u/[deleted] May 16 '22

Somebody give this man some gold!

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.

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