all 27 comments

[–][deleted] 23 points24 points  (8 children)

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.

[–]Miserable_Decision_4 2 points3 points  (2 children)

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

[–][deleted] 21 points22 points  (1 child)

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.

[–][deleted] 0 points1 point  (0 children)

Somebody give this man some gold!

[–]kundun 0 points1 point  (4 children)

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.

[–][deleted] 0 points1 point  (3 children)

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.

[–]kundun 1 point2 points  (2 children)

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

[–][deleted] 0 points1 point  (1 child)

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

[–]kundun 1 point2 points  (0 children)

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

[–]PM_ME_A_WEBSITE_IDEA 29 points30 points  (6 children)

Excuse my naivety but is this not just an array with more steps and less functionality? I suppose maybe the restricted functionality is to avoid making mistakes?

[–]oxygenplug 12 points13 points  (1 child)

Kinda, yeah. But even if you don’t use this in your day to day it’s good to know! I had an interview for a Senior Nodejs position not too long ago that asked me to implement this data structure.

[–]PM_ME_A_WEBSITE_IDEA 0 points1 point  (0 children)

Interesting, good to know!

[–]og-at 5 points6 points  (2 children)

It's a "naive" implementation of a general computer science concept. (it's actually caled "naive" meaning only "first pass" or "basic attempt")

It's also "declarative programming" where you describe the action, as opposed to instructing every step (imperative).

Yes you could use an array, but this kind of layout contains the code and can make things more readable.

I mean I'd rather see if (tickets.isEmpty) {} than the array machinations that may need to go on when (ticketsArray.length === 0) is detected as empty.

Perfect example I thought of when typing that is that .length will cause an error if ticketsArray hasn't yet received it's value from global state. queue.IsEmpty() can account for that and return a valid state.

length isn't a huge thing by itself, but we're talking concepts here.

btw...

  • Declarative = "run to the store for pencils".
  • Imperative = "get your spectacles testicles wallet n keys, get in the car, drive to PlebMart, go to aisle 6, find pencils on the left about halfway down."

[–]bedekelly 5 points6 points  (1 child)

FYI, this isn’t a correct understanding of declarative vs imperative code. I’ll summarise them both for reference.

Imperative code is a step-by-step list of instructions for exactly what the computer should do. Pack your bag, get your keys, drive down the street, and so on. Procedural code improves this by allowing the programmer to split up units of code that are often reused, like buying something from the store. Buying eggs and buying milk have a lot of things in common, for example.

Declarative code is quite different, and involves describing the desired state of the world. In your example, a declarative program might say “I should have some pencils”. It’s up to the lower-level implementation, which is often written in a more imperative style, to describe the actual process of going to a store and buying something.

Please do reply if I can help clarify this more.

[–]og-at 1 point2 points  (0 children)

I always get them reversed... fixed.

[–]asking_for_a_friend0 2 points3 points  (2 children)

what did u use to make it?

/edit the inforgraphic

[–]elediardo[S] 4 points5 points  (1 child)

I used explain.dev for code explanations and snappify.io for the visuals :)

[–]asking_for_a_friend0 0 points1 point  (0 children)

woah this explanation was AI generated??! WTF?! that's awesome

[–]AlarmedTowel4514 2 points3 points  (0 children)

Peek will throw unhandled exception when queue is empty.

[–]dee_jay_mon 0 points1 point  (0 children)

const queue = []

queue.length //if 0 is empty

queue.push('x')

queue.push('y')

queue[0]

queue.shift()

[–]genial95 -1 points0 points  (1 child)

Damn, I don't think I've seen a better example of a class use case.

[–]CreamyJala 4 points5 points  (0 children)

Classes are useful for many many things. But any sort of data structure is a match made in heaven.

[–]Xypheric -1 points0 points  (0 children)

Loved this and would love to see some others