Linked Lists to the Rescue – Part II – Queues

In Part I, we looked at an implementation of Stacks using Linked Lists. In this post, we’ll look at Linked Lists with Queues.

As a review of the Linked Lists of Stacks, here’s a drawing of the implementation of Stacks using the linked-list nodes:

stack

As you can see, the latest node points to the previous node, which points to the node previous to that, etc…

Whenever we add a new node to the Stack, we make sure we point it back to the previous node. Once we “pop” the stack, we return the value of the “current” node, and follow the “current” node’s pointer back to the previous node, which we now make as the new “current” node. The previous “current” node is now orphaned, and left for the garbage collector. The main thing to note is that the pointers are going backwards (towards the left), as we add more nodes to the Stack.

In my implementation of a Queue, the pointers are going to go in the opposite direction! Check it:

queue

The pointers are now going to the right. What’s going on ? In a queue, recall that it’s “FIFO”, or “First in, First Out”. We start out with a single node as our first item. When we add a node, the previous node points to our new node.

In order to “pop” (we call it “dequeue” in this case), we have to remember our very first node on the left, so we assign a variable to keep track of it. After that first node is returned, we follow it’s pointer to the next node, and make this next node the “first” node. The first node is then orphaned, and gets cleaned up from the garbage collector.

In addition to remembering our first node, we also have to keep track of our most recent node, in order to add the future nodes to it. Let’s talk with code now:

The “@q” variable is our “first” node, and the “@current” variable is the latest node.

To summarize, creating Stacks and Queues with linked lists has some advantages:

  • We don’t need to keep track of the size of the array, and the memory is dependent strictly on how big our list is
  • As another point related to size – the bigger the size, the longer it takes to do certain operations, such as resizing. For instance, downsizing a large array takes at least as many operations as the size of the array to resize, since we’re copying the values. In linked lists, the time is independent of the size
  • It’s easier to think about conceptually, then the resizing (more of an opinion)
  • Linked lists are so cool!

    Linked Lists to the Rescue – Part I – Stacks

    As one might have imagined from the many hints and questions from the previous post, linked lists can be very useful when dealing with Stacks and Queues.

    To define a linked list, let’s start with the basic element of a linked list, called a node. Here is my silly illustration of a node:

    Screen Shot 2016-07-11 at 8.38.42 PM

    The left box represents the “value” of the node, and the right box represent where to look for the next node. That’s it!

    You can put nodes in a list like this:

    Screen Shot 2016-07-11 at 8.38.46 PM

    The leftmost node has a value, and it also tell us where to go for the next node, which is the node in the center. The center node has a value and tells us to look at the right node next. Nodes in a list are called a “linked list.”

    Let’s see a node represented in Ruby!

    In this “node class”, there are two variables: “item” and “next”.

    The “Item” can hold anything you want: Strings, Numbers, Integers, Arrays, Hashes, other Ruby classes, etc… the “list” goes on (pardon my intended pun). The “next” is like a pointer, in that it shows us where to look for the “next” node.

    To see it in action, here is one implementation of a Stack using Linked Lists:

    We need our node class, so the first line requires it. Before saying anything, see how much shorter the code is already! This has to do with not needing to remember the array size. If all you need to remember is where to go next, you don’t need to remember to resize your data structure once you hit size limits. The Linked Lists shrinks and grows on command, and “orphaned” nodes are cleaned up by the garbage collector. It seems to be more pleasant to read (and implement) the stack class using linked lists.

    The stack is initialized by creating a single node. As we add items to the stack, we tell our new node to point to our previous node. Unlike the array implementation where we had to keep track of all elements in the stack, all we ever have to know at any point in time is our latest node when we use the linked list implementation. When we remove items, we follow our latest node to the previous node, and tell the previous node to become the “current” node.

    In Part II, let’s see how to implement Queues with Linked Lists!