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!

    Leave a Reply