loading...
Cover image for Three data structures you do not need to know in 2020

Three data structures you do not need to know in 2020

brettimus profile image Boots ・4 min read

It seems that you, dear reader, have been compelled to brush up on your data structures, or at least the ones that you will never, ever need to know. Ever.

I commend your studiousness. As a reward, here are three useless data structures that you'll never need to know about, neither now nor for the remainder of the current garbage year that we're calling ✨2020✨.

🌳 1. The giving trie

The giving trie is a variant of the classic German-speaking trie, except this data structure is only half German. (Don't worry, the other half is actually quite friendly1.)

The giving trie has no interface to insert new items. It can only remove its elements until there’s nothing left but a nebulous melancholic log message that confuses young children and adults alike.

class GivingTrie {
  OLD = Symbol("I am now an old trie")
  constructor(...initialTrieStuff) {
    this._trieStuff = initialTrieStuff
  }
  takeUntil(signal = OLD) {
    if (signal === OLD) {
      const everything = this._trieStuff
      this._trieStuff = []
      return everything
    }
    throw new Error('I only get old. That is all I do. I am a Trie.')
  }
  takeMore() {
    const remainingTrieThings = this._trieStuff?.length
    if (remainingTrieThings) {
      return this._trieStuff.pop()
    }
    console.log("All I have left is this log message.")
    console.log("But I am happy.")
    console.log("But there is nothing left of me.")
    console.log("Also I am a trie.")
  }
}

/*********************
 *** Example Usage *** 
 *********************/

const gt = new GivingTrie(1, 2, 3)
gt.takeUntil(GivingTrie.OLD)
gt.takeMore()
// Prints:
// => All I have left is this log message.
// => But I am happy.
// => But there is nothing left of me.
// => Also I am a trie.

πŸ“ Also worth noting is that the giving trie is, in fact, nothing like a trie at all.

πŸ’ 2. The linked-by-a-barrel-of-monkeys list

Typically, linked lists have banal, straight pointers between their nodes.

The linked-by-a-barrel-of-monkeys list, on the other hand, is a linked list where each node is connected by tiny monkeys that link arms with each other. Hence, its name.

omfg two baby chimps embracing each other

The thing about these tiny monkeys is that they are constantly moving around, changing places, etc, which makes the next and prev methods much more whimsical than a traditional linked list.

Usage of next and prev is subject to random monkey-business. Their values change on each access, and a node could possibly link back to itself or start flying through Oz.

Proper use of the next and prev accessors should guard against potential FlyingToOzErrors, since these are thrown roughly 10% of the time you access said properties. (The monkeys really like Oz.)

One last note: This data structure always has a tail property, which, when accessed, returns a gif of a surprised or angered monkey.

class FlyingToOzError extends Error {
  constructor(message) {
    super(message);
    this.name = 'FlyingToOzError';
  }
};

class LinkedBarrelOfMonkeysList {
  // Utility getter that might throw a FlyingToOzError
  pickRandomOrFlyToOz = list => {
    const shouldFlyToOz = !Math.floor(Math.random() * 10)
    if (shouldFlyToOz)
      throw new FlyingToOzError('OOaAOo I FLY TO OZ!')
    return list[Math.floor(Math.random() * list.length)]
  }

  constructor(...initialValues) {
    const bomInstance = this;
    this._items = initialValues
      .map(value => ({
         value,
         get prev() {
           return pickRandomOrFlyToOz(bomInstance._items)
         },
         get next() {
           return pickRandomOrFlyToOz(bomInstance._items)
         }
       }))
    Object.defineProperty(this, 'tail', {
      writable: false,
      get: () => console.warn(
        'OOoOOAAaAA NO POL TAIL!',
        'https://media.giphy.com/media/l378hyTQvH3bCdD2g/giphy.gif'
      )
    })
  }
}


/*********************
 *** Example Usage *** 
 *********************/

const bomList = new LinkedBarrelOfMonkeysList(1, 2, 3)
bomList.tail 
// This will print a warning, along with a link to the gif below

Confused monkey

OOoOOAAaAA NO POL TAIL

Say what you will about these nondeterministic rascalsβ€”they’re a heck of a lot more fun than your traditional linked lists.

🀀 3. The lack of priorities queue

The lack of priorities queue uses a first-Doritos-last-whatever algorithm to resolve which element it should return next.

The function for accessing the next item in the queue is asynchronous, and does not have a timeout mechanism. You just have to chill and be patient.

A common workaround to this queue’s inconsistent priority ranking is to wrap known high priority items inside a struct-like Tortilla, as if it were a virtual burrito. Tortillas provide a priority boost to their wrapped values2.

Note that a nap subroutine may be implemented to reduce lag, but it’s not guaranteed to work.

For this data structure, I provide no reference implementation. I might write one like next week or something or whatever.

πŸ€¦πŸ»β€β™‚οΈ Conclusion

There you have it. Three useless data structures that you will never use. I hope you learned something useless.

Frankly, I'm kind of surprised you made it this far. This is complicated stuff. Really complicated! Why not reward yourself with a little nap?

sloth takin' a nap

this guy knos what i'm talkin bout

πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€

πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€

πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€
πŸ’€

...Hey! If you're still awake why not hit the follow button? You'll get a notification when I implement that LackOfPrioritiesQueue!


  1. Also Entschuldigung. Ich muss es hier sagen dass die Deutsche Sprache, Kultur, und Menschen gefallen mir sehr. (Ich trΓ€ge manchmal Lederhosen. Ernsthaft!) Ich wollte am Anfang nur einen kleinen Witz machen. Hoffentlich ist der nicht ganz in die Hose gegangen πŸ˜… πŸ‡©πŸ‡ͺ πŸ₯¨ 🍻 ❀️ ↩

  2. In some cases, Durum wraps may also be used. ↩

Posted on Apr 3 by:

brettimus profile

Boots

@brettimus

I like things that I don't understand on the first try

Discussion

markdown guide