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