Stack & Queue with (Singly) Linked List
Linked List, one of the topics of common data structure questions in tech interviews. I will take you guys to explore the concepts of stack and queues with linked list!
(Disclaimer: Prior Knowledge to Linked List is required for this article and the codes will be written in Javascript.)
I spent my last two weeks learning linked lists. I’ve gotta say after struggling with sorting algorithms (those bubble, insertion, merge, just — aaaahh), I found linked lists is so much easier to grasp. I will go back to sorting algorithms eventually. At this moment, I am living in the bubble of linked list (hats off to sorting algorithms🎩).
Table of Contents:
- Quick Glance at Linked List
- Stack
- Queue
- Big O of Stack and Queue
- Recap: Side-by-side-comparison: stack vs queue
Before we dive into stack and queues, let’s quickly recap what linked list is.
Quick Glance at Linked List
Linked list is a linear data structure, just like arrays. As you may or may not know, there are two types of linked lists: singly linked list and doubly linked list. Ah, even the names are so adorable. What are the major differences?
Singly Linked List: Usually the head (the first node) is provided, but not the tail.
Doubly Linked List: Both the head and the tail would be provided.
Why would we use linked list over array?
Because
- Inserting/Removing elements from an array is expensive because rooms are needed to shift or insert an element while in linked list, adding a head or tail or even inserting/removing in the middle is easy peasy. The difference between O(n) vs O(1).
- The dynamic size of linked list has made things easier, since the length of list can increase or decrease as necessary.
However
- Linked List tends to take up more memory space than arrays because of the pointers;
- Randomly accessing the element is seemingly impossible due to pointer system.
Anyways, I don’t plan to spend half of my article explaining what linked list is. I assume you want to have a better understanding with stack and queues, that’s why you are here. In this article, we would focus on using the concepts of singly linked list to explain stack and queue.
Alright, what’s stacks and what’s queues?
Stack
Before we start, here’s the starter code with our two classes: Stack and Nodes.
(New Girl Season 3 Episode 19 9:39 — Perfect example for Stack)
Quick Explanation: we would set this list as an empty list. No head(first) and no tail (last).
Think stacks as… a pile of dirty clothes you have on your chair, aka chairdrobe.
It’s 7:30 in the morning and you are getting ready for work/school. You are too lazy to find new clothes in your closet and you know it’s not laundry day yet and you know what? The clothes on the chair ain’t too dirty either. So you grab the first top you find on the pile (that you threw on last night) and sniff *deep sniff*… Yep, doesn’t smell like it’s too dirty, so you put it on. So what do you call that? LIFO, aka Last-In-First-Out. That’s pretty much what stack is. You will see that situation a lot, including recursion.
There are two methods in stacks (in array terms): unshift(the item to the head) and shift (the first item from the head). I’ll explain with codes.
push(val)
In this case, the value of 53 need to be pushed to the head of the list. Since this is not an array, there is no built-in method to “push” the value into our list. Instead, let’s write a function:
Here’s what happened:
- We first create a node with a value, in our case, 53.
- We then create a conditional statement:
Ifthe list is empty, our new node would be the head and the tail of the list.- Or
else, since we don’t want to completely mutate our original head, we set the original head into a new variabletemp. Then we set our new node as the new head and our original head become the next node withthis.first.next.
3. Last but not least, we increment the size of the list by 1.
Cool, right? Next up, let’s “pop” the 53 out of our list (like your clothes).
pop()
Similar to our push method, there’s no built-in method to “pop” the value out of the list. So we need to write one:
- The edge case:
ifthe list is empty, we don’t have to do anything and simply returnnull. - Set our current head (53) to a variable
temp. If the head and the tail (i.e. the size of the list is 1) are the same, we can set the tail tonull, as we don’t need to go through the entire list. If our list doesn’t satisfy our conditional statement, we can ignore that.
3. We then set our head to the next node (since we are removing our current head). Decrement the size of the list by 1.
4. Last but not least, the function returns the value of the current head temp.
Queue
Our starter code for Queue
Queue… that pronounces like the letter “Q.” What’s the point of the “-ueue”? Anyways, we are not learning the English language, but we are here to learn computer language. In British English, queue is a queue. In American English, queue means lining up. So that’s pretty self-explanatory of what “queue” is.
In our daily lives, we line up for… almost everything. Okay, think Stanley from the Office, who LOVES Pretzel Day.
It’s Pretzel Day and everyone has to wait for their turn for the free pretzel. The concept of queue is FIFO, aka First-In-First-Out. In array terms, there are two methods that can meet the criteria: push and shift. In Queue, push is called enqueue and shift is called dequeue. Since there’s no built in method for this, let’s build our functions.
enqueue(val)
Stanley’s excitedly waiting for his turn to get his free pretzel. But when Stanley thinks Phyllis tries to cut in the line because of Bob, nah-uh. Stanley MAD! Phyllis has to go to the back of the line.
In order to do that, our function looks like this:
Here’s what happened:
- We first create our new node (in our case, Phyllis) with the value which is accepted in the parameter.
- We then create a conditional statement:
- We first check whether there is any head (i.e. whether the list is empty or not) or not.
ifthe head does not exist, our new node would be the head and the tail of the list. else, we set the next node of our current tail to our new nodenewNode, therefore, ournewNodewould become the new tail of our list.
3. Last but not least, increment the size of our list by 1.
dequeue()
Yay! Stanley finally got his pretzel! Let’s dequeue/pop him out of our queue.
This has the exact same code as our pop function from Stack. Here are the steps once again, in case you need a reminder:
- The edge case:
ifthe list is empty, we don’t have to do anything and simply returnnull. - Set our current head (Stanley) to a variable
temp. If the head and the tail (i.e. the size of the list is 1) are the same, we can set the tail tonull, as we don’t need to go through the entire list. If our list doesn’t satisfy our conditional statement, we can ignore that.
3. We then set our head to the next node (since we are removing our current head). Decrement the size of the list by 1.
4. Last but not least, the function returns the value of the current head temp.
That’s pretty much Queue! Pretty exciting stuff and quite intuitive I’d say!
Big O of Stack and Queue
As mentioned earlier in the Linked List section, Linked List is good for insertion and removal, compared to array. In terms of the time complexity, insertion and removal in linked list is O(1) while in array, that’d be O(n), as array has to iterate through the list to shift through the index of the elements and such.
However, searching and accessing are not the best bet for linked list, since the computer has to go through each node to find that particular. Therefore, the time complexity for linked list would be O(n). But in array, the computer can simply search and access the element, since the elements are “labeled” with indexes (ex. array[1]). Therefore, the time complexity for array would be O(1).
Recap: Comparison between Stack and Queue
To conclude this article, let’s compare the difference between stack and queue.
- Stacks are based on the LIFO principle, i.e. the last element inserted at the last would be the first element to “leave” the list v.s. Queues are based on the FIFO principle, i.e. the first element inserted first would be the first element to “leave” the list.
- In Stacks, insertion and deletion take place from the top, while in Queues, insertion and deletion take place from the opposite end of the list — insertion takes place in the rear of the list and deletion takes place in the front of the list.
- Stacks: insert -> push and delete -> pop vs Queues: insert -> enqueue and delete -> dequeue
Thanks for reading this article! I apologize if you are expecting some very technical terms and explanations. I wrote this article as if I am trying to explain this to a friend who does not fully understand how computer science works and this method helps me understand the concepts more intuitively. I hope you enjoy the article!
Resources
To understand stack and queue:
For visual learners:
More about Linked List:
From how I understood the basic concepts of the data structures and algorithms I learned:
And a little humor from the Peanuts Comic:
