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.
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:
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:
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!