Detect a Loop/Cycle in a Singly Linked List
A detailed examination of the Floyd cycle detection algorithm in Ruby
In our discussions of Data Structures and Algorithms in Ruby we have investigated Singly Linked Lists and applied some standard methods on them including #push, #pop, #shift, #unshift, #get, #set, #remove, and #reverse. See here and here for the two articles going through these methods.
Odd as it may seem at first, but there are occasions when a node within a Singly Linked List may inadvertently have its #next pointer point to a node that is already in the same list instance. The photo above illustrates an example of what this could look like. One reason that this may occur could be a bug somewhere in the code, or in other cases, a node may point to a corrupted memory location. If you’re programming in Ruby or Ruby on Rails, not only will you probably not be utilizing data structures such as Linked Lists, but memory allocation and management is not even a consideration like it is in the lower-level languages of C and C++ where it becomes important.
That being said, anyone coming out of a coding bootcamp would do well to learn how to navigate these data structures as questions regarding them are often included in the coding challenge of the software engineering interview process. Besides the basic methods…
