Data structures are ways of organizing information with optimal ‘runtime complexity’ for adding, editing or removing records. Today, I will explore queues, stacks and linked lists.

Queue

Queues are like your typical ticketing counter. Records, or ‘customers’ will enter on one side and exit on another.

This is classified as a First-In-First-Out system. If I enter the deli before you and grab a ticket, I will always be served first (or removed from the queue) before you.

Here’s how it would look in visualization:

And to actually create it in JavaScript:

Here, you can see how records are moved from the top to the bottom of the queue using typical JavaScript array functions like ‘pop’ and ‘unshift.’

Stacks

Stacks are similar to queues; they also are an ordered list of records that live inside of some container.

The main difference is that they operate like Will Smith, first one in, last one out the club (song ‘Switch’ if you’re unfamiliar).

If you need another example of First-In-Last-Out — consider stacking dishes from the dishwasher. The plate you picked up first to create the stack is the last one you use when grabbing dishes later. It would like like so:

As you can see, if a record (6) was added, it is tacked on to the end. If you needed to remove a record, it also is pulled from the end of the stack.

Creating a stack looks like this:

Linked List

Finally, we have linked lists. This are of course another ordered collection of data, however linked lists actually contain nodes that are chained together. Think of a node as a JavaScript object with two key/value pairs.

Nodes instances are always initialized with some piece of data. They also hold a reference to the next node in the chain.

There are two distinct nodes to consider here:

  • Tail: the last node in the list. You can see above that the node constructor has a default ‘next’ argument of null. The tail of a linked list has no node after it, which is the reason for this default.
  • Head: the first node in the list. Linked lists are actually instantiated with this node in mind.

Linked Lists are different from queues and stacks because there are no rules about adding records. You can create functions to insert a node at the beginning of the list, the end of the list, or at a specific index. You can do the same removing nodes. This is a topic for another time — but is a very fun one to explore!