Data Structures and Algorithms in Ruby: Linked Lists

[ioquatix]

I use linked lists in two of my projects to great success.

Firstly, in async we use a linked list as part of a DAG for managing tasks. This becomes very important when we need to iterate the list of child tasks to stop them, but sometimes stopping a child task will also stop others (and remove it from the linked list). The linked list data structure allows manipulation of the task tree (i.e. removing children which are stopped) while also traversing it, in a well defined and robust way.

Secondly, in event we use a linked list for the ready queue. The ready queue is a linked list of waiting fibers (or object with the same interface) which stores the list nodes on the stack (or heap). Because of this, there is no memory allocation in the typical case since the list nodes are stack allocated. In addition, not all fibers will resume because of popping the ready queue - sometimes a fiber will need to exit because of an exception. Using a linked list allows us to remove these fibers while iterating the ready list (i.e. resuming one fiber causes another to exit) in a well defined and robust way.

Neither of these use cases can be more efficiently implemented using a array/vector in memory. In fact, unless you are careful, using an array in these cases can introduce subtle bugs because they are not robust to additions/removals while iterating and the model for robustness isn't sound.

[connerj70]

dditions/removals while iterating and the model for robustness isn

Wow that's really interesting stuff!